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:2310.19783 · PRX Quantum

Approximate t -Designs in Generic Circuit Architectures

Daniel Belkin, James Allen, Soumik Ghosh, Christopher Kang, Sophia Fuhui Lin, James Sud, Frederic T. Chong, Bill Fefferman, Bryan K. Clark

Published Dec 17, 2024• 17 citations
arXivHTMLPDF

Abstract

Unitary t -designs are distributions on the unitary group whose first t moments appear maximally random. Previous work has established several upper bounds on the depths at which certain specific random quantum circuit ensembles approximate t -designs. Here we show that these bounds can be extended to any fixed architecture of Haar-random two-site gates. This is accomplished by relating the spectral gaps of such architectures to those of one-dimensional brickwork architectures. Our bound depends on the details of the architecture only via the typical number of layers needed for a block of the circuit to form a connected graph over the sites. When this quantity is bounded, the circuit forms an approximate t -design in at most linear depth. We give numerical evidence for a stronger bound that depends only on the number of connected blocks into which the architecture can be divided. We also give an implicit bound for nondeterministic architectures in terms of properties of the corresponding distribution over fixed architectures. Published by the American Physical Society 2024

DOI
10.1103/prxquantum.5.040344

Related papers

Approximate 𝑡-Designs in Generic Circuit Architectures

Daniel Belkin, James Allen, Soumik Ghosh +6 more

Unitary 𝑡-designs are distributions on the unitary group whose first 𝑡 moments appear maximally random. Previous work has established several upper bounds on the depths at which certain specific random quantum circuit ensembles approximate 𝑡-designs. Here we show that these bounds can be extended to any fixed architecture of Haar-random two-site gates. This is accomplished by relating the spectral gaps of such architectures to those of one-dimensional brickwork architectures. Our bound depends on the details of the architecture only via the typical number of layers needed for a block of the circuit to form a connected graph over the sites. When this quantity is bounded, the circuit forms an approximate 𝑡-design in at most linear depth. We give numerical evidence for a stronger bound that depends only on the number of connected blocks into which the architecture can be divided. We also give an implicit bound for nondeterministic architectures in terms of properties of the corresponding distribution over fixed architectures.

•Dec 17, 2024•0 citations

Conditional t-independent spectral gap for random quantum circuits and implications for t-design depths

Allen, James, Daniel Belkin, Bryan K. Clark

A fundamental question is understanding the rate at which random quantum circuits converge to the Haar measure. One quantity which is important in establishing this rate is the spectral gap of a random quantum ensemble. In this work we establish a new bound on the spectral gap of the t-th moment of a one-dimensional brickwork architecture on N qudits. This bound is independent of both t and N, provided t does not exceed the qudit dimension q. We also show that the bound is nearly optimal. The improved spectral gaps gives large improvements to the constant factors in known results on the approximate t-design depths of the 1D brickwork, of generic circuit architectures, and of specially-constructed architectures which scramble in depth O(log N). We moreover show that the spectral gap gives the dominant epsilon-dependence of the t-design depth at small epsilon. Our spectral gap bound is obtained by bounding the N-site 1D brickwork architecture by the spectra of 3-site operators. We then exploit a block-triangular hierarchy and a global symmetry in these operators in order to efficiently bound them. The technical methods used are a qualitatively different approach for bounding spectral gaps and and have little in common with previous techniques.

arXiv:2411.13739•Nov 20, 2024•1 citation

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

Shallow Approximate Unitary Designs from Relative Entropy Decay of Unstructured Random Circuits

Nicholas D. LaRacuente

Approximate unitary k-designs are ensembles of unitary matrices whose first k statistical moments approximate the Haar (uniform) measure. Shallow, random quantum circuits with temporally and spatially structured architectures are known to yield approximate k-designs in depth that is logarithmic in the number of qubits. It was open whether this structure is physically necessary. Shown here is shallow relative entropy convergence for standard notions of less structured, time-periodic circuits, implying additive-error approximate k-designs in nearly logarithmic depth (up to sub-logarithmic factors). These architectures include 1-dimensional brickwork and gates placed randomly according to a connected, bounded-degree graph. Relative entropy recombination methods derived herein are potentially of independent interest.

arXiv:2510.08537•Oct 9, 2025•6 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

Local random quantum circuits form approximate designs on arbitrary architectures

Shivan Mittal, Nicholas Hunter-Jones

We consider random quantum circuits (RQC) on arbitrary connected graphs whose edges determine the allowed $2$-qudit interactions. Prior work has established that such $n$-qudit circuits with local dimension $q$ on 1D, complete, and $D$-dimensional graphs form approximate unitary designs, that is, they generate unitaries from distributions close to the Haar measure on the unitary group $U(q^n)$ after polynomially many gates. Here, we extend those results by proving that RQCs comprised of $O(\mathrm{poly}(n,k))$ gates on a wide class of graphs form approximate unitary $k$-designs. We prove that RQCs on graphs with spanning trees of bounded degree and height form $k$-designs after $O(|E|n\,\mathrm{poly}(k))$ gates, where $|E|$ is the number of edges in the graph. Furthermore, we identify larger classes of graphs for which RQCs generate approximate designs in polynomial circuit size. For $k \leq 4$, we show that RQCs on graphs of certain maximum degrees form designs after $O(|E|n)$ gates, providing explicit constants. We determine our circuit size bounds from the spectral gaps of local Hamiltonians. To that end, we extend the finite-size (or Knabe) method for bounding gaps of frustration-free Hamiltonians on regular graphs to arbitrary connected graphs. We further introduce a new method based on the Detectability Lemma for determining the spectral gaps of Hamiltonians on arbitrary graphs. Our methods have wider applicability as the first method provides a succinct alternative proof of [Commun. Math. Phys. 291, 257 (2009)] and the second method proves that RQCs on any connected architecture form approximate designs in quasi-polynomial circuit size.

