arXiv:2405.10242

Quantum State Learning Implies Circuit Lower Bounds

Nai-Hui Chia, Daniel Liang, Fang Song

Published May 16, 2024• 0 citations

Abstract

We establish connections between state tomography, pseudorandomness, quantum state synthesis, and circuit lower bounds. In particular, let $\mathfrak{C}$ be a family of non-uniform quantum circuits of polynomial size and suppose that there exists an algorithm that, given copies of $|ψ\rangle$, distinguishes whether $|ψ\rangle$ is produced by $\mathfrak{C}$ or is Haar random, promised one of these is the case. For arbitrary fixed constant $c$, we show that if the algorithm uses at most $O(2^{n^c})$ time and $2^{n^{0.99}}$ samples then $\mathsf{stateBQE} \not\subset \mathsf{state}\mathfrak{C}$. Here $\mathsf{stateBQE} := \mathsf{stateBQTIME}[2^{O(n)}]$ and $\mathsf{state}\mathfrak{C}$ are state synthesis complexity classes as introduced by Rosenthal and Yuen (ITCS 2022), which capture problems with classical inputs but quantum output. Note that efficient tomography implies a similarly efficient distinguishing algorithm against Haar random states, even for nearly exponential-time algorithms. Because every state produced by a polynomial-size circuit can be learned with $2^{O(n)}$ samples and time, or $O(n^{ω(1)})$ samples and $2^{O(n^{ω(1)})}$ time, we show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis. Finally, a slight modification of our proof shows that distinguishing algorithms for quantum states can imply circuit lower bounds for decision problems as well. This help sheds light on why time-efficient tomography algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work parallels results by Arunachalam et al. (FOCS 2021) that revealed a similar connection between quantum learning of Boolean functions and circuit lower bounds for classical circuit classes, but modified for the purposes of state tomography and state synthesis.

DOI: 10.48550/arxiv.2405.10242

Related papers

Quantum learning algorithms imply circuit lower bounds

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

Annual Symposium on Foundations of Computer ScienceFeb 1, 20226 citations

Quantum learning algorithms imply circuit lower bounds

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

arXiv:2012.01920Dec 3, 20201 citation

Learning Random Quantum Circuits and the Emergence of Pseudorandomness

Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha

quant-pharXiv:2609.39821Oct 1, 20260 citations

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits

Jonathan Allcock, João Fernando Doriguello, Gábor Ivanyos +1 more

arXiv:2405.06357May 10, 20240 citations

Quantum Hardness of Learning Shallow Classical Circuits

Srinivasan Arunachalam, Alex B. Grilo, Aarthi Sundaram

arXiv:1903.02840SIAM Journal on ComputingJan 1, 202111 citations

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

Alexandru Gheorghiu

quant-pharXiv:2605.31448Jun 1, 20260 citations

arXiv:2405.10242

Quantum State Learning Implies Circuit Lower Bounds

Nai-Hui Chia, Daniel Liang, Fang Song

Published May 16, 2024• 0 citations

arXiv HTML PDF

Abstract

We establish connections between state tomography, pseudorandomness, quantum state synthesis, and circuit lower bounds. In particular, let

\mathfrak{C}

be a family of non-uniform quantum circuits of polynomial size and suppose that there exists an algorithm that, given copies of

|ψ\rangle

, distinguishes whether

|ψ\rangle

is produced by

\mathfrak{C}

or is Haar random, promised one of these is the case. For arbitrary fixed constant

c

, we show that if the algorithm uses at most

O(2^{n^c})

time and

2^{n^{0.99}}

samples then

\mathsf{stateBQE} \not\subset \mathsf{state}\mathfrak{C}

. Here

\mathsf{stateBQE} := \mathsf{stateBQTIME}[2^{O(n)}]

and

\mathsf{state}\mathfrak{C}

are state synthesis complexity classes as introduced by Rosenthal and Yuen (ITCS 2022), which capture problems with classical inputs but quantum output. Note that efficient tomography implies a similarly efficient distinguishing algorithm against Haar random states, even for nearly exponential-time algorithms. Because every state produced by a polynomial-size circuit can be learned with

2^{O(n)}

samples and time, or

O(n^{ω(1)})

samples and

2^{O(n^{ω(1)})}

time, we show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis. Finally, a slight modification of our proof shows that distinguishing algorithms for quantum states can imply circuit lower bounds for decision problems as well. This help sheds light on why time-efficient tomography algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work parallels results by Arunachalam et al. (FOCS 2021) that revealed a similar connection between quantum learning of Boolean functions and circuit lower bounds for classical circuit classes, but modified for the purposes of state tomography and state synthesis.

