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:2002.09524 · Communications in Mathematical Physics

Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates

Jonas Haferkamp, Felipe Montealegre‐Mora, Markus Heinrich, Jens Eisert, D. Gross, Ingo Roth

Published Nov 12, 2022• 114 citations
arXivHTMLPDF

Abstract

Abstract Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full n -qubit group, one often resorts to t -designs. Unitary t -designs mimic the Haar-measure up to t -th moments. It is known that Clifford operations can implement at most 3-designs. In this work, we quantify the non-Clifford resources required to break this barrier. We find that it suffices to inject $$O(t^{4}\log ^{2}(t)\log (1/\varepsilon ))$$ O ( t 4 log 2 ( t ) log ( 1 / ε ) ) many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an $$\varepsilon $$ ε -approximate t -design. Strikingly, the number of non-Clifford gates required is independent of the system size – asymptotically, the density of non-Clifford gates is allowed to tend to zero. We also derive novel bounds on the convergence time of random Clifford circuits to the t -th moment of the uniform distribution on the Clifford group. Our proofs exploit a recently developed variant of Schur-Weyl duality for the Clifford group, as well as bounds on restricted spectral gaps of averaging operators.

DOI
10.1007/s00220-022-04507-6

Related papers

Non-Clifford Cost of Random Unitaries

Lorenzo Leone, Salvatore F. E. Oliviero, Alioscia Hamma +2 more

Recent years have enjoyed a strong interest in exploring properties and applications of random quantum circuits. In this work, we explore the ensemble of t -doped Clifford circuits on n qubits, consisting of Clifford circuits interspersed with t single-qubit non-Clifford gates. We establish rigorous convergence bounds toward unitary k -designs, revealing the intrinsic cost in terms of non-Clifford resources in various flavors. First, we analyze the k th order frame potential, which quantifies how well the ensemble of doped Clifford circuits is spread within the unitary group. We prove that a quadratic doping level, t = Θ ~ ( k 2 ) , is both necessary and sufficient to approximate the frame potential of the full unitary group. As a consequence, we refine existing upper bounds on the convergence of the ensemble toward state k -designs. Second, we derive tight bounds on the convergence of t -doped Clifford circuits toward relative-error k -designs, showing that t = Θ ~ ( n k ) is both necessary and sufficient for the ensemble to form a relative ε -approximate k -design. Similarly, t = Θ ~ ( n ) is required to generate pseudorandom unitaries. All these results highlight that generating random unitaries is extremely costly in terms of non-Clifford resources, and that such ensembles fundamentally lie beyond the classical simulability barrier. Additionally, we analyze high-order doped-Clifford-Weingarten functions to derive analytic expressions for the twirling operator over the ensemble of random doped Clifford circuits, and we establish their asymptotic behavior in relevant regimes.

arXiv:2505.10110•PRX Quantum•Feb 3, 2026•22 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•3 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

Adaptively Secure Unitary Designs with Constant Non-Clifford Cost

Lennart Bittel, Lorenzo Leone

Randomness is a fundamental resource in quantum information, with crucial applications in cryptography, algorithms, and error correction. A central challenge is to construct unitary k designs that closely approximate Haar-random unitaries while minimizing the costly use of non-Clifford operations. In this Letter, we present a protocol able to generate unitary k designs on n qubits, secure against any adversarial quantum measurement, with a system-size-independent number of non-Clifford gates. Our construction applies a k design only to a subsystem of size Θ(k), independent of n. This "seed" design is then "diluted" across the entire n-qubit system by sandwiching it between two random Clifford operators. The resulting ensemble forms an ϵ-approximate unitary k design on n qubits. We prove that this construction achieves full quantum security against adaptive adversaries using only O[over ˜](k^{2}logϵ^{-1}) non-Clifford gates. If one requires security only against polynomial-time adaptive adversaries, the non-Clifford cost decreases to O[over ˜](k+log^{1+c}ϵ^{-1}). This is optimal, since we show that at least Ω(k) non-Clifford gates are required in this setting. Compared to existing approaches, our method significantly reduces non-Clifford overhead while strengthening security guarantees to adaptive security as well as removing artificial assumptions between n and k. These results make high-order unitary designs practically attainable in near-term fault-tolerant quantum architectures.

arXiv:2510.08129•Physical Review Letters•Apr 3, 2026•1 citation

Exact and Approximate Unitary 2-Designs: Constructions and Applications

Dankert, Christoph, Cleve, Richard, Joseph Emerson +1 more

