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.
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(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 ε ε -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 n-qubit approximate unitary k-designs in 1D systems, achieving circuit depth O(log(n/ε)+klogk) with relative error ε and requiring O(nklogk) magic gates. This matches existing lower bounds Ω(log(n/ε)+k) for circuit depth, and Ω(nk) for the required number of T gates, up to a logk 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(klogk) to 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(logk)-local random unitaries realizable in depth 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.
Random unitaries are useful in quantum information and related fields but hard to generate with limited resources. An approximate unitary k-design is a measure over an ensemble of unitaries such that the average is close to a Haar (uniformly) random ensemble up to the first k moments. A strong notion of approximation bounds the distance from Haar randomness in relative error: the weighted twirl induced by an approximate design can be written as a convex combination involving that of an exact design and vice versa. The main focus of our work is on efficient constructions of approximate designs, in particular whether relative-error designs in sublinear depth are possible. We give a positive answer to this question as part of our main results: 1. Twirl-Swap-Twirl: Let A and B be systems of the same size. Consider a protocol that locally applies k-design unitaries to A^k and B^k respectively, then exchanges l qudits between each copy of A and B respectively, then again applies local k-design unitaries. This protocol yields an ε-approximate relative k-design when l = O(k log k + log(1/ε)). In particular, this bound is independent of the size of A and B as long as it is sufficiently large compared to k and 1/ε. 2. Twirl-Crosstwirl: Let A_1, … , A_P be subsystems of a multipartite system A. Consider the following protocol for k copies of A: (1) locally apply a k-design unitary to each A_p for p = 1, … , P; (2) apply a "crosstwirl" k-design unitary across a joint system combining l qudits from each A_p. Assuming each A_p’s dimension is sufficiently large compared to other parameters, one can choose l to be of the form 2 (Pk + 1) log_q k + log_q P + log_q(1/ε) + O(1) to achieve an ε-approximate relative k-design. As an intermediate step, we show that this protocol achieves a k-tensor-product-expander, in which the approximation error is in 2 → 2 norm, using communication logarithmic in k. 3. Recursive Crosstwirl: Consider an m-qudit system with connectivity given by a lattice in spatial dimension D. For every D = 1, 2, …, we give a construction of an ε-approximate relative k-design using unitaries of spatially local circuit depth O ((log m + log(1/ε) + k log k ) k polylog(k)). Moreover, across the boundaries of spatially contiguous sub-regions, unitaries used in the design ensemble require only area law communication up to corrections logarithmic in m. Hence they generate only that much entanglement on any product state input. These constructions use the alternating projection method to analyze overlapping Haar twirls, giving a bound on the convergence speed to the full twirl with respect to the 2-norm. Using von Neumann subalgebra indices to replace system dimension, the 2-norm distance converts to relative error without introducing system size. The Recursive Crosstwirl construction answers one variant of [Harrow and Mehraban, 2023, Open Problem 1], showing that with a specific, layered architecture, random circuits produce relative error k-designs in sublinear depth. Moreover, it addresses [Harrow and Mehraban, 2023, Open Problem 7], showing that structured circuits in spatial dimension D of depth << m^{1/D} may achieve approximate k-designs.
Constructing ensembles of circuits which efficiently approximate the Haar measure over various groups is a long-standing and fundamental problem in quantum information theory. Recently it was shown that one can obtain approximate designs over the unitary group with depths scaling logarithmically in the number of qubits, but that no sublinear-depth approximate designs exist over the orthogonal group. Here we derive, for any group G possessing an invariant state G⊗k∣Ψ⟩=∣Ψ⟩, a lower bound on the diamond distance between the k\textsuperscript{th} moment operator of any ensemble of elements of G, and that of the Haar measure over G. We then use this bound to prove that for many groups of interest, no subset of G consisting of sublinear-depth one-dimensional circuits with local gates can form an approximate k-design over G. More generally, on a D-dimensional lattice, our results imply that such group designs require depths scaling at least as n1/D. Moreover, for most of the groups we consider we find that such ensembles can, with high probability, be distinguished from k-designs by a single shot of a constant-depth measurement. Among other examples, we show that there is a constant separation between (a) the maximum depth and gate count for which no circuit can approximate even the second moment of random matchgate circuits, and (b) the depth and gate count required to implement the matchgate Haar distribution exactly. We furthermore rule out the existence of sublinear-depth 8-designs over the Clifford group. Finally, we relax the assumption of working with local gates, and prove the impossibility of obtaining approximate designs over G using any circuit comprised of a sublinear number of gates generated by Pauli strings.