Learning sparse quantum states from single-qubit measurements
Abstract
We study the problem of learning a sparse quantum state, an n-qubit quantum state whose density matrix has at most s nonzero matrix entries in an unknown product basis. While such states admit compact classical descriptions, they can carry long-range entanglement that prevents reconstruction from local reduced density matrices alone. Therefore, previous learning approaches addressed such long-range-entangled states using many entangling gates to extract the necessary information. In this work, we show that sparse states can nevertheless be efficiently learned using only single-qubit measurements. Specifically, when the sparsity s is constant, our algorithm can learn sparse states from single-qubit measurements with polynomial sample complexity and classical computational complexity. When s grows polynomially with n, sparse states can still be learned from single-qubit measurements with polynomial sample complexity, although efficient classical computation is not guaranteed in general. In this regime, however, the classical computational complexity becomes quasipolynomial when the state is sparse in an unknown basis that is a product of a known fixed finite set of single-qubit bases (e.g., eigenbases of Pauli operators). These results establish efficient learning of sparse states with long-range entanglement without entangling gates, and the single-qubit measurement requirements make our algorithms compatible with current quantum devices.
Related
- Exact Entanglement Swapping through Single-Occupancy Measurements in Gaussian Fermion States
- Quantum simultaneous decoding via pretty-good measurements of tilted states
- Adaptive Local Measurements For Quantum Learning Can Exponentially Outperform Nonadaptive Global Measurements
- Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means
- Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements
BibTeX
@misc{lee2026learning,
title = {{Learning sparse quantum states from single-qubit measurements}},
author = {Su-un Lee and Liang Jiang and Kunal Sharma},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35648},
eprint = {2609.35648},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35648},
}
RIS
TY - UNPB
TI - Learning sparse quantum states from single-qubit measurements
AU - Su-un Lee
AU - Liang Jiang
AU - Kunal Sharma
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35648
UR - https://arxiv.org/abs/2609.35648
AB - We study the problem of learning a sparse quantum state, an n-qubit quantum state whose density matrix has at most s nonzero matrix entries in an unknown product basis. While such states admit compact classical descriptions, they can carry long-range entanglement that prevents reconstruction from local reduced density matrices alone. Therefore, previous learning approaches addressed such long-range-entangled states using many entangling gates to extract the necessary information. In this work, we show that sparse states can nevertheless be efficiently learned using only single-qubit measurements. Specifically, when the sparsity s is constant, our algorithm can learn sparse states from single-qubit measurements with polynomial sample complexity and classical computational complexity. When s grows polynomially with n, sparse states can still be learned from single-qubit measurements with polynomial sample complexity, although efficient classical computation is not guaranteed in general. In this regime, however, the classical computational complexity becomes quasipolynomial when the state is sparse in an unknown basis that is a product of a known fixed finite set of single-qubit bases (e.g., eigenbases of Pauli operators). These results establish efficient learning of sparse states with long-range entanglement without entangling gates, and the single-qubit measurement requirements make our algorithms compatible with current quantum devices.
ER -