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:1903.02840 · SIAM Journal on Computing

Quantum Hardness of Learning Shallow Classical Circuits

Srinivasan Arunachalam, Alex B. Grilo, Aarthi Sundaram

Published Jan 1, 2021• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1137/20m1344202

Related papers

Quantum learning algorithms imply circuit lower bounds

Srinivasan Arunachalam, Alex B. Grilo, Tom Gur +2 more

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let $\mathfrak{C}$ be a class of polynomial-size concepts, and suppose that $\mathfrak{C}$ can be PAC-learned with membership queries under the uniform distribution with error $1/2 - γ$ by a time $T$ quantum algorithm. We prove that if $γ^2 \cdot T \ll 2^n/n$, then $\mathsf{BQE} \nsubseteq \mathfrak{C}$, where $\mathsf{BQE} = \mathsf{BQTIME}[2^{O(n)}]$ is an exponential-time analogue of $\mathsf{BQP}$. This result is optimal in both $γ$ and $T$, since it is not hard to learn any class $\mathfrak{C}$ of functions in (classical) time $T = 2^n$ (with no error), or in quantum time $T = \mathsf{poly}(n)$ with error at most $1/2 - Ω(2^{-n/2})$ via Fourier sampling. In other words, even a marginal improvement on these generic learning algorithms would lead to major consequences in complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and crucially, on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). Extending their approach to quantum learning algorithms turns out to create significant challenges. To achieve that, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.

arXiv:2012.01920•Dec 3, 2020•1 citation

Quantum learning algorithms imply circuit lower bounds

Srinivasan Arunachalam, Alex B. Grilo, Tom Gur +2 more

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let$\mathfrak{C}$be a class of polynomial-size concepts, and suppose that$\mathfrak{C}$can be PAC-learned with membership queries under the uniform distribution with error$1/2 -\gamma$by a time$T$quantum algorithm. We prove that if$\gamma^{2}\cdot T \ll 2^{n} /n$, then$\mathsf{BQE}\not\subset \mathfrak{C}$, where$\mathsf{BQE} = \mathsf{BQTIME}[2^{O(n)}]$is an exponential-time analogue of$\mathsf{BQP}$. This result is optimal in both$\gamma$and$T$, since it is not hard to learn any class$\mathfrak{C}$of functions in (classical) time$T=2^{n}$(with no error), or in quantum time$T= \mathsf{poly}(n)$with error at most$1/2-\Omega(2^{-n/2})$via Fourier sampling. In other words, even a marginal quantum speedup over these generic learning algorithms would lead to major consequences in complexity lower bounds. As a consequence, our result shows that the study of quantum learning speedups is intimately connected to fundamental open problems about algorithms, quantum computing, and complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). Extending their approach to quantum learning algorithms turns out to create significant challenges, since extracting computational hardness from a quantum computation is inherently more complicated. To achieve that, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.

Annual Symposium on Foundations of Computer Science•Feb 1, 2022•6 citations

Learnability of the output distributions of local quantum circuits

Marcel Hinsche, Marios Ioannou, Alexander Nietner +6 more

There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable in the statistical query model, i.e., when given query access to empirical expectation values of bounded functions over the sample space. This immediately implies the hardness, for both quantum and classical algorithms, of learning from statistical queries the output distributions of local quantum circuits using any gate set which includes the Clifford group. As many practical generative modelling algorithms use statistical queries -- including those for training quantum circuit Born machines -- our result is broadly applicable and strongly limits the possibility of a meaningful quantum advantage for learning the output distributions of local quantum circuits. As a positive result, we show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable by a classical learner. Our results are equally applicable to the problems of learning an algorithm for generating samples from the target distribution (generative modelling) and learning an algorithm for evaluating its probabilities (density modelling). They provide the first rigorous insights into the learnability of output distributions of local quantum circuits from the probabilistic modelling perspective.

arXiv:2110.05517•Oct 11, 2021•8 citations

Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure

