aiqbench analysis
This paper presents the first near-optimal algorithm for learning k-sparse pure quantum states, establishing tight sample and time complexity bounds previously unknown in this domain. By leveraging the random purification channel technique, the authors also derive efficient methods for learning mixed states, though matching time complexity for higher-rank cases remains an open challenge. These advances significantly improve our theoretical understanding of quantum state tomography efficiency relative to classical distribution learning.
Learning Sparse Quantum States
arXiv:2609.12219v1 Announce Type: new Abstract: 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.
Abstract: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.
Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
arXiv:2609.12219 [quant-ph]
(or arXiv:2609.12219v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2609.12219 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 222 words
Related coverage
Researchers Develop Machine Learning Framework for Wigner Function Reconstruction from Sparse Data
Quantum Zeitgeist · Jul 21, 2026
Learning sparse quantum states from single-qubit measurements
arXiv · Sep 30, 2026
Sparse Hamiltonians can be learned with slower quantum controls
Quantum Zeitgeist · Oct 16, 2026
Synthesis Superintelligence: from Semiconductors to Superconductors — Periodic Labs’ Liam Fedus and Ekin Dogus Cubuk
Latent Space · Oct 8, 2026