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:2609.39821

Learning Random Quantum Circuits and the Emergence of Pseudorandomness

Srinivasan Arunachalam, Qizhao Huang, Makrand Sinha

quant-phcs.DSSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper asks when local random quantum circuits can be reconstructed from copies of a single output state, and how learnability constrains pseudorandomness. It considers depth-$d$ brickwork circuits on $n$ sites of a fixed-dimensional lattice, with $\ell$ qubits per site and two-site gates. The learning model uses a public set of $M=64n^2d^2/\delta^2$ independently Haar-sampled, finite-precision gates; unknown circuit locations receive uniformly random labels from this set. For fixed lattice dimension $k$ and $d\leq0.01n^{1/k}$, the algorithm exactly recovers the gate labels from copies of $U|0\rangle^{\otimes n\ell}$ in sample and time complexity $\operatorname{poly}_k(n,d,\delta^{-1})2^{O_k(\ell d)}$, with high probability over the gateset, circuit and measurements. This is polynomial when $\ell d=O(\log n)$. It peels off layers by testing candidate inverse gates: the correct inverse eliminates correlations between selected output sites, while incorrect candidates leave a detectable correlation gap. The analysis constructs Bell-pair routing witnesses involving only $O_k(d)$ gates, avoiding reconstruction of full lightcones. A technical ingredient is a Haar-unitary small-ball bound for degree-$s$ polynomials: $\Pr[|P(U)|\leq\varepsilon\|P\|_\infty]\leq64m^2\varepsilon^{1/(24\pi s)}$. Its exponent is independent of matrix dimension; the proof combines Weyl integration, interpolation and a univariate Remez inequality. Exact recovery is restricted to the specified discrete public-gateset model, rather than unrestricted continuous Haar gates. The paper does not establish pseudorandomness above the learning regime. The scale $\ell d=\omega(\log n)$ is necessary for one-dimensional pseudorandom states; whether it marks an ancilla-free threshold in higher dimensions remains open.

Little sign of AI-generated textAI use disclosedStrong assumptions
The main idea for proving the improved anticoncentration bound was provided by an LLM.

Central claim may not hold: The abstract claims recovery of the original Haar-random circuit without stating the essential known finite-codebook assumption; without that side information, exact original-circuit recovery is not identifiable even at depth one. The abstract omits the theorem's restriction d ≤ 0.01 n^(1/k), although this restriction is asymptotically automatic in the highlighted ℓd = O(log n) regime.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits

Bill Fefferman, Ghosh, Soumik, Zhan, Wei

We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an $\varepsilon$ range is at most a polynomial in $\varepsilon$. Using it, we show that the scrambling speed of a random quantum circuit is lower bounded: Namely, every input qubit has an influence that is at least inverse exponential in depth, on any output qubit touched by its lightcone. Our result on scrambling speed works with high probability over the choice of a circuit from an ensemble, as opposed to just working in expectation. As an application, we give the first polynomial-time algorithm for learning log-depth random quantum circuits with Haar random gates up to polynomially small diamond distance, given oracle access to the circuit. Other applications of this new scrambling speed lower bound include: $\bullet$ An optimal $Ω(\log \varepsilon^{-1})$ depth lower bound for $\varepsilon$-approximate unitary designs on any circuit architecture; $\bullet$ A polynomial-time quantum algorithm that computes the depth of a bounded-depth circuit, given oracle access to the circuit. Our learning and depth-testing algorithms apply to architectures defined over any geometric dimension, and can be generalized to a wide class of architectures with good lightcone properties.

arXiv:2407.19561•Leibniz international proceedings in informatics•Jul 28, 2024•20 citations

Random Unitaries in Constant (Quantum) Time

Ben Foxman, Natalie Parham, Francisca Vasconcelos +1 more

Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using $Θ(\log \log n)$-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of $\textit{constant-time}$ quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class $\mathsf{QAC}^0$. Finally, our results suggest a new approach towards proving that PARITY is not computable in $\mathsf{QAC}^0$, a long-standing question in quantum complexity theory.

arXiv:2508.11487•Leibniz international proceedings in informatics•Aug 15, 2025•29 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

