Learning Sparse Quantum States

We study the problem of tomography for k-sparse quantum states. In contrast to classical distribution learning, where tight sample and time complexity bounds in terms of support size are well understood, no non-trivial bounds were previously shown for this problem. We give the first near optimal algorithm for learning n-qubit k-sparse pure quantum states, obtaining fidelity at least 1-varepsilon with high probability using {O}\(k/varepsilon\) copies of the state and {O}\(kn/varepsilon\) time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal {O}\(kr/varepsilon\) sample complexity for learning k-sparse rank-r mixed states, via the random purification channel technique. Obtaining time complexity nearly matching the sample complexity, for r>1, remains an important open question.