# Exponential separations between classical and quantum learners

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 53 references that are in the map.
- First posted on arXiv 28 Jun 2023.

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

- [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)
- [Provably efficient machine learning for quantum many-body problems](https://mlsanity.com/paper/2106.12627/) (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)
- [Learning many-body Hamiltonians with Heisenberg-limited scaling](https://mlsanity.com/paper/2210.03030/) (2022)
- [On establishing learning separations between classical and quantum machine learning with classical data](https://mlsanity.com/paper/2208.06339/) (2022)

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

- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (2023)
- [On the relation between trainability and dequantization of variational quantum learning models](https://mlsanity.com/paper/2406.07072/) (2024)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Exponential quantum advantage in processing massive classical data](https://mlsanity.com/paper/2604.07639/) (2026)
- [Artificial intelligence for representing and characterizing quantum systems](https://mlsanity.com/paper/2509.04923/) (2025)
- [Double descent in quantum kernel methods](https://mlsanity.com/paper/2501.10077/) (2025)
- [Expressibility-induced Concentration of Quantum Neural Tangent Kernels](https://mlsanity.com/paper/2311.04965/) (2023)
- [Quantum delegated and federated learning via quantum homomorphic encryption](https://mlsanity.com/paper/2409.19359/) (2024)
- [Quantum computing and artificial intelligence: status and perspectives](https://mlsanity.com/paper/2505.23860/) (2025)
- [Advantage of Quantum Machine Learning from General Computational Advantages](https://mlsanity.com/paper/2312.03057/) (2023)
- [Entanglement-induced provable and robust quantum learning advantages](https://mlsanity.com/paper/2410.03094/) (2024)
- [Prospects for quantum advantage in machine learning from the representability of functions](https://mlsanity.com/paper/2512.15661/) (2025)
- [TQml Simulator: optimized simulation of quantum machine learning](https://mlsanity.com/paper/2506.04891/) (2025)
- [Learning Reduced Representations for Quantum Classifiers](https://mlsanity.com/paper/2512.01509/) (2025)
- [Quantum Machine Learning for Industrial Applications](https://mlsanity.com/paper/2606.14822/) (2026)
- [Provable learning separation for predicting time-evolution of quantum many-body systems](https://mlsanity.com/paper/2607.06472/) (2026)
- [Can Geometric Quantum Machine Learning Lead to Advantage in Barcode Classification?](https://mlsanity.com/paper/2409.01496/) (2024)
- [The role of data-induced randomness in quantum machine learning classification tasks](https://mlsanity.com/paper/2411.19281/) (2024)
- [Detecting underdetermination in parameterized quantum circuits](https://mlsanity.com/paper/2504.03315/) (2025)
- [Limitations of Using Identical Distributions for Training and Testing When Learning Boolean Functions](https://mlsanity.com/paper/2512.00791/) (2025)
- [A Quantum/Classical Example Oracle Separation for Making Things Up](https://mlsanity.com/paper/2608.11648/) (2026)
- [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)
- [Classical Hardness of Learning Functions of Hamiltonians](https://mlsanity.com/paper/2610.01141/) (2026)
- [Quantum Machine Learning Protection of Military Quantum Key Distribution Against Cryptographically Camouflaged Attacks](https://mlsanity.com/paper/2610.04543/) (2026)
- [Verifiable Sampling for Delegated Generative Quantum Machine Learning](https://mlsanity.com/paper/2610.13211/) (2026)

## Abstract (arXiv)

Despite significant effort, the quantum machine learning community has only demonstrated quantum learning advantages for artificial cryptography-inspired datasets when dealing with classical data. In this paper we address the challenge of finding learning problems where quantum learning algorithms can achieve a provable exponential speedup over classical learning algorithms. We reflect on computational learning theory concepts related to this question and discuss how subtle differences in definitions can result in significantly different requirements and tasks for the learner to meet and solve. We examine existing learning problems with provable quantum speedups and find that they largely rely on the classical hardness of evaluating the function that generates the data, rather than identifying it. To address this, we present two new learning separations where the classical difficulty primarily lies in identifying the function generating the data. Furthermore, we explore computational hardness assumptions that can be leveraged to prove quantum speedups in scenarios where data is quantum-generated, which implies likely quantum advantages in a plethora of more natural settings (e.g., in condensed matter and high energy physics). We also discuss the limitations of the classical shadow paradigm in the context of learning separations, and how physically-motivated settings such as characterizing phases of matter and Hamiltonian learning fit in the computational learning framework.