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

One Gate at a Time: Complexity Growth in Random Quantum Circuits

Zhi Li

quant-phmath-phSubmitted Sep 15, 2026• Announced Sep 16, 2026• 0 citations
arXivHTMLPDF

Abstract

A random unitary quantum circuit is expected to be incompressible for exponentially long times. We show that the constant-error circuit complexity of a random unitary circuit grows almost linearly with time as $Ω(T/\log T)$. The bound holds for all $2\leq T\leq 4^n$ where $n$ is the system size, and involves no other $n$-dependence. This improves previous lower bounds derived from spectral gaps and unitary designs by a factor of $\mathrm{poly}(n)$. Drawing on insights from stochastic calculus, geometric functional analysis, and randomized linear algebra, our approach exploits the circuit's response to variations of individual gates and requires no control over convergence to high-order unitary designs.

AI Summary

The paper asks how long a random quantum circuit remains incompressible when constant approximation error is allowed. It studies sequential all-to-all circuits on $n$ qubits, with each gate Haar-random on a uniformly chosen qubit pair. Complexity counts arbitrary two-qubit gates needed for an operator-norm approximation. For every $2\le T\le D=4^n-1$, it proves $\mathcal C_{1/2}(U_T)=\Omega(T/\log T)$ except with probability $\exp[-\Omega((T/n^2)(1+\log(D/T)))]$. For $T=O(n^2)$, the failure probability improves to $\exp[-\Omega(T)]$. The complexity bound removes a factor of $n$ relative to the stated bound obtained from the optimal uniform spectral gap, while retaining the exponential time range. The proof analyzes tangent directions obtained by varying individual gates. Adaptive selectors retain a constant fraction whose frame operator has bounded norm. Integration by parts and a smooth maximum then bound the probability of approaching any target set of size $\exp(cT)$ in normalized Hilbert–Schmidt distance. A circuit-net argument converts this into complexity growth; a separate support-counting argument handles very short circuits. The method avoids high-order designs and uniform moment gaps, but uses second-moment mixing. Supporting examples include exponentially small small-ball probabilities for random Pauli rotations through $T=O(2^n)$ and complexity growth for Kac’s walk despite its exponentially small spectral gap. The main local-circuit theorem concerns all-to-all connectivity, retains a logarithmic loss, and has system-size-dependent failure probabilities. The Pauli and Kac examples are explicitly not optimized in time range or constants.

No sign of AI-generated textAI use disclosed
In particular, AI proposed and analyzed the final form of the selectors used in that section, which are crucial for our work.

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

Related papers

On the moments of random quantum circuits and robust quantum complexity

Jonas Haferkamp

We prove new lower bounds on the growth of robust quantum circuit complexity -- the minimal number of gates $C_δ(U)$ to approximate a unitary $U$ up to an error of $δ$ in operator norm distance. More precisely we show two bounds for random quantum circuits with local gates drawn from a subgroup of $SU(4)$. First, for $δ=Θ(2^{-n})$, we prove a linear growth rate: $C_δ\geq d/\mathrm{poly}(n)$ for random quantum circuits on $n$ qubits with $d\leq 2^{n/2}$ gates. Second, for $ δ=Ω(1)$, we prove a square-root growth of complexity: $C_δ\geq \sqrt{d}/\mathrm{poly}(n)$ for all $d\leq 2^{n/2}$. Finally, we provide a simple conjecture regarding the Fourier support of randomly drawn Boolean functions that would imply linear growth for constant $δ$. While these results follow from bounds on the moments of random quantum circuits, we do not make use of existing results on the generation of unitary $t$-designs. Instead, we bound the moments of an auxiliary random walk on the diagonal unitaries acting on phase states. In particular, our proof is comparably short and self-contained.

arXiv:2303.16944•Mar 29, 2023•15 citations

Random unitary circuits with constant spectral gap

Tim Baer, Jeongwan Haah

We prove constant lower bounds for the spectral gap of the following random walks on unitary groups $\mathsf{SU}(2^n)$ on $n$ qubits. (i) Random Pauli Rotation: choose an $n$-qubit Pauli operator $P$ and an angle $θ\in [0,2π)$, both uniformly at random, and apply $e^{\mathrm i θP}$. (ii) Brickwork Random Unitary Circuit: choose $n-1$ unitaries $U_{i}$ uniformly at random from $\mathsf{SU}(4)$ (including central phases of the parent group) independently, and apply $U_{2j-1}$ on two qubits $2j-1, 2j$ and then $U_{2j}$ on two qubits $2j, 2j+1$. Importantly, the gap bounds are independent of $n$ and apply for all finite dimensional unitary representations of $\mathsf{SU}(2^n)$ uniformly. Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary $t$-designs after $\mathcal{O}(nt)$ steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be $\mathcal{O}(2^{cn})$ for some $c < 1$. Our unconditional constant spectral gap removes this restriction. We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal $t$-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for $t=2$.

