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

Local random quantum circuits form approximate designs on arbitrary architectures

Shivan Mittal, Nicholas Hunter-Jones

Published Oct 30, 2023• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2310.19355

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

Approximate t -Designs in Generic Circuit Architectures

Daniel Belkin, James Allen, Soumik Ghosh +6 more

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

arXiv:2310.19783•PRX Quantum•Dec 17, 2024•8 citations

Approximate Unitary t-Designs by Short Random Quantum Circuits Using Nearest-Neighbor and Long-Range Gates

Aram W. Harrow, Saeed Adel Mehraban

Abstract We prove that $${{\,\textrm{poly}\,}}(t) \cdot n^{1/D}$$ poly ( t ) · n 1 / D -depth local random quantum circuits with two qudit nearest-neighbor gates on a D -dimensional lattice with n qudits are approximate t -designs in various measures. These include the “monomial” measure, meaning that the monomials of a random circuit from this family have expectation close to the value that would result from the Haar measure. Previously, the best bound was $${{\,\textrm{poly}\,}}(t)\cdot n$$ poly ( t ) · n due to Brandão–Harrow–Horodecki (Commun Math Phys 346(2):397–434, 2016) for $$D=1$$ D = 1 . We also improve the “scrambling” and “decoupling” bounds for spatially local random circuits due to Brown and Fawzi (Scrambling speed of random quantum circuits, 2012). One consequence of our result is that assuming the polynomial hierarchy ( $${{\,\mathrm{\textsf{PH}}\,}}$$ PH ) is infinite and that certain counting problems are $$\#{\textsf{P}}$$ # P -hard “on average”, sampling within total variation distance from these circuits is hard for classical computers. Previously, exact sampling from the outputs of even constant-depth quantum circuits was known to be hard for classical computers under these assumptions. However the standard strategy for extending this hardness result to approximate sampling requires the quantum circuits to have a property called “anti-concentration”, meaning roughly that the output has near-maximal entropy. Unitary 2-designs have the desired anti-concentration property. Our result improves the required depth for this level of anti-concentration from linear depth to a sub-linear value, depending on the geometry of the interactions. This is relevant to a recent experiment by the Google Quantum AI group to perform such a sampling task with 53 qubits on a two-dimensional lattice (Arute in Nature 574(7779):505–510, 2019; Boixo et al. in Nate Phys 14(6):595–600, 2018) (and related experiments by USTC), and confirms their conjecture that $$O(\sqrt{n})$$ O ( n ) depth suffices for anti-concentration. The proof is based on a previous construction of t -designs by Brandão et al. (2016), an analysis of how approximate designs behave under composition, and an extension of the quasi-orthogonality of permutation operators developed by Brandão et al. (2016). Different versions of the approximate design condition correspond to different norms, and part of our contribution is to introduce the norm corresponding to anti-concentration and to establish equivalence between these various norms for low-depth circuits. For random circuits with long-range gates, we use different methods to show that anti-concentration happens at circuit size $$O(n\ln ^2 n)$$ O ( n ln 2 n ) corresponding to depth $$O(\ln ^3 n)$$ O ( ln 3 n ) . We also show a lower bound of $$\Omega (n \ln n)$$ Ω ( n ln n )

arXiv:1809.06957•Communications in Mathematical Physics•May 4, 2023•126 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

(Almost) quadruply optimal unitary designs in 1D

Guoding Liu, Jonas Helsen

We construct $n$-qubit approximate unitary $k$-designs in 1D systems, achieving circuit depth $O(\log(n/\varepsilon) + k\log k)$ with relative error $\varepsilon$ and requiring $O(nk\log k)$ magic gates. This matches existing lower bounds $Ω(\log(n/\varepsilon) + k)$ for circuit depth, and $\widetildeΩ(nk)$ for the required number of $T$ gates, up to a $\log k$ factor, achieving simultaneous near-optimality in all parameters. Our construction is based on a combination and refinement of two existing results. We reduce the required magic block size for breaking Clifford symmetries in the magic-augmented circuit construction of Zhang et al. from $O(k\log k)$ to $O(\log k)$. We also improve the breakthrough construction of Chen et al. to construct a generating set of 1D local constant-depth circuits for the unitary group with a constant spectral gap, making $O(\log k)$-local random unitaries realizable in depth $O(k\log k)$. As a by-product, we provide a constant-size 1D-local generating set for the Clifford group, which we expect to be of independent interest. Combining the two results with the gluing lemma, we prove the final result.