Alexandru Gheorghiu

We construct a family of 2D-local constant-depth quantum circuits that output states whose entanglement entropy across a specified cut cannot be estimated in quantum polynomial time. As constant-depth quantum circuits can be learned from polynomially many quantum samples, our resulting pseudoentangled states are implicitly public-key and not pseudorandom. This separates pseudoentanglement from pseudorandomness in the shallow-circuit regime: the former is possible, while the latter is not. The construction is based on the quantum intractability of the Dense-Sparse Learning Parity with Noise problem introduced in [DJ25] and uses a bounded-fan-in, bounded-fan-out classical randomized encoding for linear maps $\mathbf{x} \mapsto \mathbf{Mx},$ which could be of independent interest. As applications, we obtain quantum hardness for the problem of learning the entanglement structure (across a fixed cut) of the ground-state of 1D and 2D local Hamiltonians. The 1D Hamiltonian has an inverse polynomial gap, whereas the 2D one has a constant gap. This complements the result of [BZZ24] that showed only factoring-based hardness for the 1D case, though achieving a volume versus area entanglement difference.

quant-pharXiv:2605.31448•Jun 1, 2026•0 citations

On the Sample Complexity of PAC Learning Quantum Process.

Kai-Min Chung, Han-Hsuan Lin

We generalize the PAC (probably approximately correct) learning model to the quantum world by generalizing the concepts from classical functions to quantum processes, defining the problem of \emph{PAC learning quantum process}, and study its sample complexity. In the problem of PAC learning quantum process, we want to learn an $\epsilon$-approximate of an unknown quantum process $c^*$ from a known finite concept class $C$ with probability $1-\delta$ using samples $\{(x_1,c^*(x_1)),(x_2,c^*(x_2)),\dots\}$, where $\{x_1,x_2, \dots\}$ are computational basis states sampled from an unknown distribution $D$ and $\{c^*(x_1),c^*(x_2),\dots\}$ are the (possibly mixed) quantum states outputted by $c^*$. The special case of PAC-learning quantum process under constant input reduces to a natural problem which we named as approximate state discrimination, where we are given copies of an unknown quantum state $c^*$ from an known finite set $C$, and we want to learn with probability $1-\delta$ an $\epsilon$-approximate of $c^*$ with as few copies of $c^*$ as possible. We show that the problem of PAC learning quantum process can be solved with $$O\left(\frac{\log|C| + \log(1/ \delta)} { \epsilon^2}\right)$$ samples when the outputs are pure states and $$O\left(\frac{\log^3 |C|(\log |C|+\log(1/ \delta))} { \epsilon^2}\right)$$ samples if the outputs can be mixed. Some implications of our results are that we can PAC-learn a polynomial sized quantum circuit in polynomial samples and approximate state discrimination can be solved in polynomial samples even when concept class size $|C|$ is exponential in the number of qubits, an exponentially improvement over a full state tomography.

•Oct 25, 2018•0 citations

An unconditional distribution learning advantage with shallow quantum circuits

Niklas Pirnay, Sofiène Jerbi, Jean‐Pierre Seifert +1 more

One of the core challenges of research in quantum computing is concerned with the question whether quantum advantages can be found for near-term quantum circuits that have implications for practical applications. Motivated by this mindset, in this work, we prove an unconditional quantum advantage in the probably approximately correct (PAC) distribution learning framework with shallow quantum circuit hypotheses. We identify a meaningful generative distribution learning problem where constant-depth quantum circuits using one and two qubit gates (QNC^0) are superior compared to constant-depth bounded fan-in classical circuits (NC^0) as a choice for hypothesis classes. We hence prove a PAC distribution learning separation for shallow quantum circuits over shallow classical circuits. We do so by building on recent results by Bene Watts and Parham on unconditional quantum advantages for sampling tasks with shallow circuits, which we technically uplift to a hyperplane learning problem, identifying non-local correlations as the origin of the quantum advantage.

