# On the Quantum versus Classical Learnability of Discrete Distributions

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

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jul 2020.

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

- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Quantum machine learning beyond kernel methods](https://mlsanity.com/paper/2110.13162/) (2021)
- [Parametrized quantum policies for reinforcement learning](https://mlsanity.com/paper/2103.05577/) (2021)
- [Exponential concentration in quantum kernel methods](https://mlsanity.com/paper/2208.11060/) (2022)
- [Encoding-dependent generalization bounds for parametrized quantum circuits](https://mlsanity.com/paper/2106.03880/) (2021)
- [Understanding quantum machine learning also requires rethinking generalization](https://mlsanity.com/paper/2306.13461/) (2023)
- [Enhancing Generative Models via Quantum Correlations](https://mlsanity.com/paper/2101.08354/) (2021)
- [Classical surrogates for quantum learning models](https://mlsanity.com/paper/2206.11740/) (2022)
- [Trainability barriers and opportunities in quantum generative modeling](https://mlsanity.com/paper/2305.02881/) (2023)
- [Towards provably efficient quantum algorithms for large-scale machine-learning models](https://mlsanity.com/paper/2303.03428/) (2023)
- [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)
- [On the relation between trainability and dequantization of variational quantum learning models](https://mlsanity.com/paper/2406.07072/) (2024)
- [Quantum Policy Gradient Algorithm with Optimized Action Decoding](https://mlsanity.com/paper/2212.06663/) (2022)
- [Variational inference with a quantum computer](https://mlsanity.com/paper/2103.06720/) (2021)
- [On the expressivity of embedding quantum kernels](https://mlsanity.com/paper/2309.14419/) (2023)
- [A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Models](https://mlsanity.com/paper/2303.15626/) (2023)
- [On establishing learning separations between classical and quantum machine learning with classical data](https://mlsanity.com/paper/2208.06339/) (2022)
- [Quantum Machine Learning on Near-Term Quantum Devices: Current State of Supervised and Unsupervised Techniques for Real-World Applications](https://mlsanity.com/paper/2307.00908/) (2023)
- [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)
- [A super-polynomial quantum-classical separation for density modelling](https://mlsanity.com/paper/2210.14936/) (2022)
- [Double descent in quantum kernel methods](https://mlsanity.com/paper/2501.10077/) (2025)
- [Generalization Metrics for Practical Quantum Advantage in Generative Models](https://mlsanity.com/paper/2201.08770/) (2022)
- [Learnability of the output distributions of local quantum circuits](https://mlsanity.com/paper/2110.05517/) (2021)
- [Classical versus Quantum: comparing Tensor Network-based Quantum Circuits on LHC data](https://mlsanity.com/paper/2202.10471/) (2022)
- [Completely Quantum Neural Networks](https://mlsanity.com/paper/2202.11727/) (2022)
- [Hyperparameter Importance of Quantum Neural Networks Across Small Datasets](https://mlsanity.com/paper/2206.09992/) (2022)
- [Quantum delegated and federated learning via quantum homomorphic encryption](https://mlsanity.com/paper/2409.19359/) (2024)
- [Power of Quantum Generative Learning](https://mlsanity.com/paper/2205.04730/) (2022)

## Abstract (arXiv)

Here we study the comparative power of classical and quantum learners for generative modelling within the Probably Approximately Correct (PAC) framework. More specifically we consider the following task: Given samples from some unknown discrete probability distribution, output with high probability an efficient algorithm for generating new samples from a good approximation of the original distribution. Our primary result is the explicit construction of a class of discrete probability distributions which, under the decisional Diffie-Hellman assumption, is provably not efficiently PAC learnable by a classical generative modelling algorithm, but for which we construct an efficient quantum learner. This class of distributions therefore provides a concrete example of a generative modelling problem for which quantum learners exhibit a provable advantage over classical learning algorithms. In addition, we discuss techniques for proving classical generative modelling hardness results, as well as the relationship between the PAC learnability of Boolean functions and the PAC learnability of discrete probability distributions.