Learning shallow quantum circuits with many-qubit gates

Francisca Vasconcelos, Hsin-Yuan Huang

We present the first computationally-efficient algorithm for average-case learning of shallow quantum circuits with many-qubit gates. Specifically, we provide a quasi-polynomial time and sample complexity algorithm for learning unknown QAC$^0$ circuits -- constant-depth circuits with arbitrary single-qubit gates and polynomially many $CZ$ gates of unbounded width -- with at most logarithmic ancilla, up to inverse-polynomially small error. Furthermore, we show that the learned unitary can be efficiently synthesized in poly-logarithmic depth. This work expands the family of efficiently learnable quantum circuits, notably since in finite-dimensional circuit geometries, QAC$^0$ circuits require polynomial depth to implement.

arXiv:2410.16693•Oct 22, 2024•11 citations

Quantum State Learning Implies Circuit Lower Bounds

Nai-Hui Chia, Daniel Liang, Fang Song

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.

arXiv:2405.10242•May 16, 2024•5 citations

Proper Learning of Shallow All-to-All Quantum Circuits

Steven Kordonowy, Jacob Watkins

This work considers a variation on the problem of learning shallow quantum circuits. Given query access to the circuit, as well as knowledge of its gate layout, we consider the task of learning the specific gates used in the circuit, producing an operationally-equivalent circuit matching this structure. Building on recent work for learning Haar random brickwork circuits, we identify a meta-algorithmic framework for learning broad classes of circuits based on iterative local gate inversions at the front and back of the circuit. We apply these techniques to study random, all-to-all, two-local circuits, and provide analytical and numerical evidence that this ensemble undergoes a sharp learnability transition at depth $d^* \sim \log_2 n + \log_2\log_2 n$ in the large size limit, based on an analysis of lightcone growth. These results have implications for recently proposed quantum cryptographic schemes based on the difficulty of circuit learning, though there are important distinctions with respect to our setting that suggest avenues for future study.

