# On the average-case complexity of learning output distributions of quantum circuits

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 76 references that are in the map.
- First posted on arXiv 9 May 2023.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [The Loss Surfaces of Multilayer Networks](https://mlsanity.com/paper/1412.0233/) (2014)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine](https://mlsanity.com/paper/1904.02214/) (2019)
- [SGD Learns the Conjugate Kernel Class of the Network](https://mlsanity.com/paper/1702.08503/) (2017)
- [Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization](https://mlsanity.com/paper/1512.09170/) (2015)
- [A General Characterization of the Statistical Query Complexity](https://mlsanity.com/paper/1608.02198/) (2016)
- [Poly-time universality and limitations of deep learning](https://mlsanity.com/paper/2001.02992/) (2020)
- [A Deep Conditioning Treatment of Neural Networks](https://mlsanity.com/paper/2002.01523/) (2020)
- [Hardness of Learning Neural Networks with Natural Weights](https://mlsanity.com/paper/2006.03177/) (2020)
- [Provable Bounds for Learning Some Deep Representations](https://mlsanity.com/paper/1310.6343/) (2013)
- [On the Complexity of Random Satisfiability Problems with Planted Solutions](https://mlsanity.com/paper/1311.4821/) (2013)
- [A Survey of Quantum Learning Theory](https://mlsanity.com/paper/1701.06806/) (2017)
- [Learning (Very) Simple Generative Models Is Hard](https://mlsanity.com/paper/2205.16003/) (2022)
- [Quantum hardness of learning shallow classical circuits](https://mlsanity.com/paper/1903.02840/) (2019)

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

- [Barren Plateaus in Variational Quantum Computing](https://mlsanity.com/paper/2405.00781/) (2024)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [Learning unitaries with quantum statistical queries](https://mlsanity.com/paper/2310.02254/) (2023)
- [Learning Quantum Processes with Quantum Statistical Queries](https://mlsanity.com/paper/2310.02075/) (2023)
- [Quantum advantage for learning shallow neural networks with natural data distributions](https://mlsanity.com/paper/2503.20879/) (2025)
- [Learning and Generating Mixed States Prepared by Shallow Channel Circuits](https://mlsanity.com/paper/2604.01197/) (2026)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)

## Abstract (arXiv)

In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on n qubits of depth d, we show three main results: - At super logarithmic circuit depth d=ω(log(n)), any learning algorithm requires super polynomially many queries to achieve a constant probability of success over the randomly drawn instance. - There exists a d=O(n), such that any learning algorithm requires Omega(2n) queries to achieve a O(2-n) probability of success over the randomly drawn instance. - At infinite circuit depth d→∞, any learning algorithm requires 2^2Omega(n) many queries to achieve a 2^-2Omega(n) probability of success over the randomly drawn instance. As an auxiliary result of independent interest, we show that the output distribution of a brickwork random quantum circuit is constantly far from any fixed distribution in total variation distance with probability 1-O(2-n), which confirms a variant of a conjecture by Aaronson and Chen.