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

On the moments of random quantum circuits and robust quantum complexity

Jonas Haferkamp

Published Mar 29, 2023• 15 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2303.16944

Related papers

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

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

Random Quantum Circuits Beyond Moment Matching

Shih-Han Hung

Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accurately these designs reproduce the distribution of each output probability. We show that, for every strong $\varepsilon$-approximate unitary $k$-design on $n$ qubits, the distribution of each output probability is within $O(k^{-1/2}(1+k/2^n)^{-1/2}+\varepsilon)$ in Kolmogorov distance of the Porter-Thomas distribution, a beta distribution with parameters $1$ and $2^n-1$. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We then show that a mild form of local invariance suffices. We prove that any such design that is invariant under unitary translations acting on a single qubit approximates Porter-Thomas to total variation distance $O(k^{-1/2}+\varepsilon)$. Every strong $\varepsilon$-approximate unitary $k$-design invariant on $\log k+O(1)$ qubits achieves error $2^{-Ω(k)}+O(\varepsilon)$ in Kolmogorov distance and $2^{-Ω(k)}+O(\varepsilon\log(2/\varepsilon))$ in total variation distance. These results identify the distributional accuracy guaranteed by moment matching and the structure that improves it. As an application, we show that the Shannon entropy of the output distribution of a strong $\varepsilon$-approximate $k$-design is concentrated around its Haar value $n-Θ(1)$: its mean differs from the Haar mean by $O(k^{-1/4}+\varepsilon^{1/2})$ and its standard deviation is $O(2^{-n/2}+k^{-1/8}+\varepsilon^{1/4})$. Consequently, a trusted device sampling such circuits generates $n-O(1)$ bits of entropy per sample, which makes them useful for random number generation.

quant-pharXiv:2610.02135•Oct 2, 2026•0 citations

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

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•117 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
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) δ=Ω(1)δ=Ω(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.
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 quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accurately these designs reproduce the distribution of each output probability. We show that, for every strong ε\varepsilonε-approximate unitary kkk-design on nnn qubits, the distribution of each output probability is within O(k−1/2(1+k/2n)−1/2+ε)O(k^{-1/2}(1+k/2^n)^{-1/2}+\varepsilon)O(k−1/2(1+k/2n)−1/2+ε) in Kolmogorov distance of the Porter-Thomas distribution, a beta distribution with parameters 111 and 2n−12^n-12n−1. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We then show that a mild form of local invariance suffices. We prove that any such design that is invariant under unitary translations acting on a single qubit approximates Porter-Thomas to total variation distance O(k−1/2+ε)O(k^{-1/2}+\varepsilon)O(k−1/2+ε). Every strong ε\varepsilonε-approximate unitary kkk-design invariant on log⁡k+O(1)\log k+O(1)logk+O(1) qubits achieves error 2−Ω(k)+O(ε)2^{-Ω(k)}+O(\varepsilon)2−Ω(k)+O(ε) in Kolmogorov distance and 2−Ω(k)+O(εlog⁡(2/ε))2^{-Ω(k)}+O(\varepsilon\log(2/\varepsilon))2−Ω(k)+O(εlog(2/ε)) in total variation distance. These results identify the distributional accuracy guaranteed by moment matching and the structure that improves it. As an application, we show that the Shannon entropy of the output distribution of a strong ε\varepsilonε-approximate kkk-design is concentrated around its Haar value n−Θ(1)n-Θ(1)n−Θ(1): its mean differs from the Haar mean by O(k−1/4+ε1/2)O(k^{-1/4}+\varepsilon^{1/2})O(k−1/4+ε1/2) and its standard deviation is O(2−n/2+k−1/8+ε1/4)O(2^{-n/2}+k^{-1/8}+\varepsilon^{1/4})O(2−n/2+k−1/8+ε1/4). Consequently, a trusted device sampling such circuits generates n−O(1)n-O(1)n−O(1) bits of entropy per sample, which makes them useful for random number generation.
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 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.
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.