Metraipolis › archive › dc_4519ce704ea5
Learning Sparse Quantum States — arXiv:2609.12219
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.12219
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T03:59:04.360Z
- SHA-256 of the archived text
3ff8243b64ccd950bc272a16aae18d152964f4fb68ac71a50c2c6ad26c7683f4- Stable URL of this page
https://metraipolis.com/documento/dc_4519ce704ea5
How to cite
Learning Sparse Quantum States — arXiv:2609.12219 — arXiv (en), https://arxiv.org/abs/2609.12219 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4519ce704ea5 (Metraipolis archive dc_4519ce704ea5, sha256 3ff8243b64ccd950bc272a16aae18d152964f4fb68ac71a50c2c6ad26c7683f4)
BibTeX
@misc{dc4519ce704ea5,
title = {Learning Sparse Quantum States — arXiv:2609.12219},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.12219},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4519ce704ea5; sha256 3ff8243b64ccd950bc272a16aae18d152964f4fb68ac71a50c2c6ad26c7683f4},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12219. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 also obtain an algorithm with near optimal $\tilde{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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-14 in cs.DS).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.12219 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T03:50:18.684Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).