arXiv:2411.15548•Nov 23, 2024•0 citations
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 establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let C\mathfrak{C}C be a class of polynomial-size concepts, and suppose that C\mathfrak{C}C can be PAC-learned with membership queries under the uniform distribution with error 1/2−γ1/2 - γ1/2−γ by a time TTT quantum algorithm. We prove that if γ2⋅T≪2n/nγ^2 \cdot T \ll 2^n/nγ2⋅T≪2n/n, then BQE⊈C\mathsf{BQE} \nsubseteq \mathfrak{C}BQE⊈C, where BQE=BQTIME[2O(n)]\mathsf{BQE} = \mathsf{BQTIME}[2^{O(n)}]BQE=BQTIME[2O(n)] is an exponential-time analogue of BQP\mathsf{BQP}BQP. This result is optimal in both γγγ and TTT, since it is not hard to learn any class C\mathfrak{C}C of functions in (classical) time T=2nT = 2^nT=2n (with no error), or in quantum time T=poly(n)T = \mathsf{poly}(n)T=poly(n) with error at most 1/2−Ω(2−n/2)1/2 - Ω(2^{-n/2})1/2−Ω(2−n/2) via Fourier sampling. In other words, even a marginal improvement on these generic learning algorithms would lead to major consequences in complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and crucially, on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). Extending their approach to quantum learning algorithms turns out to create significant challenges. To achieve that, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, letC\mathfrak{C}Cbe a class of polynomial-size concepts, and suppose thatC\mathfrak{C}Ccan be PAC-learned with membership queries under the uniform distribution with error1/2−γ1/2 -\gamma1/2−γby a timeTTTquantum algorithm. We prove that ifγ2⋅T≪2n/n\gamma^{2}\cdot T \ll 2^{n} /nγ2⋅T≪2n/n, thenBQE⊄C\mathsf{BQE}\not\subset \mathfrak{C}BQE⊂C, whereBQE=BQTIME[2O(n)]\mathsf{BQE} = \mathsf{BQTIME}[2^{O(n)}]BQE=BQTIME[2O(n)]is an exponential-time analogue ofBQP\mathsf{BQP}BQP. This result is optimal in bothγ\gammaγandTTT, since it is not hard to learn any classC\mathfrak{C}Cof functions in (classical) timeT=2nT=2^{n}T=2n(with no error), or in quantum timeT=poly(n)T= \mathsf{poly}(n)T=poly(n)with error at most1/2−Ω(2−n/2)1/2-\Omega(2^{-n/2})1/2−Ω(2−n/2)via Fourier sampling. In other words, even a marginal quantum speedup over these generic learning algorithms would lead to major consequences in complexity lower bounds. As a consequence, our result shows that the study of quantum learning speedups is intimately connected to fundamental open problems about algorithms, quantum computing, and complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). Extending their approach to quantum learning algorithms turns out to create significant challenges, since extracting computational hardness from a quantum computation is inherently more complicated. To achieve that, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.
There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable in the statistical query model, i.e., when given query access to empirical expectation values of bounded functions over the sample space. This immediately implies the hardness, for both quantum and classical algorithms, of learning from statistical queries the output distributions of local quantum circuits using any gate set which includes the Clifford group. As many practical generative modelling algorithms use statistical queries -- including those for training quantum circuit Born machines -- our result is broadly applicable and strongly limits the possibility of a meaningful quantum advantage for learning the output distributions of local quantum circuits. As a positive result, we show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable by a classical learner. Our results are equally applicable to the problems of learning an algorithm for generating samples from the target distribution (generative modelling) and learning an algorithm for evaluating its probabilities (density modelling). They provide the first rigorous insights into the learnability of output distributions of local quantum circuits from the probabilistic modelling perspective.
We construct a family of 2D-local constant-depth quantum circuits that output states whose entanglement entropy across a specified cut cannot be estimated in quantum polynomial time. As constant-depth quantum circuits can be learned from polynomially many quantum samples, our resulting pseudoentangled states are implicitly public-key and not pseudorandom. This separates pseudoentanglement from pseudorandomness in the shallow-circuit regime: the former is possible, while the latter is not. The construction is based on the quantum intractability of the Dense-Sparse Learning Parity with Noise problem introduced in [DJ25] and uses a bounded-fan-in, bounded-fan-out classical randomized encoding for linear maps x↦Mx,\mathbf{x} \mapsto \mathbf{Mx},x↦Mx, which could be of independent interest. As applications, we obtain quantum hardness for the problem of learning the entanglement structure (across a fixed cut) of the ground-state of 1D and 2D local Hamiltonians. The 1D Hamiltonian has an inverse polynomial gap, whereas the 2D one has a constant gap. This complements the result of [BZZ24] that showed only factoring-based hardness for the 1D case, though achieving a volume versus area entanglement difference.
We generalize the PAC (probably approximately correct) learning model to the quantum world by generalizing the concepts from classical functions to quantum processes, defining the problem of \emph{PAC learning quantum process}, and study its sample complexity. In the problem of PAC learning quantum process, we want to learn an ϵ\epsilonϵ-approximate of an unknown quantum process c∗c^*c∗ from a known finite concept class CCC with probability 1−δ1-\delta1−δ using samples {(x1,c∗(x1)),(x2,c∗(x2)),… }\{(x_1,c^*(x_1)),(x_2,c^*(x_2)),\dots\}{(x1​,c∗(x1​)),(x2​,c∗(x2​)),…}, where {x1,x2,… }\{x_1,x_2, \dots\}{x1​,x2​,…} are computational basis states sampled from an unknown distribution DDD and {c∗(x1),c∗(x2),… }\{c^*(x_1),c^*(x_2),\dots\}{c∗(x1​),c∗(x2​),…} are the (possibly mixed) quantum states outputted by c∗c^*c∗. The special case of PAC-learning quantum process under constant input reduces to a natural problem which we named as approximate state discrimination, where we are given copies of an unknown quantum state c∗c^*c∗ from an known finite set CCC, and we want to learn with probability 1−δ1-\delta1−δ an ϵ\epsilonϵ-approximate of c∗c^*c∗ with as few copies of c∗c^*c∗ as possible. We show that the problem of PAC learning quantum process can be solved with O(log⁡∣C∣+log⁡(1/δ)ϵ2)O\left(\frac{\log|C| + \log(1/ \delta)} { \epsilon^2}\right)O(ϵ2log∣C∣+log(1/δ)​) samples when the outputs are pure states and O(log⁡3∣C∣(log⁡∣C∣+log⁡(1/δ))ϵ2)O\left(\frac{\log^3 |C|(\log |C|+\log(1/ \delta))} { \epsilon^2}\right)O(ϵ2log3∣C∣(log∣C∣+log(1/δ))​) samples if the outputs can be mixed. Some implications of our results are that we can PAC-learn a polynomial sized quantum circuit in polynomial samples and approximate state discrimination can be solved in polynomial samples even when concept class size ∣C∣|C|∣C∣ is exponential in the number of qubits, an exponentially improvement over a full state tomography.
One of the core challenges of research in quantum computing is concerned with the question whether quantum advantages can be found for near-term quantum circuits that have implications for practical applications. Motivated by this mindset, in this work, we prove an unconditional quantum advantage in the probably approximately correct (PAC) distribution learning framework with shallow quantum circuit hypotheses. We identify a meaningful generative distribution learning problem where constant-depth quantum circuits using one and two qubit gates (QNC^0) are superior compared to constant-depth bounded fan-in classical circuits (NC^0) as a choice for hypothesis classes. We hence prove a PAC distribution learning separation for shallow quantum circuits over shallow classical circuits. We do so by building on recent results by Bene Watts and Parham on unconditional quantum advantages for sampling tasks with shallow circuits, which we technically uplift to a hyperplane learning problem, identifying non-local correlations as the origin of the quantum advantage.