We consider an extension of the concept of spherical t-designs to the unitary group in order to develop a unified framework for analyzing the resource requirements of randomized quantum algorithms. We show that certain protocols based on twirling require a unitary 2-design. We describe an efficient construction for an exact unitary 2-design based on the Clifford group, and then develop a method for generating an epsilon-approximate unitary 2-design that requires only O(n log(1/epsilon)) gates, where n is the number of qubits and epsilon is an appropriate measure of precision. These results lead to a protocol with exponential resource savings over existing experimental methods for estimating the characteristic fidelities of physical quantum processes.

•Jun 20, 2006•10 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
Abstract Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full n -qubit group, one often resorts to t -designs. Unitary t -designs mimic the Haar-measure up to t -th moments. It is known that Clifford operations can implement at most 3-designs. In this work, we quantify the non-Clifford resources required to break this barrier. We find that it suffices to inject O(t4log⁡2(t)log⁡(1/ε))O(t^{4}\log ^{2}(t)\log (1/\varepsilon ))O(t4log2(t)log(1/ε)) O ( t 4 log 2 ( t ) log ( 1 / ε ) ) many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an ε\varepsilon ε ε -approximate t -design. Strikingly, the number of non-Clifford gates required is independent of the system size – asymptotically, the density of non-Clifford gates is allowed to tend to zero. We also derive novel bounds on the convergence time of random Clifford circuits to the t -th moment of the uniform distribution on the Clifford group. Our proofs exploit a recently developed variant of Schur-Weyl duality for the Clifford group, as well as bounds on restricted spectral gaps of averaging operators.
Recent years have enjoyed a strong interest in exploring properties and applications of random quantum circuits. In this work, we explore the ensemble of t -doped Clifford circuits on n qubits, consisting of Clifford circuits interspersed with t single-qubit non-Clifford gates. We establish rigorous convergence bounds toward unitary k -designs, revealing the intrinsic cost in terms of non-Clifford resources in various flavors. First, we analyze the k th order frame potential, which quantifies how well the ensemble of doped Clifford circuits is spread within the unitary group. We prove that a quadratic doping level, t = Θ ~ ( k 2 ) , is both necessary and sufficient to approximate the frame potential of the full unitary group. As a consequence, we refine existing upper bounds on the convergence of the ensemble toward state k -designs. Second, we derive tight bounds on the convergence of t -doped Clifford circuits toward relative-error k -designs, showing that t = Θ ~ ( n k ) is both necessary and sufficient for the ensemble to form a relative ε -approximate k -design. Similarly, t = Θ ~ ( n ) is required to generate pseudorandom unitaries. All these results highlight that generating random unitaries is extremely costly in terms of non-Clifford resources, and that such ensembles fundamentally lie beyond the classical simulability barrier. Additionally, we analyze high-order doped-Clifford-Weingarten functions to derive analytic expressions for the twirling operator over the ensemble of random doped Clifford circuits, and we establish their asymptotic behavior in relevant regimes.
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 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.
Randomness is a fundamental resource in quantum information, with crucial applications in cryptography, algorithms, and error correction. A central challenge is to construct unitary k designs that closely approximate Haar-random unitaries while minimizing the costly use of non-Clifford operations. In this Letter, we present a protocol able to generate unitary k designs on n qubits, secure against any adversarial quantum measurement, with a system-size-independent number of non-Clifford gates. Our construction applies a k design only to a subsystem of size Θ(k), independent of n. This "seed" design is then "diluted" across the entire n-qubit system by sandwiching it between two random Clifford operators. The resulting ensemble forms an ϵ-approximate unitary k design on n qubits. We prove that this construction achieves full quantum security against adaptive adversaries using only O[over ˜](k^{2}logϵ^{-1}) non-Clifford gates. If one requires security only against polynomial-time adaptive adversaries, the non-Clifford cost decreases to O[over ˜](k+log^{1+c}ϵ^{-1}). This is optimal, since we show that at least Ω(k) non-Clifford gates are required in this setting. Compared to existing approaches, our method significantly reduces non-Clifford overhead while strengthening security guarantees to adaptive security as well as removing artificial assumptions between n and k. These results make high-order unitary designs practically attainable in near-term fault-tolerant quantum architectures.
We consider an extension of the concept of spherical t-designs to the unitary group in order to develop a unified framework for analyzing the resource requirements of randomized quantum algorithms. We show that certain protocols based on twirling require a unitary 2-design. We describe an efficient construction for an exact unitary 2-design based on the Clifford group, and then develop a method for generating an epsilon-approximate unitary 2-design that requires only O(n log(1/epsilon)) gates, where n is the number of qubits and epsilon is an appropriate measure of precision. These results lead to a protocol with exponential resource savings over existing experimental methods for estimating the characteristic fidelities of physical quantum processes.
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.