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:2406.07478 · Annual Symposium on Foundations of Computer Science

Incompressibility and Spectral Gaps of Random Circuits

Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, Xinyu Tan

Published Dec 14, 2025• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/focs63196.2025.00069

Related papers

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

Zhi Li

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.

quant-pharXiv:2609.17457•Sep 16, 2026•0 citations

Improved spectral gaps for random quantum circuits: Large local dimensions and all-to-all interactions

Jonas Haferkamp, Nicholas Hunter-Jones

Random quantum circuits are a central concept in quantum information theory with applications ranging from demonstrations of quantum computational advantage to descriptions of scrambling in strongly interacting systems and black holes. The utility of random quantum circuits in these settings stems from their ability to rapidly generate quantum pseudorandomness. In a seminal paper by Brand\~ao, Harrow, and Horodecki [Commun. Math. Phys. 346, 397 (2016)] it was proven that the $t\mathrm{th}$ moment operator of local random quantum circuits on $n$ qudits with local dimension $q$ has a spectral gap of at least $\mathrm{\ensuremath{\Omega}}({n}^{\ensuremath{-}1}{t}^{\ensuremath{-}5\ensuremath{-}3.1/ln(q)})$, which implies that they are efficient constructions of approximate unitary designs. As a first result, we use Knabe bounds for the spectral gaps of frustration-free Hamiltonians to show that one-dimensional random quantum circuits have a spectral gap scaling as $\mathrm{\ensuremath{\Omega}}({n}^{\ensuremath{-}1})$, provided that $t$ is small compared to the local dimension: ${t}^{2}\ensuremath{\le}O(q)$. This implies a (nearly) linear scaling of the circuit depth in the design order $t$. Our second result is an unconditional spectral gap bounded below by $\mathrm{\ensuremath{\Omega}}[{n}^{\ensuremath{-}1}{ln}^{\ensuremath{-}1}(n){t}^{\ensuremath{-}\ensuremath{\alpha}(q)}]$ for random quantum circuits with all-to-all interactions. This improves both the $n$ and $t$ scaling in design depth for the nonlocal model. We show this by proving a recursion relation for the spectral gaps involving an auxiliary random walk. Lastly, we solve the smallest nontrivial case exactly and combine with numerics and Knabe bounds to improve the constants involved in the spectral gap for small values of $t$.

arXiv:2012.05259•Physical Review A•Aug 17, 2021•30 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)$ independently, and apply $U_{2j-1}$ on two qubits $2j-1, 2j$ and then $U_{2j}$ on two qubits $2j, 2j+1$. Importantly, the spectral gap lower bounds are independent of $n$ and apply for all finite dimensional unitary representations of $\mathsf{SU}(2^n)$ uniformly, including those that appear in unitary $t$-designs. We also prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit.

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

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•1 citation

Exact spectral gaps of random one-dimensional quantum circuits

Andrew E. Deneris, Pablo Bermejo, Paolo Braccia +2 more

The spectral gap of local random quantum circuits is a fundamental property that determines how close the moments of the circuit's unitaries match those of a Haar random distribution. When studying spectral gaps, it is common to bound these quantities using tools from statistical mechanics or via quantum information-based inequalities. By focusing on the second moment of one-dimensional unitary circuits where nearest-neighboring gates act on sets of qudits (with open and closed boundary conditions), we show that one can exactly compute the associated spectral gaps. Indeed, having access to their functional form allows us to prove several important results, such as the fact that the spectral gap for closed boundary condition is exactly the square of the gap for open boundaries, as well as improve on previously known bounds for approximate design convergence. Finally, we verify our theoretical results by numerically computing the spectral gap for systems of up to 70 qubits, as well as comparing them to gaps of random orthogonal and symplectic circuits.

arXiv:2408.11201•Physical Review A•Nov 25, 2025•4 citations

Random quantum circuits are approximate unitary t -designs in depth O(nt5+o(1))

Jonas Haferkamp

