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

Non-Clifford Cost of Random Unitaries

Lorenzo Leone, Salvatore F. E. Oliviero, Alioscia Hamma, Jens Eisert, Lennart Bittel

Published Feb 3, 2026• 22 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/25v1-my1x

Related papers

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

Jonas Haferkamp, Felipe Montealegre‐Mora, Markus Heinrich +3 more

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.

arXiv:2002.09524•Communications in Mathematical Physics•Nov 12, 2022•114 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

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

Quantum Complexity and Chaos in Many-Qudit Doped Clifford Circuits

Beatrice Magni, Xhek Turkeshi

We investigate the emergence of quantum complexity and chaos in doped Clifford circuits acting on qudits of odd prime dimension d . Using doped Clifford Weingarten calculus and a replica tensor network formalism, we derive exact results and perform large-scale simulations in regimes challenging for tensor network and Pauli-based methods. We begin by analyzing generalized stabilizer entropies, computable magic monotones in many-qudit systems, and identify a dynamical phase transition in the doping rate, marking the breakdown of classical simulability and the onset of Haar-random behavior. The critical behavior is governed by the qudit dimension and the magic content of the non-Clifford gate. Using the qudit T -gate as a benchmark, we show that higher-dimensional qudits converge faster to Haar-typical stabilizer entropies. For qutrits ( d = 3 ), analytical predictions match numerics on brickwork circuits, showing that locality plays a limited role in magic spreading. We also examine anticoncentration and entanglement growth, showing that O ( log ⁡ N ) non-Clifford gates suffice for approximating Haar expectation values to precision ε , and relate antiflatness measures to stabilizer entropies in qutrit systems. Finally, we analyze out-of-time-order correlators and show that a finite density of non-Clifford gates is needed to induce chaos, with a sharp transition fixed by the local dimension, twice that of the magic transition. Altogether, these results establish a unified framework for diagnosing complexity in doped Clifford circuits and deepen our understanding of resource theories in multiqudit systems.

arXiv:2506.02127•Quantum•Dec 24, 2025•27 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

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
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.
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.
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.
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 investigate the emergence of quantum complexity and chaos in doped Clifford circuits acting on qudits of odd prime dimension d . Using doped Clifford Weingarten calculus and a replica tensor network formalism, we derive exact results and perform large-scale simulations in regimes challenging for tensor network and Pauli-based methods. We begin by analyzing generalized stabilizer entropies, computable magic monotones in many-qudit systems, and identify a dynamical phase transition in the doping rate, marking the breakdown of classical simulability and the onset of Haar-random behavior. The critical behavior is governed by the qudit dimension and the magic content of the non-Clifford gate. Using the qudit T -gate as a benchmark, we show that higher-dimensional qudits converge faster to Haar-typical stabilizer entropies. For qutrits ( d = 3 ), analytical predictions match numerics on brickwork circuits, showing that locality plays a limited role in magic spreading. We also examine anticoncentration and entanglement growth, showing that O ( log ⁡ N ) non-Clifford gates suffice for approximating Haar expectation values to precision ε , and relate antiflatness measures to stabilizer entropies in qutrit systems. Finally, we analyze out-of-time-order correlators and show that a finite density of non-Clifford gates is needed to induce chaos, with a sharp transition fixed by the local dimension, twice that of the magic transition. Altogether, these results establish a unified framework for diagnosing complexity in doped Clifford circuits and deepen our understanding of resource theories in multiqudit systems.
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.
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.