quant-pharXiv:2608.18650•Aug 20, 2026•0 citations

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
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.
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.
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
Abstract We prove that  poly (t)⋅n1/D{{\,\textrm{poly}\,}}(t) \cdot n^{1/D}poly(t)⋅n1/D poly ( t ) · n 1 / D -depth local random quantum circuits with two qudit nearest-neighbor gates on a D -dimensional lattice with n qudits are approximate t -designs in various measures. These include the “monomial” measure, meaning that the monomials of a random circuit from this family have expectation close to the value that would result from the Haar measure. Previously, the best bound was  poly (t)⋅n{{\,\textrm{poly}\,}}(t)\cdot npoly(t)⋅n poly ( t ) · n due to Brandão–Harrow–Horodecki (Commun Math Phys 346(2):397–434, 2016) for D=1D=1D=1 D = 1 . We also improve the “scrambling” and “decoupling” bounds for spatially local random circuits due to Brown and Fawzi (Scrambling speed of random quantum circuits, 2012). One consequence of our result is that assuming the polynomial hierarchy (  PH {{\,\mathrm{\textsf{PH}}\,}}PH PH ) is infinite and that certain counting problems are #P\#{\textsf{P}}#P # P -hard “on average”, sampling within total variation distance from these circuits is hard for classical computers. Previously, exact sampling from the outputs of even constant-depth quantum circuits was known to be hard for classical computers under these assumptions. However the standard strategy for extending this hardness result to approximate sampling requires the quantum circuits to have a property called “anti-concentration”, meaning roughly that the output has near-maximal entropy. Unitary 2-designs have the desired anti-concentration property. Our result improves the required depth for this level of anti-concentration from linear depth to a sub-linear value, depending on the geometry of the interactions. This is relevant to a recent experiment by the Google Quantum AI group to perform such a sampling task with 53 qubits on a two-dimensional lattice (Arute in Nature 574(7779):505–510, 2019; Boixo et al. in Nate Phys 14(6):595–600, 2018) (and related experiments by USTC), and confirms their conjecture that O(n)O(\sqrt{n})O(n​) O ( n ) depth suffices for anti-concentration. The proof is based on a previous construction of t -designs by Brandão et al. (2016), an analysis of how approximate designs behave under composition, and an extension of the quasi-orthogonality of permutation operators developed by Brandão et al. (2016). Different versions of the approximate design condition correspond to different norms, and part of our contribution is to introduce the norm corresponding to anti-concentration and to establish equivalence between these various norms for low-depth circuits. For random circuits with long-range gates, we use different methods to show that anti-concentration happens at circuit size O(nln⁡2n)O(n\ln ^2 n)O(nln2n) O ( n ln 2 n ) corresponding to depth O(ln⁡3n)O(\ln ^3 n)O(ln3n) O ( ln 3 n ) . We also show a lower bound of Ω(nln⁡n)\Omega (n \ln n)Ω(nlnn) Ω ( n ln n )
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 construct nnn-qubit approximate unitary kkk-designs in 1D systems, achieving circuit depth O(log⁡(n/ε)+klog⁡k)O(\log(n/\varepsilon) + k\log k)O(log(n/ε)+klogk) with relative error ε\varepsilonε and requiring O(nklog⁡k)O(nk\log k)O(nklogk) magic gates. This matches existing lower bounds Ω(log⁡(n/ε)+k)Ω(\log(n/\varepsilon) + k)Ω(log(n/ε)+k) for circuit depth, and Ω~(nk)\widetildeΩ(nk)Ω(nk) for the required number of TTT gates, up to a log⁡k\log klogk factor, achieving simultaneous near-optimality in all parameters. Our construction is based on a combination and refinement of two existing results. We reduce the required magic block size for breaking Clifford symmetries in the magic-augmented circuit construction of Zhang et al. from O(klog⁡k)O(k\log k)O(klogk) to O(log⁡k)O(\log k)O(logk). We also improve the breakthrough construction of Chen et al. to construct a generating set of 1D local constant-depth circuits for the unitary group with a constant spectral gap, making O(log⁡k)O(\log k)O(logk)-local random unitaries realizable in depth O(klog⁡k)O(k\log k)O(klogk). As a by-product, we provide a constant-size 1D-local generating set for the Clifford group, which we expect to be of independent interest. Combining the two results with the gluing lemma, we prove the final result.
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.