mlsanityData to 7 Oct 2026

The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)

arXiv 2602.01054 ↗First posted 1 Feb 2026quant-ph cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

This paper surveys various results in the field of Quantum Learning theory, specifically focusing on learning quantum-encoded classical concepts in the Probably Approximately Correct (PAC) framework. The cornerstone of this work is the emphasis on query, sample, and time complexity separations between classical and quantum learning that emerge under learning with query access to different labeling oracles. This paper aims to consolidate all known results in the area under the above umbrella and underscore the limits of our understanding by leaving the reader with 23 open problems.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 20 of its 99 references that are in the map. First posted on arXiv 1 Feb 2026.

Builds on

20 of 99 references.

References · 20

  1. 2020A rigorous and robust quantum speed-up in supervised machine learningcited by 270
  2. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  3. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  4. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  5. 2016Optimal Quantum Sample Complexity of Learning Algorithmscited by 32
  6. 2023A survey on the complexity of learning quantum statescited by 31
  7. 2014A PTAS for Agnostically Learning Halfspacescited by 21
  8. 2019Quantum Learning Boolean Linear Functions w.r.t. Product Distributionscited by 9
  9. 2022Superpolynomial Lower Bounds for Decision Tree Learning and Testingcited by 9
  10. 2018Two new results about quantum exact learningcited by 8
  11. 2019Quantum hardness of learning shallow classical circuitscited by 7
  12. 2023Classical Verification of Quantum Learningcited by 6
8 more
  1. 2023Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithmscited by 6
  2. 2024Online learning of a panoply of quantum objectscited by 5
  3. 2023Optimal lower bounds for Quantum Learning via Information Theorycited by 4
  4. 2025Amplitude amplification and estimation require inversescited by 4
  5. 2016Distribution Free Learning with Local Queriescited by 3
  6. 2023Quantum Learning Theory Beyond Batch Binary Classificationcited by 3
  7. 2018Learning DNFs under product distributions via μ-biased quantum Fourier samplingcited by 2
  8. 2022Efficient Quantum Agnostic Improper Learning of Decision Treescited by 2

Built on by

Not cited yet.