DOI: 10.48550/arxiv.2405.10242

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 -\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.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 ScienceFeb 1, 20226 citations

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.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.01920Dec 3, 20201 citation

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.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.39821Oct 1, 20260 citations

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits

Jonathan Allcock, João Fernando Doriguello, Gábor Ivanyos +1 more

Bell sampling is a simple yet powerful measurement primitive that has recently attracted a lot of attention, and has proven to be a valuable tool in studying stabiliser states. Unfortunately, however, it is known that Bell sampling fails when used on qu\emph{d}its of dimension $d>2$ . In this paper, we explore and quantify the limitations of Bell sampling on qudits, and propose new quantum algorithms to circumvent the use of Bell sampling in solving two important problems: learning stabiliser states and providing pseudorandomness lower bounds on qudits. More specifically, as our first result, we characterise the output distribution corresponding to Bell sampling on copies of a stabiliser state and show that the output can be uniformly random, and hence reveal no information. As our second result, for $d=p$ prime we devise a quantum algorithm to identify an unknown stabiliser state in $(\mathbb{C}^p)^{\otimes n}$ that uses $O(n)$ copies of the input state and runs in time $O(n^4)$ . As our third result, we provide a quantum algorithm that efficiently distinguishes a Haar-random state from a state with non-negligible stabiliser fidelity. As a corollary, any Clifford circuit on qudits of dimension $d$ using $O(\log{n}/\log{d})$ auxiliary non-Clifford single-qudit gates cannot prepare computationally pseudorandom quantum states.Bell sampling is a simple yet powerful measurement primitive that has recently attracted a lot of attention, and has proven to be a valuable tool in studying stabiliser states. Unfortunately, however, it is known that Bell sampling fails when used on qu\emph{d}its of dimension $d>2$. In this paper, we explore and quantify the limitations of Bell sampling on qudits, and propose new quantum algorithms to circumvent the use of Bell sampling in solving two important problems: learning stabiliser states and providing pseudorandomness lower bounds on qudits. More specifically, as our first result, we characterise the output distribution corresponding to Bell sampling on copies of a stabiliser state and show that the output can be uniformly random, and hence reveal no information. As our second result, for $d=p$ prime we devise a quantum algorithm to identify an unknown stabiliser state in $(\mathbb{C}^p)^{\otimes n}$ that uses $O(n)$ copies of the input state and runs in time $O(n^4)$. As our third result, we provide a quantum algorithm that efficiently distinguishes a Haar-random state from a state with non-negligible stabiliser fidelity. As a corollary, any Clifford circuit on qudits of dimension $d$ using $O(\log{n}/\log{d})$ auxiliary non-Clifford single-qudit gates cannot prepare computationally pseudorandom quantum states.

arXiv:2405.06357May 10, 20240 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.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.02840SIAM Journal on ComputingJan 1, 202111 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.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.31448Jun 1, 20260 citations

We establish connections between state tomography, pseudorandomness, quantum state synthesis, and circuit lower bounds. In particular, let

\mathfrak{C}

be a family of non-uniform quantum circuits of polynomial size and suppose that there exists an algorithm that, given copies of

|ψ\rangle

, distinguishes whether

|ψ\rangle

is produced by

\mathfrak{C}

or is Haar random, promised one of these is the case. For arbitrary fixed constant

c

, we show that if the algorithm uses at most

O(2^{n^c})

time and

2^{n^{0.99}}

samples then

\mathsf{stateBQE} \not\subset \mathsf{state}\mathfrak{C}

. Here

\mathsf{stateBQE} := \mathsf{stateBQTIME}[2^{O(n)}]

and

\mathsf{state}\mathfrak{C}

2^{O(n)}

samples and time, or

O(n^{ω(1)})

samples and

2^{O(n^{ω(1)})}

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.

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.

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.

d>2

. In this paper, we explore and quantify the limitations of Bell sampling on qudits, and propose new quantum algorithms to circumvent the use of Bell sampling in solving two important problems: learning stabiliser states and providing pseudorandomness lower bounds on qudits. More specifically, as our first result, we characterise the output distribution corresponding to Bell sampling on copies of a stabiliser state and show that the output can be uniformly random, and hence reveal no information. As our second result, for

d=p

prime we devise a quantum algorithm to identify an unknown stabiliser state in

(\mathbb{C}^p)^{\otimes n}

that uses

O(n)

copies of the input state and runs in time

O(n^4)

. As our third result, we provide a quantum algorithm that efficiently distinguishes a Haar-random state from a state with non-negligible stabiliser fidelity. As a corollary, any Clifford circuit on qudits of dimension

d

using

O(\log{n}/\log{d})

auxiliary non-Clifford single-qudit gates cannot prepare computationally pseudorandom quantum states.

{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.

\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.