quant-pharXiv:2607.20919•Jul 24, 2026•8 citations

Models of Quantum Complexity Growth

Fernando G. S. L. Brandão, Wissam A Chemissany, Nicholas Hunter-Jones +2 more

The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics.The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state.It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a shortcut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions.To go further, one may study more generic models of complexity growth.We provide a rigorous connection between complexity growth and unitary k-designs, ensembles that capture the randomness of the unitary group.This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity.We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind.Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.

arXiv:1912.04297•PRX Quantum•Jul 29, 2021•176 citations

Linear growth of quantum circuit complexity

Jonas Haferkamp, Philippe Faist, Naga Bhavya Teja Kothakonda +2 more

Abstract The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haar-random two-qubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates—this is the operation’s exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.

arXiv:2106.05305•Nature Physics•Mar 28, 2022•197 citations

Incompressibility and Spectral Gaps of Random Circuits

Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp +3 more

Random reversible and quantum circuits form random walks on the alternating group Alt(2n) and unitary group SU(2n), respectively, with each random gate as one step of the walk. Existing bounds on the spectral gap for the t-th moment of these random walks have inverse-polynomial dependence in both n and t. We prove that the gap for random reversible circuits is Ω(n−3) for all t≥1, and the gap for random quantum circuits is Ω(n−3) for t ≤ Θ(2n/2).Importantly, these gaps are independent of t in the respective regimes. We can further improve both gaps to n−1/polylog(n, t) for t ≤ 2Θ(n), which is tight up to polylog factors in n and t. Our spectral gap results have a number of consequences:1)Random reversible circuits with $\mathcal{O}\left( {{n^4}t} \right)$ gates form multiplicative-error t-wise independent (even) permutations for all t ≥ 1; for t ≤ Θ(2n/6.1), we show that $\tilde {\mathcal{O}}\left( {{n^2}t} \right)$ gates suffice.2)Random quantum circuits with $\mathcal{O}\left( {{n^4}t} \right)$ gates form multiplicative-error unitary t-designs for t ≤Θ(2n/2); for t ≤ Θ(22n/5), we show that $\tilde {\mathcal{O}}\left( {{n^2}t} \right)$ gates suffice.3)The robust quantum circuit complexity of random quantum circuits grows linearly for an exponentially long time, proving the robust Brown–Susskind conjecture [1], [2]. We also show an analogous result for random reversible circuits.Our spectral gap bounds are proven by reducing random quantum circuits to a more structured walk: a modification of the "PFC ensemble" from [3] together with an expander on the alternating group due to Kassabov [4], for which we give an efficient implementation using reversible circuits. In our reduction, we approximate the structured walk with local random circuits without losing the gap, which uses tools from the study of frustration-free Hamiltonians.

arXiv:2406.07478•Annual Symposium on Foundations of Computer Science•Dec 14, 2025•75 citations

Depth dependence of entanglement and circuit complexity in random linear optical networks

Laura Shou, Joseph T. Iosue, Yu-Xin Wang +2 more

We study the growth of entanglement and circuit complexity in random passive linear optical networks as a function of the circuit depth. For entanglement dynamics, we start with an initial Gaussian state with all $n$ modes equally squeezed. For random brickwork circuits, we show that entanglement, as measured by the Rényi-2 entropy, grows diffusively as a function of the depth, in contrast to the linear growth for random qubit brickwork circuits. In the other direction, for arbitrary circuit geometries we prove bounds on depths which ensure the average-case subsystem entanglement reaches within a constant factor of the maximum value in all subsystems, and bounds which ensure closeness of the random linear optical unitary to a Haar random unitary in $L^2$ Wasserstein distance. We also consider robust circuit complexity for random one-dimensional brickwall circuits, as measured by the minimum number of gates required in any circuit that approximately implements the linear optical unitary. Viewing this as a function of the number of modes and the circuit depth, we show the robust circuit complexity for random one-dimensional brickwall circuits scales at most diffusively in the depth with high probability, again in contrast to the linear scaling for certain random qubit circuits. The corresponding Gaussian unitary $\tilde{\mathcal U}$ for the approximate implementation retains high output fidelity $|\langleψ|\mathcal U^\dagger \tilde{\mathcal U}|ψ\rangle|^2$ for pure states $|ψ\rangle$ with constrained expected photon-number.