quant-pharXiv:2608.20162•Aug 21, 2026•1 citation
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.
The paper asks when local random quantum circuits can be reconstructed from copies of a single output state, and how learnability constrains pseudorandomness. It considers depth-ddd brickwork circuits on nnn sites of a fixed-dimensional lattice, with ℓ\ellℓ qubits per site and two-site gates. The learning model uses a public set of M=64n2d2/δ2M=64n^2d^2/\delta^2M=64n2d2/δ2 independently Haar-sampled, finite-precision gates; unknown circuit locations receive uniformly random labels from this set.
For fixed lattice dimension kkk and d≤0.01n1/kd\leq0.01n^{1/k}d≤0.01n1/k, the algorithm exactly recovers the gate labels from copies of U∣0⟩⊗nℓU|0\rangle^{\otimes n\ell}U∣0⟩⊗nℓ in sample and time complexity poly⁡k(n,d,δ−1)2Ok(ℓd)\operatorname{poly}_k(n,d,\delta^{-1})2^{O_k(\ell d)}polyk​(n,d,δ−1)2Ok​(ℓd), with high probability over the gateset, circuit and measurements. This is polynomial when ℓd=O(log⁡n)\ell d=O(\log n)ℓd=O(logn). It peels off layers by testing candidate inverse gates: the correct inverse eliminates correlations between selected output sites, while incorrect candidates leave a detectable correlation gap. The analysis constructs Bell-pair routing witnesses involving only Ok(d)O_k(d)Ok​(d) gates, avoiding reconstruction of full lightcones.
A technical ingredient is a Haar-unitary small-ball bound for degree-sss polynomials: Pr⁡[∣P(U)∣≤ε∥P∥∞]≤64m2ε1/(24πs)\Pr[|P(U)|\leq\varepsilon\|P\|_\infty]\leq64m^2\varepsilon^{1/(24\pi s)}Pr[∣P(U)∣≤ε∥P∥∞​]≤64m2ε1/(24πs). Its exponent is independent of matrix dimension; the proof combines Weyl integration, interpolation and a univariate Remez inequality.
Exact recovery is restricted to the specified discrete public-gateset model, rather than unrestricted continuous Haar gates. The paper does not establish pseudorandomness above the learning regime. The scale ℓd=ω(log⁡n)\ell d=\omega(\log n)ℓd=ω(logn) is necessary for one-dimensional pseudorandom states; whether it marks an ancilla-free threshold in higher dimensions remains open.
We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an ε\varepsilonε range is at most a polynomial in ε\varepsilonε. Using it, we show that the scrambling speed of a random quantum circuit is lower bounded: Namely, every input qubit has an influence that is at least inverse exponential in depth, on any output qubit touched by its lightcone. Our result on scrambling speed works with high probability over the choice of a circuit from an ensemble, as opposed to just working in expectation. As an application, we give the first polynomial-time algorithm for learning log-depth random quantum circuits with Haar random gates up to polynomially small diamond distance, given oracle access to the circuit. Other applications of this new scrambling speed lower bound include: ∙\bullet∙ An optimal Ω(log⁡ε−1)Ω(\log \varepsilon^{-1})Ω(logε−1) depth lower bound for ε\varepsilonε-approximate unitary designs on any circuit architecture; ∙\bullet∙ A polynomial-time quantum algorithm that computes the depth of a bounded-depth circuit, given oracle access to the circuit. Our learning and depth-testing algorithms apply to architectures defined over any geometric dimension, and can be generalized to a wide class of architectures with good lightcone properties.
Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(log⁡log⁡n)Θ(\log \log n)Θ(loglogn)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time\textit{constant-time}constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC0\mathsf{QAC}^0QAC0. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC0\mathsf{QAC}^0QAC0, a long-standing question in quantum complexity theory.
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 present the first computationally-efficient algorithm for average-case learning of shallow quantum circuits with many-qubit gates. Specifically, we provide a quasi-polynomial time and sample complexity algorithm for learning unknown QAC0^00 circuits -- constant-depth circuits with arbitrary single-qubit gates and polynomially many CZCZCZ gates of unbounded width -- with at most logarithmic ancilla, up to inverse-polynomially small error. Furthermore, we show that the learned unitary can be efficiently synthesized in poly-logarithmic depth. This work expands the family of efficiently learnable quantum circuits, notably since in finite-dimensional circuit geometries, QAC0^00 circuits require polynomial depth to implement.
We establish connections between state tomography, pseudorandomness, quantum state synthesis, and circuit lower bounds. In particular, let C\mathfrak{C}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 C\mathfrak{C}C or is Haar random, promised one of these is the case. For arbitrary fixed constant ccc, we show that if the algorithm uses at most O(2nc)O(2^{n^c})O(2nc) time and 2n0.992^{n^{0.99}}2n0.99 samples then stateBQE⊄stateC\mathsf{stateBQE} \not\subset \mathsf{state}\mathfrak{C}stateBQE⊂stateC. Here stateBQE:=stateBQTIME[2O(n)]\mathsf{stateBQE} := \mathsf{stateBQTIME}[2^{O(n)}]stateBQE:=stateBQTIME[2O(n)] and stateC\mathsf{state}\mathfrak{C}stateC 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 2O(n)2^{O(n)}2O(n) samples and time, or O(nω(1))O(n^{ω(1)})O(nω(1)) samples and 2O(nω(1))2^{O(n^{ω(1)})}2O(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.
This work considers a variation on the problem of learning shallow quantum circuits. Given query access to the circuit, as well as knowledge of its gate layout, we consider the task of learning the specific gates used in the circuit, producing an operationally-equivalent circuit matching this structure. Building on recent work for learning Haar random brickwork circuits, we identify a meta-algorithmic framework for learning broad classes of circuits based on iterative local gate inversions at the front and back of the circuit. We apply these techniques to study random, all-to-all, two-local circuits, and provide analytical and numerical evidence that this ensemble undergoes a sharp learnability transition at depth d∗∼log⁡2n+log⁡2log⁡2nd^* \sim \log_2 n + \log_2\log_2 nd∗∼log2​n+log2​log2​n in the large size limit, based on an analysis of lightcone growth. These results have implications for recently proposed quantum cryptographic schemes based on the difficulty of circuit learning, though there are important distinctions with respect to our setting that suggest avenues for future study.