mlsanityData to 7 Oct 2026

On the Quantum versus Classical Learnability of Discrete Distributions

arXiv 2007.14451 ↗First posted 28 Jul 2020quant-ph cs.LGcited by 57

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 13; 2023: 13; 2024: 6; 2025: 10; 2026: 7.

57 papers.

Sort:

By area:

  1. 2021Information-theoretic bounds on quantum advantage in machine learningcited by 95
  2. 2021Quantum machine learning beyond kernel methodscited by 91
  3. 2022Exponential concentration in quantum kernel methodscited by 89
  4. 2021Parametrized quantum policies for reinforcement learningcited by 87
  5. 2021Encoding-dependent generalization bounds for parametrized quantum circuitscited by 81
  6. 2023Understanding quantum machine learning also requires rethinking generalizationcited by 48
  7. 2021Enhancing Generative Models via Quantum Correlationscited by 40
  8. 2022Classical surrogates for quantum learning modelscited by 39
  9. 2023Trainability barriers and opportunities in quantum generative modelingcited by 35
  10. 2023Towards provably efficient quantum algorithms for large-scale machine-learning modelscited by 32
  11. 2023Shadows of quantum machine learningcited by 31
  12. 2024On the relation between trainability and dequantization of variational quantum learning modelscited by 24
38 more
  1. 2022Quantum Policy Gradient Algorithm with Optimized Action Decodingcited by 21
  2. 2023Exponential separations between classical and quantum learnerscited by 21
  3. 2021Variational inference with a quantum computercited by 18
  4. 2023On the expressivity of embedding quantum kernelscited by 17
  5. 2022On establishing learning separations between classical and quantum machine learning with classical datacited by 15
  6. 2023A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Modelscited by 15
  7. 2023Quantum Machine Learning on Near-Term Quantum Devices: Current State of Supervised and Unsupervised Techniques for Real-World Applicationscited by 14
  8. 2022A super-polynomial quantum-classical separation for density modellingcited by 9
  9. 2025Double descent in quantum kernel methodscited by 9
  10. 2025Generative quantum advantage for classical and quantum problemscited by 9
  11. 2025A Primer on Quantum Machine Learningcited by 9
  12. 2022Generalization Metrics for Practical Quantum Advantage in Generative Modelscited by 8
  13. 2021Learnability of the output distributions of local quantum circuitscited by 7
  14. 2022Classical versus Quantum: comparing Tensor Network-based Quantum Circuits on LHC datacited by 7
  15. 2022Hyperparameter Importance of Quantum Neural Networks Across Small Datasetscited by 7
  16. 2024Quantum delegated and federated learning via quantum homomorphic encryptioncited by 7
  17. 2022Completely Quantum Neural Networkscited by 6
  18. 2022Power of Quantum Generative Learningcited by 6
  19. 2023Quantum Natural Policy Gradients: Towards Sample-Efficient Reinforcement Learningcited by 6
  20. 2023Classical Verification of Quantum Learningcited by 6
  21. 2023Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computationcited by 5
  22. 2024Arbitrary Polynomial Separations in Trainable Quantum Machine Learningcited by 5
  23. 2025Quantum computing and artificial intelligence: status and perspectivescited by 5
  24. 2021Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learningcited by 4
  25. 2023Advantage of Quantum Machine Learning from General Computational Advantagescited by 4
  26. 2025Towards efficient quantum algorithms for diffusion probabilistic modelscited by 4
  27. 2022Quantum-Aided Meta-Learning for Bayesian Binary Neural Networks via Born Machinescited by 3
  28. 2022A learning theory for quantum photonic processors and beyondcited by 3
  29. 2023Generative Invertible Quantum Neural Networkscited by 3
  30. 2025Generalization Bounds in Hybrid Quantum-Classical Machine Learning Modelscited by 3
  31. 2022Generalized quantum similarity learningcited by 2
  32. 2024Satellite image classification with neural quantum kernelscited by 2
  33. 2024An unconditional distribution learning advantage with shallow quantum circuitscited by 2
  34. 2025TabularQGAN: A quantum generative model for tabular data synthesiscited by 2
  35. 2026A PAC-Bayesian approach to generalization for quantum modelscited by 2
  36. 2024Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisationcited by 1
  37. 2025Limits of quantum generative models with classical sampling hardnesscited by 1
  38. 2026Optimal algorithmic complexity of inference in quantum kernel methodscited by 1

50 most cited of 57 All 57 (JSON)