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 and
TC0 under the uniform distribution. Our first result concerns the concept class
TC0 (resp.,
AC0), 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
TC0; and if there exists no
2O(d1/η)-time quantum algorithm to solve
RLWE with dimension
d=O(polylogn) (for every constant
η>2), then there exists no
O(nlogνn)-time quantum learning algorithm for
poly(n)-sized
AC0 circuits (for a constant
ν>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 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
TC20, i.e., depth-2
TC0 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
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ℓ-qubit gates, the algorithm learns the original circuit
U with high probability in
poly(n,2ℓd) time for every constant dimensional lattice. In particular, the algorithm is polynomial time as long as
ℓd=O(logn). In one dimension, this reaches the natural boundary suggested by pseudorandomness: pseudorandom states require
ℓ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=ω(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.
A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.
Approximate unitary designs reproduce the statistics of Haar-random unitaries to a given order and accuracy. Recent constructions realize such designs with logarithmic-depth circuits, enabling shallow measurement protocols for various quantum state-learning tasks while preserving performance. These results raise the question of whether approximate designs can replace exact designs more generally. We show that even exponentially small design error need not preserve the learning guarantees of exact designs. This motivates deriving learning guarantees directly from the measurement circuit structure. For observable estimation with classical shadows, we prove that logarithmic-depth two-layer Clifford circuits yield an unbiased estimator matching the global Clifford variance scaling for every state and Hermitian observable. Beyond observable estimation, this bound allows shallow measurements to retain global Clifford guarantees for other tasks, including setting-efficient tomography, mixed-state metrology, and stabilizer structure learning. We complement these statistical guarantees with a compact, exact tensor-network representation of the inverse shadow channel. When measurement bases are reused, approximate unitary designs of arbitrarily high order need not uniformly match the Haar variance in the many-shot limit. For the all-to-all random two-local circuits considered, doing so requires nearly linear depth. Together, our results reveal the capabilities and limitations of shallow quantum state learning, highlighting the distinction between approximating Haar randomness and reproducing its learning guarantees.
Recently, a polynomial time classical algorithm has been found for learning the shallow representation of a unitary
U acting on
n-qubits, by learning local inversions and then sewing them back together with ancilla qubits and SWAP gates. In this work, we bootstrap local inversion learning (LIL) to optimize quantum circuit depth by learning shallow representations for its sub-unitaries. We recursively cut circuits and apply the LIL algorithm to replace sub-circuits with their shallow representations, if it can be found by the algorithm. If not, we keep cutting until the optimization terminates, either by finding shallow representations or by reaching constant-depth sub-circuits. By replacing sub-circuits with their shallow representations, we hope to obtain some compression of the quantum circuit. Due to the binary search structure, the optimization algorithm has time complexity logarithmic in the depth of the original given circuit.
Learning quantum states from measurement data is a central problem in quantum information and computational complexity. In this work, we study the problem of learning to generate mixed states on a finite-dimensional lattice. Motivated by recent developments in mixed state phases of matter, we focus on arbitrary states in the trivial phase. A state belongs to the trivial phase if there exists a shallow preparation channel circuit under which local reversibility is preserved throughout the preparation. We prove that any mixed state in this class can be efficiently learned from measurement access alone. Specifically, given copies of an unknown trivial phase mixed state, our algorithm outputs a shallow local channel circuit that approximately generates this state in trace distance. The sample complexity and runtime are polynomial (or quasi-polynomial) in the number of qubits, assuming constant (or polylogarithmic) circuit depth and gate locality. Importantly, the learner is not given the original preparation circuit and relies only on its existence. Our results provide a structural foundation for quantum generative models based on shallow channel circuits. In the classical limit, our framework also inspires an efficient algorithm for classical diffusion models using only a polynomial overhead of training and generation.