arXiv:2310.19355•Oct 30, 2023•29 citations
Unitary t -designs are distributions on the unitary group whose first t moments appear maximally random. Previous work has established several upper bounds on the depths at which certain specific random quantum circuit ensembles approximate t -designs. Here we show that these bounds can be extended to any fixed architecture of Haar-random two-site gates. This is accomplished by relating the spectral gaps of such architectures to those of one-dimensional brickwork architectures. Our bound depends on the details of the architecture only via the typical number of layers needed for a block of the circuit to form a connected graph over the sites. When this quantity is bounded, the circuit forms an approximate t -design in at most linear depth. We give numerical evidence for a stronger bound that depends only on the number of connected blocks into which the architecture can be divided. We also give an implicit bound for nondeterministic architectures in terms of properties of the corresponding distribution over fixed architectures. Published by the American Physical Society 2024
Unitary 𝑡-designs are distributions on the unitary group whose first 𝑡 moments appear maximally random. Previous work has established several upper bounds on the depths at which certain specific random quantum circuit ensembles approximate 𝑡-designs. Here we show that these bounds can be extended to any fixed architecture of Haar-random two-site gates. This is accomplished by relating the spectral gaps of such architectures to those of one-dimensional brickwork architectures. Our bound depends on the details of the architecture only via the typical number of layers needed for a block of the circuit to form a connected graph over the sites. When this quantity is bounded, the circuit forms an approximate 𝑡-design in at most linear depth. We give numerical evidence for a stronger bound that depends only on the number of connected blocks into which the architecture can be divided. We also give an implicit bound for nondeterministic architectures in terms of properties of the corresponding distribution over fixed architectures.
A fundamental question is understanding the rate at which random quantum circuits converge to the Haar measure. One quantity which is important in establishing this rate is the spectral gap of a random quantum ensemble. In this work we establish a new bound on the spectral gap of the t-th moment of a one-dimensional brickwork architecture on N qudits. This bound is independent of both t and N, provided t does not exceed the qudit dimension q. We also show that the bound is nearly optimal. The improved spectral gaps gives large improvements to the constant factors in known results on the approximate t-design depths of the 1D brickwork, of generic circuit architectures, and of specially-constructed architectures which scramble in depth O(log N). We moreover show that the spectral gap gives the dominant epsilon-dependence of the t-design depth at small epsilon. Our spectral gap bound is obtained by bounding the N-site 1D brickwork architecture by the spectra of 3-site operators. We then exploit a block-triangular hierarchy and a global symmetry in these operators in order to efficiently bound them. The technical methods used are a qualitatively different approach for bounding spectral gaps and and have little in common with previous techniques.
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.
Approximate unitary k-designs are ensembles of unitary matrices whose first k statistical moments approximate the Haar (uniform) measure. Shallow, random quantum circuits with temporally and spatially structured architectures are known to yield approximate k-designs in depth that is logarithmic in the number of qubits. It was open whether this structure is physically necessary. Shown here is shallow relative entropy convergence for standard notions of less structured, time-periodic circuits, implying additive-error approximate k-designs in nearly logarithmic depth (up to sub-logarithmic factors). These architectures include 1-dimensional brickwork and gates placed randomly according to a connected, bounded-degree graph. Relative entropy recombination methods derived herein are potentially of independent interest.
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.
We consider random quantum circuits (RQC) on arbitrary connected graphs whose edges determine the allowed 222-qudit interactions. Prior work has established that such nnn-qudit circuits with local dimension qqq on 1D, complete, and DDD-dimensional graphs form approximate unitary designs, that is, they generate unitaries from distributions close to the Haar measure on the unitary group U(qn)U(q^n)U(qn) after polynomially many gates. Here, we extend those results by proving that RQCs comprised of O(poly(n,k))O(\mathrm{poly}(n,k))O(poly(n,k)) gates on a wide class of graphs form approximate unitary kkk-designs. We prove that RQCs on graphs with spanning trees of bounded degree and height form kkk-designs after O(∣E∣n poly(k))O(|E|n\,\mathrm{poly}(k))O(∣E∣npoly(k)) gates, where ∣E∣|E|∣E∣ is the number of edges in the graph. Furthermore, we identify larger classes of graphs for which RQCs generate approximate designs in polynomial circuit size. For k≤4k \leq 4k≤4, we show that RQCs on graphs of certain maximum degrees form designs after O(∣E∣n)O(|E|n)O(∣E∣n) gates, providing explicit constants. We determine our circuit size bounds from the spectral gaps of local Hamiltonians. To that end, we extend the finite-size (or Knabe) method for bounding gaps of frustration-free Hamiltonians on regular graphs to arbitrary connected graphs. We further introduce a new method based on the Detectability Lemma for determining the spectral gaps of Hamiltonians on arbitrary graphs. Our methods have wider applicability as the first method provides a succinct alternative proof of [Commun. Math. Phys. 291, 257 (2009)] and the second method proves that RQCs on any connected architecture form approximate designs in quasi-polynomial circuit size.