# A super-polynomial quantum-classical separation for density modelling

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

## Key facts

- Cited by 9 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 26 Oct 2022.

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

- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Parameterized quantum circuits as machine learning models](https://mlsanity.com/paper/1906.07682/) (2019)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine](https://mlsanity.com/paper/1904.02214/) (2019)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [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, 9 of 9)

- [Understanding quantum machine learning also requires rethinking generalization](https://mlsanity.com/paper/2306.13461/) (2023)
- [Towards provably efficient quantum algorithms for large-scale machine-learning models](https://mlsanity.com/paper/2303.03428/) (2023)
- [Machine Learning for Anomaly Detection in Particle Physics](https://mlsanity.com/paper/2312.14190/) (2023)
- [Let Quantum Neural Networks Choose Their Own Frequencies](https://mlsanity.com/paper/2309.03279/) (2023)
- [Towards efficient quantum algorithms for diffusion probabilistic models](https://mlsanity.com/paper/2502.14252/) (2025)
- [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)
- [An unconditional distribution learning advantage with shallow quantum circuits](https://mlsanity.com/paper/2411.15548/) (2024)
- [Cautious optimism for deep parameterized quantum circuits](https://mlsanity.com/paper/2607.21409/) (2026)

## Abstract (arXiv)

Density modelling is the task of learning an unknown probability density function from samples, and is one of the central problems of unsupervised machine learning. In this work, we show that there exists a density modelling problem for which fault-tolerant quantum computers can offer a super-polynomial advantage over classical learning algorithms, given standard cryptographic assumptions. Along the way, we provide a variety of additional results and insights, of potential interest for proving future distribution learning separations between quantum and classical learning algorithms. Specifically, we (a) provide an overview of the relationships between hardness results in supervised learning and distribution learning, and (b) show that any weak pseudo-random function can be used to construct a classically hard density modelling problem. The latter result opens up the possibility of proving quantum-classical separations for density modelling based on weaker assumptions than those necessary for pseudo-random functions.