# Optimal Quantum Sample Complexity of Learning Algorithms

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2016.

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

- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Variational inference with a quantum computer](https://mlsanity.com/paper/2103.06720/) (2021)
- [Sample Complexity of Learning Parametric Quantum Circuits](https://mlsanity.com/paper/2107.09078/) (2021)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [Quantum Local Differential Privacy and Quantum Statistical Query Model](https://mlsanity.com/paper/2203.03591/) (2022)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Generative quantum advantage for classical and quantum problems](https://mlsanity.com/paper/2509.09033/) (2025)
- [On the Hardness of PAC-learning Stabilizer States with Noise](https://mlsanity.com/paper/2102.05174/) (2021)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [An invitation to the sample complexity of quantum hypothesis testing](https://mlsanity.com/paper/2403.17868/) (2024)
- [Inference, interference and invariance: How the Quantum Fourier Transform can help to learn from data](https://mlsanity.com/paper/2409.00172/) (2024)
- [From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability](https://mlsanity.com/paper/2106.01382/) (2021)
- [Optimal lower bounds for Quantum Learning via Information Theory](https://mlsanity.com/paper/2301.02227/) (2023)
- [Learning Quantum Processes with Quantum Statistical Queries](https://mlsanity.com/paper/2310.02075/) (2023)
- [Quantum Learning Theory Beyond Batch Binary Classification](https://mlsanity.com/paper/2302.07409/) (2023)
- [Provable learning of quantum states with graphical models](https://mlsanity.com/paper/2309.09235/) (2023)
- [Quantum advantage for learning shallow neural networks with natural data distributions](https://mlsanity.com/paper/2503.20879/) (2025)
- [Efficient Quantum Agnostic Improper Learning of Decision Trees](https://mlsanity.com/paper/2210.00212/) (2022)
- [Quantum Boosting using Domain-Partitioning Hypotheses](https://mlsanity.com/paper/2110.12793/) (2021)
- [Clifford Circuits can be Properly PAC Learned if and only if textsfRP=textsfNP](https://mlsanity.com/paper/2204.06638/) (2022)
- [Advances in Machine Learning: Where Can Quantum Techniques Help?](https://mlsanity.com/paper/2507.08379/) (2025)
- [Information-Theoretic Limits of Quantum Learning via Data Compression](https://mlsanity.com/paper/2112.06841/) (2021)
- [Unclonability and Quantum Cryptanalysis: From Foundations to Applications](https://mlsanity.com/paper/2210.17545/) (2022)
- [Fat Shattering, Joint Measurability, and PAC Learnability of POVM Hypothesis Classes](https://mlsanity.com/paper/2308.12304/) (2023)
- [Proper vs Improper Quantum PAC learning](https://mlsanity.com/paper/2403.03295/) (2024)
- [Expanding the Horizon: Enabling Hybrid Quantum Transfer Learning for Long-Tailed Chest X-Ray Classification](https://mlsanity.com/paper/2405.00156/) (2024)
- [The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)](https://mlsanity.com/paper/2602.01054/) (2026)
- [A Quantum/Classical Example Oracle Separation for Making Things Up](https://mlsanity.com/paper/2608.11648/) (2026)

## Abstract (arXiv)

 newcommandepsvarepsilon In learning theory, the VC dimension of a concept class C is the most common way to measure its "richness." In the PAC model  ThetaBig(fracdeps + fraclog(1/δ)epsBig)  examples are necessary and sufficient for a learner to output, with probability 1-δ, a hypothesis h that is eps-close to the target concept c. In the related agnostic model, where the samples need not come from a c∈ C, we know that  ThetaBig(fracdeps2 + fraclog(1/δ)eps2Big)  examples are necessary and sufficient to output an hypothesis h∈ C whose error is at most eps worse than the best concept in C. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson, who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio, improved by Zhang, showed that in the PAC setting, quantum examples cannot be much more powerful: the required number of quantum examples is  OmegaBig(fracd1-ηeps + d + fraclog(1/δ)epsBig)mbox for all η> 0.  Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a log(d/eps) factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the "Pretty Good Measurement" on the quantum state identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors.