Learning Sparse Quantum States — Draconitic Research

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−ε with high probability using Õ(k/ε) copies of the state and Õ(kn/ε) time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal Õ(kr/ε) 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.

Learning sparse quantum states from single-qubit measurements
Su-un Lee, Liang Jiang, Kunal Sharma
arXiv28 Sep 2026PreprintarXiv licenceFull textGeneral mathematics Quantum physics & quantum informationarXiv
Resource-Efficient Synthesis of Sparse Quantum States
Renaud Vilmart, Sunheang Ty, Chetra Mang
HAL19 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationHAL
Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
Zekun Ye
arXiv13 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
From sparse quantum-computing data to atomistic simulation with universal machine-learning interatomic potentials
Tuan Minh Do, Yuichiro Yoshida, Kenji Ishihara +1
arXiv18 Sep 2026PreprintarXiv licenceFull textPhysical chemistry Quantum physics & quantum informationarXiv
Learning photonic quantum states
Hugo Thomas, Ulysse Chabaud, Pierre-Emmanuel Emeriau
PRX Quantum16 Oct 2026Peer-reviewedPublisher termsQuantum physics & quantum informationCrossref

Cite

BibTeX RIS

BibTeX

@misc{sen2026learning,
  title = {{Learning Sparse Quantum States}},
  author = {Aniruddha Sen},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.12219},
  eprint = {2609.12219},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.12219},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Learning Sparse Quantum States
AU  - Aniruddha Sen
PY  - 2026
DA  - 2026/09/10
PB  - arXiv
DO  - 10.48550/arxiv.2609.12219
UR  - https://arxiv.org/abs/2609.12219
AB  - 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−ε with high probability using Õ(k/ε) copies of the state and Õ(kn/ε) time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal Õ(kr/ε) 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.
ER  -

Abstract

Related

Cite