Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2305.05765 · Quantum

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

Alexander Nietner, Marios Ioannou, Ryan Sweke, Richard Kueng, Jens Eisert, Marcel Hinsche, Jonas Haferkamp

Published Oct 13, 2025• 26 citations
arXivHTMLPDF

Abstract

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 Ω(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 22Ω(n) many queries to achieve a 2−2Ω(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.

DOI
10.22331/q-2025-10-13-1883

Related papers

One T Gate Makes Distribution Learning Hard

Marcel Hinsche, Marios Ioannou, Alexander Nietner +6 more

The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits are of central importance in both quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we extensively characterize the learnability of output distributions of local quantum circuits. Firstly, we contrast learnability with simulatability by showing that Clifford circuit output distributions are efficiently learnable, while the injection of a single T gate renders the density modeling task hard for any depth d=n^{Ω(1)}. We further show that the task of generative modeling universal quantum circuits at any depth d=n^{Ω(1)} is hard for any learning algorithm, classical or quantum, and that for statistical query algorithms, even depth d=ω[log(n)] Clifford circuits are hard to learn. Our results show that one cannot use the output distributions of local quantum circuits to provide a separation between the power of quantum and classical generative modeling algorithms, and therefore provide evidence against quantum advantages for practically relevant probabilistic modeling tasks.

arXiv:2110.05517•Physical Review Letters•Jun 13, 2023•65 citations

Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness

Chirag Wadhwa, Mina Doosti

In this work, we study the learnability of quantum circuits in the near term. We demonstrate the natural robustness of quantum statistical queries for learning quantum processes, motivating their use as a theoretical tool for near-term learning problems. We adapt a learning algorithm for constant-depth quantum circuits to the quantum statistical query setting, and show that such circuits can be learned in our setting with only a linear overhead in the query complexity. We prove average-case quantum statistical query lower bounds for learning, within diamond distance, random quantum circuits with depth at least logarithmic and at most linear in the system size. Finally, we prove that pseudorandom unitaries (PRUs) cannot be constructed using circuits of constant depth by constructing an efficient distinguisher using existing learning algorithms. To show the correctness of our distinguisher, we prove a new variation of the quantum no free lunch theorem.

arXiv:2405.12085•May 20, 2024•3 citations

On the average-case complexity of learning states from the circular and Gaussian ensembles

Maxwell West

Studying the complexity of states sampled from various ensembles is a central component of quantum information theory. In this work we establish the average-case hardness of learning, in the statistical query model, the Born distributions of states sampled uniformly from the compact symmetric spaces of type AI, AII, and DIII. These ensembles correspond in various senses to the so called circular and (fermionic) Gaussian ensembles. This finding complements analogous recent results for states sampled from the classical compact groups. On the technical side, we employ a somewhat unconventional approach to integrating over the compact groups which may be of some independent interest. For example, our approach allows us to exactly evaluate the total variation distances between the output distributions of Haar random unitary and orthogonal circuits and the constant distribution, which were previously known only approximately.

quant-pharXiv:2601.10197•Jan 16, 2026•3 citations

Local random quantum circuits converge to the Porter-Thomas distribution in polynomial depth

Aniruddha Sen, Nicholas Hunter-Jones

Porter-Thomas statistics are a characteristic feature of the output distribution of random quantum states and, more broadly, chaotic quantum many-body systems. Convergence to Porter-Thomas plays a central role in random circuit sampling and experimental demonstrations of quantum advantage, where the output statistics of low-depth random quantum circuits are expected to be approximately Porter-Thomas, despite the absence of a rigorous proof of convergence. We show that the output distribution of polynomial-depth brickwork random circuits converges inverse-polynomially in total variation distance to the Porter-Thomas distribution. Specifically, consider the output probability distribution over a fixed bitstring of a local random quantum circuit, constructed from nearest-neighbor Haar random gates. Then, for any $m \geq 0$, the distribution corresponding to circuits of depth $O(n^{2m+1}\log(n))$ is at most $O(1/n^m)$ far in total variation distance from the Porter-Thomas distribution. Our proof uses moment bounds from approximate designs, analytic estimates for characteristic functions, and a local anticoncentration property for inverse moments.

quant-pharXiv:2610.02125•Oct 2, 2026•0 citations

Quantum Hardness of Learning Shallow Classical Circuits

Srinivasan Arunachalam, Alex B. Grilo, Aarthi Sundaram

In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1. Hardness of PAC learning ${AC}^0$ and ${TC}^0$ under the uniform distribution. Our first result concerns the concept class ${TC}^0$ (resp., ${AC}^0$), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., ${AND}, {OR}, {NOT}$ gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (${RLWE}$) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for ${TC}^0$; and if there exists no $2^{O(d^{1/\eta})}$-time quantum algorithm to solve ${RLWE}$ with dimension $d = O(polylog n)$ (for every constant $\eta > 2$), then there exists no $O(n^{ \log^{\nu} n} )$-time quantum learning algorithm for $poly(n)$-sized ${AC}^0$ circuits (for a constant $\nu>0$), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning ${TC}^0_2$ in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the ${LWE}$ problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class ${TC}^0_2$, i.e., depth-2 ${TC}^0$ circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.

arXiv:1903.02840•SIAM Journal on Computing•Jan 1, 2021•24 citations

Learning Random Quantum Circuits and the Emergence of Pseudorandomness

Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha

We give an efficient algorithm for learning $k$-dimensional brickwork random quantum circuits using only copies of the output state obtained by applying $U$ to the all-zero input. For a depth-$d$ circuit on $n$ sites with random $2\ell$-qubit gates, the algorithm learns the original circuit $U$ with high probability in $\text{poly}(n,2^{\ell d})$ time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as $\ell d = O(\log n)$. In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require $\ell d=ω(\log n)$, and structured cryptographic constructions suggest that this scale may be achievable from above. In higher dimensions, it remains plausible that the same $\ell d=ω(\log n)$ scale remains the threshold for ancilla-free pseudorandomness, and our results help clarify the conditions under which pseudorandomness can arise in this setting. The main idea behind our algorithm is a local correlation criterion that identifies gates in the final layer without learning their entire backward light cones, avoiding a bottleneck in the previous approaches. A key technical ingredient is a Carbery-Wright type anticoncentration inequality for low-degree polynomials of Haar random unitaries whose small-ball exponent is independent of the matrix dimension. The dimension-independent exponent is crucial for handling gates of growing locality. This anticoncentration result may also be of independent interest.

quant-pharXiv:2609.39821•Oct 1, 2026•0 citations
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 Ω(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 22Ω(n) many queries to achieve a 2−2Ω(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.
The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits are of central importance in both quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we extensively characterize the learnability of output distributions of local quantum circuits. Firstly, we contrast learnability with simulatability by showing that Clifford circuit output distributions are efficiently learnable, while the injection of a single T gate renders the density modeling task hard for any depth d=n^{Ω(1)}. We further show that the task of generative modeling universal quantum circuits at any depth d=n^{Ω(1)} is hard for any learning algorithm, classical or quantum, and that for statistical query algorithms, even depth d=ω[log(n)] Clifford circuits are hard to learn. Our results show that one cannot use the output distributions of local quantum circuits to provide a separation between the power of quantum and classical generative modeling algorithms, and therefore provide evidence against quantum advantages for practically relevant probabilistic modeling tasks.
In this work, we study the learnability of quantum circuits in the near term. We demonstrate the natural robustness of quantum statistical queries for learning quantum processes, motivating their use as a theoretical tool for near-term learning problems. We adapt a learning algorithm for constant-depth quantum circuits to the quantum statistical query setting, and show that such circuits can be learned in our setting with only a linear overhead in the query complexity. We prove average-case quantum statistical query lower bounds for learning, within diamond distance, random quantum circuits with depth at least logarithmic and at most linear in the system size. Finally, we prove that pseudorandom unitaries (PRUs) cannot be constructed using circuits of constant depth by constructing an efficient distinguisher using existing learning algorithms. To show the correctness of our distinguisher, we prove a new variation of the quantum no free lunch theorem.
Studying the complexity of states sampled from various ensembles is a central component of quantum information theory. In this work we establish the average-case hardness of learning, in the statistical query model, the Born distributions of states sampled uniformly from the compact symmetric spaces of type AI, AII, and DIII. These ensembles correspond in various senses to the so called circular and (fermionic) Gaussian ensembles. This finding complements analogous recent results for states sampled from the classical compact groups. On the technical side, we employ a somewhat unconventional approach to integrating over the compact groups which may be of some independent interest. For example, our approach allows us to exactly evaluate the total variation distances between the output distributions of Haar random unitary and orthogonal circuits and the constant distribution, which were previously known only approximately.
Porter-Thomas statistics are a characteristic feature of the output distribution of random quantum states and, more broadly, chaotic quantum many-body systems. Convergence to Porter-Thomas plays a central role in random circuit sampling and experimental demonstrations of quantum advantage, where the output statistics of low-depth random quantum circuits are expected to be approximately Porter-Thomas, despite the absence of a rigorous proof of convergence. We show that the output distribution of polynomial-depth brickwork random circuits converges inverse-polynomially in total variation distance to the Porter-Thomas distribution. Specifically, consider the output probability distribution over a fixed bitstring of a local random quantum circuit, constructed from nearest-neighbor Haar random gates. Then, for any m≥0m \geq 0m≥0, the distribution corresponding to circuits of depth O(n2m+1log⁡(n))O(n^{2m+1}\log(n))O(n2m+1log(n)) is at most O(1/nm)O(1/n^m)O(1/nm) far in total variation distance from the Porter-Thomas distribution. Our proof uses moment bounds from approximate designs, analytic estimates for characteristic functions, and a local anticoncentration property for inverse moments.
In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1. Hardness of PAC learning AC0{AC}^0AC0 and TC0{TC}^0TC0 under the uniform distribution. Our first result concerns the concept class TC0{TC}^0TC0 (resp., AC0{AC}^0AC0), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., AND,OR,NOT{AND}, {OR}, {NOT}AND,OR,NOT gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (RLWE{RLWE}RLWE) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for TC0{TC}^0TC0; and if there exists no 2O(d1/η)2^{O(d^{1/\eta})}2O(d1/η)-time quantum algorithm to solve RLWE{RLWE}RLWE with dimension d=O(polylogn)d = O(polylog n)d=O(polylogn) (for every constant η>2\eta > 2η>2), then there exists no O(nlog⁡νn)O(n^{ \log^{\nu} n} )O(nlogνn)-time quantum learning algorithm for poly(n)poly(n)poly(n)-sized AC0{AC}^0AC0 circuits (for a constant ν>0\nu>0ν>0), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning TC20{TC}^0_2TC20​ in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the LWE{LWE}LWE problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class TC20{TC}^0_2TC20​, i.e., depth-2 TC0{TC}^0TC0 circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.
We give an efficient algorithm for learning kkk-dimensional brickwork random quantum circuits using only copies of the output state obtained by applying UUU to the all-zero input. For a depth-ddd circuit on nnn sites with random 2ℓ2\ell2ℓ-qubit gates, the algorithm learns the original circuit UUU with high probability in poly(n,2ℓd)\text{poly}(n,2^{\ell d})poly(n,2ℓd) time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as ℓd=O(log⁡n)\ell d = O(\log n)ℓd=O(logn). In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require ℓd=ω(log⁡n)\ell d=ω(\log n)ℓd=ω(logn), and structured cryptographic constructions suggest that this scale may be achievable from above. In higher dimensions, it remains plausible that the same ℓd=ω(log⁡n)\ell d=ω(\log n)ℓd=ω(logn) scale remains the threshold for ancilla-free pseudorandomness, and our results help clarify the conditions under which pseudorandomness can arise in this setting. The main idea behind our algorithm is a local correlation criterion that identifies gates in the final layer without learning their entire backward light cones, avoiding a bottleneck in the previous approaches. A key technical ingredient is a Carbery-Wright type anticoncentration inequality for low-degree polynomials of Haar random unitaries whose small-ball exponent is independent of the matrix dimension. The dimension-independent exponent is crucial for handling gates of growing locality. This anticoncentration result may also be of independent interest.