arXiv:2609.35648
Learning sparse quantum states from single-qubit measurements
Su-un Lee, Liang Jiang, Kunal Sharma
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.
AI Summary
The paper asks whether an $n$-qubit state whose density matrix has at most $s$ nonzero entries in an unknown product basis can be reconstructed using only single-qubit measurements. This class includes long-range-entangled states, such as GHZ states, whose global phases cannot be recovered from proper reduced density matrices. For a known sparsifying basis, reconstruction to trace-norm error $\varepsilon$ uses $O(s^4\log s/\varepsilon^2)$ copies and $O(ns^4\log s/\varepsilon^2)$ classical time, at constant failure probability. The underlying selected-entry tomography estimates any specified matrix element using $O(\varepsilon^{-2}\log(1/\delta))$ copies, independently of $n$, through randomized product-Pauli measurements. For arbitrary unknown product bases, one algorithm achieves sample complexity and runtime $2^{O(s(\log s)^2)}(n/\varepsilon)^{O(s)}$, polynomial for constant $s$. Sparse-distribution Fourier bounds and contractions of low-order Pauli-moment tensors recover most local bases after enumerating a small exceptional qubit set. A second algorithm recursively merges reconstructed blocks and searches for sparse representations. It uses $O(n^6s^{12}\varepsilon^{-4}\log^2(ns))$ copies, but takes $(ns/\varepsilon)^{O(n)}$ classical time in general. If local bases belong to a known fixed finite set, a Donoho–Stark uncertainty bound restricts basis changes to $O(\log s)$ qubits, reducing runtime to $n^{O(\log s)}/\varepsilon^4$. Measurements adapt between copies, without within-copy feed-forward. General polynomial-time reconstruction for polynomial $s$ remains unestablished. Outputs are sparse operators, not necessarily physical density matrices. A constant-sparsity testing extension distinguishes distance $O(\varepsilon^4/n)$ from distance greater than $\varepsilon$ to sparse operators.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.