The applications of random quantum circuits range from quantum computing and quantum many-body systems to the physics of black holes. Many of these applications are related to the generation of quantum pseudorandomness: Random quantum circuits are known to approximate unitary t -designs. Unitary t -designs are probability distributions that mimic Haar randomness up to t th moments. In a seminal paper, Brandão, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth O(nt10.5) are approximate unitary t -designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by Ω(n−1t−9.5) . We improve this lower bound to Ω(n−1t−4−o(1)) , where the o(1) term goes to 0 as t→∞ . A direct consequence of this scaling is that random quantum circuits generate approximate unitary t -designs in depth O(nt5+o(1)) . Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group. As an auxiliary result, we prove fast convergence to the Haar measure for random Clifford unitaries interleaved with Haar random single qubit unitaries.

arXiv:2203.16571•Quantum•Sep 8, 2022•81 citations
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.
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.
Random quantum circuits are a central concept in quantum information theory with applications ranging from demonstrations of quantum computational advantage to descriptions of scrambling in strongly interacting systems and black holes. The utility of random quantum circuits in these settings stems from their ability to rapidly generate quantum pseudorandomness. In a seminal paper by Brand\~ao, Harrow, and Horodecki [Commun. Math. Phys. 346, 397 (2016)] it was proven that the ttht\mathrm{th}tth moment operator of local random quantum circuits on nnn qudits with local dimension qqq has a spectral gap of at least $\mathrm{\ensuremath{\Omega}}({n}^{\ensuremath{-}1}{t}^{\ensuremath{-}5\ensuremath{-}3.1/ln(q)})$, which implies that they are efficient constructions of approximate unitary designs. As a first result, we use Knabe bounds for the spectral gaps of frustration-free Hamiltonians to show that one-dimensional random quantum circuits have a spectral gap scaling as $\mathrm{\ensuremath{\Omega}}({n}^{\ensuremath{-}1})$, provided that ttt is small compared to the local dimension: ${t}^{2}\ensuremath{\le}O(q)$. This implies a (nearly) linear scaling of the circuit depth in the design order ttt. Our second result is an unconditional spectral gap bounded below by $\mathrm{\ensuremath{\Omega}}[{n}^{\ensuremath{-}1}{ln}^{\ensuremath{-}1}(n){t}^{\ensuremath{-}\ensuremath{\alpha}(q)}]$ for random quantum circuits with all-to-all interactions. This improves both the nnn and ttt scaling in design depth for the nonlocal model. We show this by proving a recursion relation for the spectral gaps involving an auxiliary random walk. Lastly, we solve the smallest nontrivial case exactly and combine with numerics and Knabe bounds to improve the constants involved in the spectral gap for small values of ttt.
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) 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 spectral gap lower bounds are independent of nnn and apply for all finite dimensional unitary representations of SU(2n)\mathsf{SU}(2^n)SU(2n) uniformly, including those that appear in unitary ttt-designs. We also prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit.
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.
The spectral gap of local random quantum circuits is a fundamental property that determines how close the moments of the circuit's unitaries match those of a Haar random distribution. When studying spectral gaps, it is common to bound these quantities using tools from statistical mechanics or via quantum information-based inequalities. By focusing on the second moment of one-dimensional unitary circuits where nearest-neighboring gates act on sets of qudits (with open and closed boundary conditions), we show that one can exactly compute the associated spectral gaps. Indeed, having access to their functional form allows us to prove several important results, such as the fact that the spectral gap for closed boundary condition is exactly the square of the gap for open boundaries, as well as improve on previously known bounds for approximate design convergence. Finally, we verify our theoretical results by numerically computing the spectral gap for systems of up to 70 qubits, as well as comparing them to gaps of random orthogonal and symplectic circuits.
The applications of random quantum circuits range from quantum computing and quantum many-body systems to the physics of black holes. Many of these applications are related to the generation of quantum pseudorandomness: Random quantum circuits are known to approximate unitary t -designs. Unitary t -designs are probability distributions that mimic Haar randomness up to t th moments. In a seminal paper, Brandão, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth O(nt10.5) are approximate unitary t -designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by Ω(n−1t−9.5) . We improve this lower bound to Ω(n−1t−4−o(1)) , where the o(1) term goes to 0 as t→∞ . A direct consequence of this scaling is that random quantum circuits generate approximate unitary t -designs in depth O(nt5+o(1)) . Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group. As an auxiliary result, we prove fast convergence to the Haar measure for random Clifford unitaries interleaved with Haar random single qubit unitaries.