mlsanityData to 7 Oct 2026

A survey on the complexity of learning quantum states

arXiv 2305.20069 ↗First posted 31 May 2023quant-ph cs.CC cs.LGcited by 31

Not on the map. Why?

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.

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

Builds on

64 of 192 references.

References · 64

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018Supervised learning with quantum enhanced feature spacescited by 654
  3. 2020The power of quantum neural networkscited by 377
  4. 2020A rigorous and robust quantum speed-up in supervised machine learningcited by 270
  5. 2020Predicting Many Properties of a Quantum System from Very Few Measurementscited by 229
  6. 2021Generalization in quantum machine learning from few training datacited by 214
  7. 2019Efficient Learning for Deep Quantum Neural Networkscited by 160
  8. 2021Provably efficient machine learning for quantum many-body problemscited by 91
  9. 2021Encoding-dependent generalization bounds for parametrized quantum circuitscited by 81
  10. 2019The Born Supremacy: Quantum Advantage and Training of an Ising Born Machinecited by 75
  11. 2018A quantum-inspired classical algorithm for recommendation systemscited by 70
  12. 2016Quantum Recommendation Systemscited by 69
38 more
  1. 2020An Equivalence Between Private Classification and Online Predictioncited by 63
  2. 2016Efficient quantum tomography IIcited by 54
  3. 2014Efficiently learning Ising models on arbitrary graphscited by 50
  4. 2021Exponential separations between learning with and without quantum memorycited by 50
  5. 2022Out-of-distribution generalization for learning quantum dynamicscited by 49
  6. 2016Interaction Screening: Efficient and Sample-Optimal Learning of Ising Modelscited by 43
  7. 2017Learning Graphical Models Using Multiplicative Weightscited by 43
  8. 2018Online Learning of Quantum Statescited by 37
  9. 2019Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learningcited by 37
  10. 2020Sample-efficient learning of quantum many-body systemscited by 36
  11. 2018Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptionscited by 34
  12. 2022Learning to predict arbitrary quantum processescited by 34
  13. 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 32
  14. 2016Optimal Quantum Sample Complexity of Learning Algorithmscited by 32
  15. 2020Pseudo-dimension of quantum circuitscited by 30
  16. 2019Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithmcited by 27
  17. 2022Learning many-body Hamiltonians with Heisenberg-limited scalingcited by 22
  18. 2022Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrixcited by 22
  19. 2023Improved machine learning algorithm for predicting ground state propertiescited by 22
  20. 2020Statistical Queries and Statistical Algorithms: Foundations and Applicationscited by 21
  21. 2020Quantum statistical query learningcited by 19
  22. 2018Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimensioncited by 18
  23. 2015Quantum assisted Gaussian process regressioncited by 17
  24. 2018Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problemcited by 16
  25. 2022Dynamical simulation via quantum machine learning with provable generalizationcited by 15
  26. 2022Adaptive Online Learning of Quantum Statescited by 12
  27. 2018Quantum-inspired sublinear classical algorithms for solving low-rank linear systemscited by 11
  28. 2023Improved Stabilizer Estimation via Bell Difference Samplingcited by 11
  29. 2019Quantum-Inspired Support Vector Machinecited by 10
  30. 2019(Pseudo) Random Quantum States with Binary Phasecited by 10
  31. 2020Fast and robust quantum state tomography from few basis measurementscited by 10
  32. 2021Private learning implies quantum stabilitycited by 10
  33. 2022Optimal algorithms for learning quantum phase statescited by 10
  34. 2015The Learnability of Unknown Quantum Measurementscited by 9
  35. 2019Quantum Learning Boolean Linear Functions w.r.t. Product Distributionscited by 9
  36. 2023On the average-case complexity of learning output distributions of quantum circuitscited by 9
  37. 2017Stabiliser states are efficiently PAC-learnablecited by 8
  38. 2018Two new results about quantum exact learningcited by 8

50 most cited of 64 All 64 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 9; 2024: 15; 2025: 6; 2026: 1.

31 papers.

Sort:

  1. 2024Barren Plateaus in Variational Quantum Computingcited by 130
  2. 2023Does provable absence of barren plateaus imply classical simulability?cited by 78
  3. 2023Learning quantum Hamiltonians at any temperature in polynomial timecited by 20
  4. 2024Learning shallow quantum circuitscited by 20
  5. 2023Beyond Classical Attention: Quantum Attention for Scalable Computationcited by 18
  6. 2023Learning quantum states and unitaries of bounded gate complexitycited by 15
  7. 2025Artificial intelligence for representing and characterizing quantum systemscited by 9
  8. 2025A Primer on Quantum Machine Learningcited by 9
  9. 2024Solving The Quantum Many-Body Hamiltonian Learning Problem with Neural Differential Equationscited by 7
  10. 2024Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuitscited by 7
  11. 2024Learning quantum states prepared by shallow circuits in polynomial timecited by 6
  12. 2023On the Role of Entanglement and Statistics in Learningcited by 5
19 more
  1. 2023Transition Role of Entangled Data in Quantum Machine Learningcited by 5
  2. 2024Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimationcited by 5
  3. 2024On the sample complexity of purity and inner product estimationcited by 4
  4. 2023Provable learning of quantum states with graphical modelscited by 3
  5. 2023Learning finitely correlated states: stability of the spectral reconstructioncited by 3
  6. 2023Efficient Learning of Long-Range and Equivariant Quantum Systemscited by 3
  7. 2024Agnostic Tomography of Stabilizer Product Statescited by 3
  8. 2024Concept learning of parameterized quantum models from limited measurementscited by 3
  9. 2024Efficient Hamiltonian, structure and trace distance learning of Gaussian statescited by 2
  10. 2024Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theoremcited by 1
  11. 2024Accurate Learning of Equivariant Quantum Systems from a Single Ground Statecited by 1
  12. 2024Reinforcement learning to learn quantum states for Heisenberg scaling accuracycited by 1
  13. 2025Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applicationscited by 1
  14. 2024Learning quantum Hamiltonians at any temperature in polynomial time with Chebyshev and bit complexitycited by 0
  15. 2024Proper vs Improper Quantum PAC learningcited by 0
  16. 2025Learning to erase quantum states: thermodynamic implications of quantum learning theorycited by 0
  17. 2025Efficient learning of bosonic Gaussian unitariescited by 0
  18. 2025Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and morecited by 0
  19. 2026The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)cited by 0