# A survey on the complexity of learning quantum states

arXiv: https://arxiv.org/abs/2305.20069 · HTML: https://mlsanity.com/paper/2305.20069/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 64 of its 192 references that are in the map.
- First posted on arXiv 31 May 2023.

## Builds on (most cited first, 30 of 64)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [The power of quantum neural networks](https://mlsanity.com/paper/2011.00027/) (2020)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Generalization in quantum machine learning from few training data](https://mlsanity.com/paper/2111.05292/) (2021)
- [Efficient Learning for Deep Quantum Neural Networks](https://mlsanity.com/paper/1902.10445/) (2019)
- [Provably efficient machine learning for quantum many-body problems](https://mlsanity.com/paper/2106.12627/) (2021)
- [Encoding-dependent generalization bounds for parametrized quantum circuits](https://mlsanity.com/paper/2106.03880/) (2021)
- [The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine](https://mlsanity.com/paper/1904.02214/) (2019)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Online Learning of Quantum States](https://mlsanity.com/paper/1802.09025/) (2018)
- [Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning](https://mlsanity.com/paper/1910.06151/) (2019)
- [Sample-efficient learning of quantum many-body systems](https://mlsanity.com/paper/2004.07266/) (2020)
- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions](https://mlsanity.com/paper/1811.00414/) (2018)
- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [Pseudo-dimension of quantum circuits](https://mlsanity.com/paper/2002.01490/) (2020)
- [Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm](https://mlsanity.com/paper/1910.02071/) (2019)
- [Learning many-body Hamiltonians with Heisenberg-limited scaling](https://mlsanity.com/paper/2210.03030/) (2022)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)

## Built on by (most cited first, 30 of 32)

- [Barren Plateaus in Variational Quantum Computing](https://mlsanity.com/paper/2405.00781/) (2024)
- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (2023)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Learning shallow quantum circuits](https://mlsanity.com/paper/2401.10095/) (2024)
- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Learning quantum states and unitaries of bounded gate complexity](https://mlsanity.com/paper/2310.19882/) (2023)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Artificial intelligence for representing and characterizing quantum systems](https://mlsanity.com/paper/2509.04923/) (2025)
- [Solving The Quantum Many-Body Hamiltonian Learning Problem with Neural Differential Equations](https://mlsanity.com/paper/2408.08639/) (2024)
- [Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits](https://mlsanity.com/paper/2408.12199/) (2024)
- [Learning quantum states prepared by shallow circuits in polynomial time](https://mlsanity.com/paper/2410.23618/) (2024)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [Transition Role of Entangled Data in Quantum Machine Learning](https://mlsanity.com/paper/2306.03481/) (2023)
- [Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation](https://mlsanity.com/paper/2408.06967/) (2024)
- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)
- [Learning finitely correlated states: stability of the spectral reconstruction](https://mlsanity.com/paper/2312.07516/) (2023)
- [Agnostic Tomography of Stabilizer Product States](https://mlsanity.com/paper/2404.03813/) (2024)
- [Provable learning of quantum states with graphical models](https://mlsanity.com/paper/2309.09235/) (2023)
- [Efficient Learning of Long-Range and Equivariant Quantum Systems](https://mlsanity.com/paper/2312.17019/) (2023)
- [Concept learning of parameterized quantum models from limited measurements](https://mlsanity.com/paper/2408.05116/) (2024)
- [Efficient Hamiltonian, structure and trace distance learning of Gaussian states](https://mlsanity.com/paper/2411.03163/) (2024)
- [Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem](https://mlsanity.com/paper/2405.07226/) (2024)
- [Accurate Learning of Equivariant Quantum Systems from a Single Ground State](https://mlsanity.com/paper/2405.12309/) (2024)
- [Reinforcement learning to learn quantum states for Heisenberg scaling accuracy](https://mlsanity.com/paper/2412.02334/) (2024)
- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [Efficient learning of bosonic Gaussian unitaries](https://mlsanity.com/paper/2510.05531/) (2025)
- [Learning quantum Hamiltonians at any temperature in polynomial time with Chebyshev and bit complexity](https://mlsanity.com/paper/2402.05552/) (2024)
- [Proper vs Improper Quantum PAC learning](https://mlsanity.com/paper/2403.03295/) (2024)
- [Learning to erase quantum states: thermodynamic implications of quantum learning theory](https://mlsanity.com/paper/2504.07341/) (2025)
- [Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more](https://mlsanity.com/paper/2510.06848/) (2025)

## Abstract (arXiv)

We survey various recent results that rigorously study the complexity of learning quantum states. These include progress on quantum tomography, learning physical quantum states, alternate learning models to tomography and learning classical functions encoded as quantum states. We highlight how these results are paving the way for a highly successful theory with a range of exciting open questions. To this end, we distill 25 open questions from these results.