quant-pharXiv:2604.14277•Apr 17, 2026•3 citations
A random unitary quantum circuit is expected to be incompressible for exponentially long times. We show that the constant-error circuit complexity of a random unitary circuit grows almost linearly with time as Ω(T/log⁡T)Ω(T/\log T)Ω(T/logT). The bound holds for all 2≤T≤4n2\leq T\leq 4^n2≤T≤4n where nnn is the system size, and involves no other nnn-dependence. This improves previous lower bounds derived from spectral gaps and unitary designs by a factor of poly(n)\mathrm{poly}(n)poly(n). Drawing on insights from stochastic calculus, geometric functional analysis, and randomized linear algebra, our approach exploits the circuit's response to variations of individual gates and requires no control over convergence to high-order unitary designs.
The paper asks how long a random quantum circuit remains incompressible when constant approximation error is allowed. It studies sequential all-to-all circuits on nnn qubits, with each gate Haar-random on a uniformly chosen qubit pair. Complexity counts arbitrary two-qubit gates needed for an operator-norm approximation.
For every 2≤T≤D=4n−12\le T\le D=4^n-12≤T≤D=4n−1, it proves C1/2(UT)=Ω(T/log⁡T)\mathcal C_{1/2}(U_T)=\Omega(T/\log T)C1/2​(UT​)=Ω(T/logT) except with probability exp⁡[−Ω((T/n2)(1+log⁡(D/T)))]\exp[-\Omega((T/n^2)(1+\log(D/T)))]exp[−Ω((T/n2)(1+log(D/T)))]. For T=O(n2)T=O(n^2)T=O(n2), the failure probability improves to exp⁡[−Ω(T)]\exp[-\Omega(T)]exp[−Ω(T)]. The complexity bound removes a factor of nnn relative to the stated bound obtained from the optimal uniform spectral gap, while retaining the exponential time range.
The proof analyzes tangent directions obtained by varying individual gates. Adaptive selectors retain a constant fraction whose frame operator has bounded norm. Integration by parts and a smooth maximum then bound the probability of approaching any target set of size exp⁡(cT)\exp(cT)exp(cT) in normalized Hilbert–Schmidt distance. A circuit-net argument converts this into complexity growth; a separate support-counting argument handles very short circuits. The method avoids high-order designs and uniform moment gaps, but uses second-moment mixing.
Supporting examples include exponentially small small-ball probabilities for random Pauli rotations through T=O(2n)T=O(2^n)T=O(2n) and complexity growth for Kac’s walk despite its exponentially small spectral gap. The main local-circuit theorem concerns all-to-all connectivity, retains a logarithmic loss, and has system-size-dependent failure probabilities. The Pauli and Kac examples are explicitly not optimized in time range or constants.
We prove new lower bounds on the growth of robust quantum circuit complexity -- the minimal number of gates Cδ(U)C_δ(U)Cδ​(U) to approximate a unitary UUU up to an error of δδδ in operator norm distance. More precisely we show two bounds for random quantum circuits with local gates drawn from a subgroup of SU(4)SU(4)SU(4). First, for δ=Θ(2−n)δ=Θ(2^{-n})δ=Θ(2−n), we prove a linear growth rate: Cδ≥d/poly(n)C_δ\geq d/\mathrm{poly}(n)Cδ​≥d/poly(n) for random quantum circuits on nnn qubits with d≤2n/2d\leq 2^{n/2}d≤2n/2 gates. Second, for $ δ=Ω(1)$, we prove a square-root growth of complexity: Cδ≥d/poly(n)C_δ\geq \sqrt{d}/\mathrm{poly}(n)Cδ​≥d​/poly(n) for all d≤2n/2d\leq 2^{n/2}d≤2n/2. Finally, we provide a simple conjecture regarding the Fourier support of randomly drawn Boolean functions that would imply linear growth for constant δδδ. While these results follow from bounds on the moments of random quantum circuits, we do not make use of existing results on the generation of unitary ttt-designs. Instead, we bound the moments of an auxiliary random walk on the diagonal unitaries acting on phase states. In particular, our proof is comparably short and self-contained.
We prove constant lower bounds for the spectral gap of the following random walks on unitary groups SU(2n)\mathsf{SU}(2^n)SU(2n) on nnn qubits. (i) Random Pauli Rotation: choose an nnn-qubit Pauli operator PPP and an angle θ∈[0,2π)θ\in [0,2π)θ∈[0,2π), both uniformly at random, and apply eiθPe^{\mathrm i θP}eiθP. (ii) Brickwork Random Unitary Circuit: choose n−1n-1n−1 unitaries UiU_{i}Ui​ uniformly at random from SU(4)\mathsf{SU}(4)SU(4) (including central phases of the parent group) independently, and apply U2j−1U_{2j-1}U2j−1​ on two qubits 2j−1,2j2j-1, 2j2j−1,2j and then U2jU_{2j}U2j​ on two qubits 2j,2j+12j, 2j+12j,2j+1. Importantly, the gap bounds are independent of nnn and apply for all finite dimensional unitary representations of SU(2n)\mathsf{SU}(2^n)SU(2n) uniformly. Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary ttt-designs after O(nt)\mathcal{O}(nt)O(nt) steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be O(2cn)\mathcal{O}(2^{cn})O(2cn) for some c<1c < 1c<1. Our unconditional constant spectral gap removes this restriction. We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal ttt-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for t=2t=2t=2.
The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics.The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state.It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a shortcut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions.To go further, one may study more generic models of complexity growth.We provide a rigorous connection between complexity growth and unitary k-designs, ensembles that capture the randomness of the unitary group.This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity.We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind.Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.
Abstract The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haar-random two-qubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates—this is the operation’s exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.
Random reversible and quantum circuits form random walks on the alternating group Alt(2n) and unitary group SU(2n), respectively, with each random gate as one step of the walk. Existing bounds on the spectral gap for the t-th moment of these random walks have inverse-polynomial dependence in both n and t. We prove that the gap for random reversible circuits is Ω(n−3) for all t≥1, and the gap for random quantum circuits is Ω(n−3) for t ≤ Θ(2n/2).Importantly, these gaps are independent of t in the respective regimes. We can further improve both gaps to n−1/polylog(n, t) for t ≤ 2Θ(n), which is tight up to polylog factors in n and t. Our spectral gap results have a number of consequences:1)Random reversible circuits with O(n4t)\mathcal{O}\left( {{n^4}t} \right)O(n4t) gates form multiplicative-error t-wise independent (even) permutations for all t ≥ 1; for t ≤ Θ(2n/6.1), we show that O~(n2t)\tilde {\mathcal{O}}\left( {{n^2}t} \right)O~(n2t) gates suffice.2)Random quantum circuits with O(n4t)\mathcal{O}\left( {{n^4}t} \right)O(n4t) gates form multiplicative-error unitary t-designs for t ≤Θ(2n/2); for t ≤ Θ(22n/5), we show that O~(n2t)\tilde {\mathcal{O}}\left( {{n^2}t} \right)O~(n2t) gates suffice.3)The robust quantum circuit complexity of random quantum circuits grows linearly for an exponentially long time, proving the robust Brown–Susskind conjecture [1], [2]. We also show an analogous result for random reversible circuits.Our spectral gap bounds are proven by reducing random quantum circuits to a more structured walk: a modification of the "PFC ensemble" from [3] together with an expander on the alternating group due to Kassabov [4], for which we give an efficient implementation using reversible circuits. In our reduction, we approximate the structured walk with local random circuits without losing the gap, which uses tools from the study of frustration-free Hamiltonians.
We study the growth of entanglement and circuit complexity in random passive linear optical networks as a function of the circuit depth. For entanglement dynamics, we start with an initial Gaussian state with all nnn modes equally squeezed. For random brickwork circuits, we show that entanglement, as measured by the Rényi-2 entropy, grows diffusively as a function of the depth, in contrast to the linear growth for random qubit brickwork circuits. In the other direction, for arbitrary circuit geometries we prove bounds on depths which ensure the average-case subsystem entanglement reaches within a constant factor of the maximum value in all subsystems, and bounds which ensure closeness of the random linear optical unitary to a Haar random unitary in L2L^2L2 Wasserstein distance. We also consider robust circuit complexity for random one-dimensional brickwall circuits, as measured by the minimum number of gates required in any circuit that approximately implements the linear optical unitary. Viewing this as a function of the number of modes and the circuit depth, we show the robust circuit complexity for random one-dimensional brickwall circuits scales at most diffusively in the depth with high probability, again in contrast to the linear scaling for certain random qubit circuits. The corresponding Gaussian unitary U~\tilde{\mathcal U}U~ for the approximate implementation retains high output fidelity ∣⟨ψ∣U†U~∣ψ⟩∣2|\langleψ|\mathcal U^\dagger \tilde{\mathcal U}|ψ\rangle|^2∣⟨ψ∣U†U~∣ψ⟩∣2 for pure states ∣ψ⟩|ψ\rangle∣ψ⟩ with constrained expected photon-number.