{"id":"arxiv/2609.12219","url":"https://arxiv.org/abs/2609.12219","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Learning Sparse Quantum States","domain":"quant-ph","source":"arxiv","authors":["Aniruddha Sen"],"reviews":0,"subject":"quant-ph","summary":"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 $\\tilde{O}(k/\\varepsilon)$ copies of the state and $\\tilde{O}(kn/\\varepsilon)$ time. Both bounds are optimal up to polylogarithmic factors. As an implication, we…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-10","reactions":{}}