# On establishing learning separations between classical and quantum machine learning with classical data

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 20 references that are in the map.
- First posted on arXiv 12 Aug 2022.

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

- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [The effect of data encoding on the expressive power of variational quantum machine learning models](https://mlsanity.com/paper/2008.08605/) (2020)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Encoding-dependent generalization bounds for parametrized quantum circuits](https://mlsanity.com/paper/2106.03880/) (2021)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [Quantum hardness of learning shallow classical circuits](https://mlsanity.com/paper/1903.02840/) (2019)

## Built on by (most cited first, 15 of 15)

- [Shadows of quantum machine learning](https://mlsanity.com/paper/2306.00061/) (2023)
- [Exponential separations between classical and quantum learners](https://mlsanity.com/paper/2306.16028/) (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)
- [A super-polynomial quantum-classical separation for density modelling](https://mlsanity.com/paper/2210.14936/) (2022)
- [Advantage of Quantum Machine Learning from General Computational Advantages](https://mlsanity.com/paper/2312.03057/) (2023)
- [Provable advantages of kernel-based quantum learners and quantum preprocessing based on Grover's algorithm](https://mlsanity.com/paper/2309.14406/) (2023)
- [Guided Quantum Compression for High Dimensional Data Classification](https://mlsanity.com/paper/2402.09524/) (2024)
- [Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises](https://mlsanity.com/paper/2405.00770/) (2024)
- [Exploiting the equivalence between quantum neural networks and perceptrons](https://mlsanity.com/paper/2407.04371/) (2024)
- [An unconditional distribution learning advantage with shallow quantum circuits](https://mlsanity.com/paper/2411.15548/) (2024)
- [Satellite image classification with neural quantum kernels](https://mlsanity.com/paper/2409.20356/) (2024)
- [An Efficient Quantum Classifier Based on Hamiltonian Representations](https://mlsanity.com/paper/2504.10542/) (2025)
- [A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features](https://mlsanity.com/paper/2609.10729/) (2026)
- [Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries](https://mlsanity.com/paper/2609.38403/) (2026)

## Abstract (arXiv)

Despite years of effort, the quantum machine learning community has only been able to show quantum learning advantages for certain contrived cryptography-inspired datasets in the case of classical data. In this note, we discuss the challenges of finding learning problems that quantum learning algorithms can learn much faster than any classical learning algorithm, and we study how to identify such learning problems. Specifically, we reflect on the main concepts in computational learning theory pertaining to this question, and we discuss how subtle changes in definitions can mean conceptually significantly different tasks, which can either lead to a separation or no separation at all. Moreover, we study existing learning problems with a provable quantum speedup to distill sets of more general and sufficient conditions (i.e., ``checklists'') for a learning problem to exhibit a separation between classical and quantum learners. These checklists are intended to streamline one's approach to proving quantum speedups for learning problems, or to elucidate bottlenecks. Finally, to illustrate its application, we analyze examples of potential separations (i.e., when the learning problem is build from computational separations, or when the data comes from a quantum experiment) through the lens of our approach.