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

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

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [A PTAS for Agnostically Learning Halfspaces](https://mlsanity.com/paper/1410.7050/) (2014)
- [Quantum Learning Boolean Linear Functions w.r.t. Product Distributions](https://mlsanity.com/paper/1902.08753/) (2019)
- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)
- [Two new results about quantum exact learning](https://mlsanity.com/paper/1810.00481/) (2018)
- [Quantum hardness of learning shallow classical circuits](https://mlsanity.com/paper/1903.02840/) (2019)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms](https://mlsanity.com/paper/2310.17716/) (2023)
- [Amplitude amplification and estimation require inverses](https://mlsanity.com/paper/2507.23787/) (2025)
- [Online learning of a panoply of quantum objects](https://mlsanity.com/paper/2406.04245/) (2024)
- [Optimal lower bounds for Quantum Learning via Information Theory](https://mlsanity.com/paper/2301.02227/) (2023)
- [Distribution Free Learning with Local Queries](https://mlsanity.com/paper/1603.03714/) (2016)
- [Quantum Learning Theory Beyond Batch Binary Classification](https://mlsanity.com/paper/2302.07409/) (2023)
- [Learning DNFs under product distributions via μ-biased quantum Fourier sampling](https://mlsanity.com/paper/1802.05690/) (2018)
- [Efficient Quantum Agnostic Improper Learning of Decision Trees](https://mlsanity.com/paper/2210.00212/) (2022)

## 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.