Source-linked AI summary
Efficient unitary designs with a system-size independent number of non-Clifford gates
Jonas Haferkamp, Felipe Montealegre-Mora, Markus Heinrich, Jens Eisert, David Gross, Ingo Roth
TL;DR
The paper asks how approximate unitary t-designs can be constructed with few non-Clifford gates. It analyzes circuits that interleave Clifford operations with non-Clifford gates and establishes bounds for unitary designs and local random Clifford designs.
Problem
The paper asks how many non-Clifford gates are required to generate an approximate unitary t-design.
Source: §III · p. 10Method
The analysis relates local random Clifford moment operators to the Clifford commutant and uses the resulting structure to study convergence.
Source: §IV · p. 17Results
A K-interleaved Clifford circuit is an additive ε-approximate t-design at depth k ≥ C1(K) log2(t)(t4 + t log(1/ε)) for n ≥ C2(K)t2.
Source: §III · p. 10Takeaways & Limitations
A number of non-Clifford gates independent of system size suffices to generate ε-approximate unitary t-designs.
Source: §VII · p. 37
Abstract
from arXiv · showhide
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))$ 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.
I. RESULTS
The paper shows that interleaving random Clifford layers with non-Clifford gates yields approximate unitary designs, and bounds how local random Clifford circuits approach Clifford designs. It gives both a system-size-independent non-Clifford gate count and a local-circuit construction.
A. Approximate t-designs with few non-Clifford gates
- A K-interleaved Clifford circuit is an additive ε-approximate t-design at depth k ≥ C1(K) log2(t)(t4 + t log(1/ε)), for n ≥ C2(K)t2.The model alternates uniformly drawn Clifford unitaries with random choices from {K, K†, 1}; K is a fixed single-qubit non-Clifford gate.Source: A. Approximate t-designs with few… · p. 3
- The construction uses O(n2/log(n) t4 log2(t)) total gates when uniformly sampled multiqubit Clifford unitaries are compiled, improving the stated scaling in both n and t over Ref..The authors describe this as a classical-quantum hybrid construction that outsources tasks to a classical computer.Source: A. Approximate t-designs with few… · p. 4
- The proof combines bounds on Haar-operator overlaps with stochastic Lagrangian subspaces, restricted spectral gaps, and a Gram-Schmidt argument to bound diamond-norm distance to a unitary t-design.The non-Clifford gates strongly affect representations of Lagrangian subspaces that are not also permutations.Source: A. Approximate t-designs with few… · p. 4
- Haar-interleaved Clifford circuits form additive ε-approximate t-designs for k ≥ 36(33t4 + 3t log(1/ε)) and n ≥ 32t2 + 7.The text also states that variants of the relative-design corollary for this model avoid the log2(t) dependence.Source: A. Approximate t-designs with few… · p. 5
B. Local random Clifford circuits for Clifford and unitary designs
- Local random Clifford circuits of depth O(n log−2(t)t8(2nt + log(1/ε))) are relative ε-approximate Clifford t-designs when n ≥ 12t.A 2-local circuit over a finite closed generating set is used; the stated result improves on the scaling O(n8) implicit in Ref..Source: B. Local random Clifford circuits for… · pp. 5–6
- Alternating local random Clifford circuits with non-Clifford gates yields an ε-approximate unitary t-design under the conditions of Corollary 2.This local-circuit construction is presented as combining the local Clifford-design bounds with the earlier bounds for interleaved circuits.Source: B. Local random Clifford circuits for… · p. 6
A. Operators and superoperators
This section sets notation for operators and maps on operators, then specifies the norms used to compare them.
A. Operators and superoperators
- The space L(H) of linear operators on a finite-dimensional Hilbert space inherits the Hilbert-Schmidt inner product.The adjoint † is defined with respect to the inner product on H.Source: A. Operators and superoperators · p. 6
- Operator-ket notation identifies |B) with B, while (A| denotes a linear form on L(H).A rank-one superoperator can be written |A)(B|, with adjoint |B)(A|.Source: A. Operators and superoperators · p. 6
- Linear maps from L(H) to itself are called superoperators, and AdA denotes the adjoint action A · A−1 for invertible A.The text also uses Ad(A) as an alternative notation.Source: A. Operators and superoperators · p. 6
- The section uses Schatten norms for operators and superoperators, including trace, Hilbert-Schmidt, and spectral norms, as well as induced and stabilized norms.It notes that ∥·∥2→2 equals ∥·∥∞ and identifies the diamond norm as a stabilized induced norm of interest.Source: A. Operators and superoperators · p. 7
B. Commutant of the diagonal representation of the Clifford group
The section describes a basis for the Clifford commutant using stochastic Lagrangian subspaces and related defect-subspace constructions.
B. Commutant of the diagonal representation of the Clifford group
- The subspaces T ∈ Σt,t are totally q-isotropic, have dimension t, and satisfy the stochastic condition.Here q(x,y) = x · x − y · y mod 4, and stochasticity means the all-ones vector belongs to T.Source: B. Commutant of the diagonal… · pp. 7–8
- For n ≥ t−1, the commutant of the Clifford group's t-th diagonal representation is spanned by linearly independent operators r(T)⊗n indexed by T ∈ Σt,t.These T are called stochastic Lagrangian subspaces.Source: B. Commutant of the diagonal… · p. 8
- A defect subspace N is isotropic for q; it is contained in N⊥ and therefore has dimension at most t/2.Such subspaces define CSS codes.Source: B. Commutant of the diagonal… · pp. 8–9
- The operators r(T) can be expressed using a stochastic orthogonal transformation and a projector associated with a defect subspace.The text gives the form 2^dim N r(O)P_N and relates the defect subspace to the CSS-code projector.Source: B. Commutant of the diagonal… · p. 9
III. APPROXIMATE UNITARY t-DESIGNS
The section proves that interleaving a random Clifford circuit with a system-size-independent number of non-Clifford gates suffices for an additive approximate unitary t-design. It establishes this through bounds on overlaps and a constructed orthogonal basis for the Clifford commutant.
III. APPROXIMATE UNITARY t-DESIGNS
- k ≥ C1(K) log^2(t)(t^4 + t log(1/ε)) interleaved steps suffice for an additive ε-approximate t-design when n ≥ C2(K)t^2.Theorem 1 assumes a single-qubit non-Clifford unitary K.Source: §III · p. 10
- For T gates, the interleaving distribution must retain a nonzero chance of applying the identity for the overlap-bound proof.The paper notes this assumption can be dropped for gates that do not square to a Clifford gate.Source: §III · p. 10
- The proof constructs an orthogonal basis of the Clifford commutant because the factorizing basis used there is non-orthogonal.The range of PCl − PH is described using permutation operators, and Gram–Schmidt supplies a suitable orthonormal basis.Source: §III · p. 11
IV. CONVERGENCE TO HIGHER MOMENTS OF THE CLIFFORD GROUP
The section bounds how quickly local random Clifford circuits approximate higher moments of the uniform Clifford distribution. It derives a spectral-gap estimate and uses it to establish a relative approximate Clifford t-design depth bound.
IV. CONVERGENCE TO HIGHER MOMENTS OF THE CLIFFORD GROUP
- For n ≥ 12t, depth O(n log^-2(t)t^8(2nt + log(1/ε))) gives a relative ε-approximate Clifford t-design.This is the stated local random Clifford circuit bound.Source: §IV · p. 16
- A bound on deviation from the Clifford moment operator implies a relative approximate Clifford t-design, with the error rescaled by 2^2tn.The implication is stated for 0 ≤ ε < 1.Source: §IV · p. 16
- The local random Clifford averaging operator has deviation gCl(σG, t) ≤ 1 − c(G)n^-1 log^2(t)t^-8 for n ≥ 12t.The constant c(G) is positive and depends on the generating set.Source: §IV · p. 16
- The proof converts spectral-gap bounds into convergence using a frustration-free Hamiltonian whose ground space is the Clifford commutant.The paper applies the martingale method to establish a uniform lower bound on the gap when n ≥ 12t.Source: §IV · p. 18
V. SINGLING OUT THE CLIFFORD GROUP
The section combines prior classification and universality results to characterize finite gate sets that generate unitary t-designs across system sizes. Under its stated assumptions, the Clifford group is singled out at lower design orders, while orders t ≥ 4 require dense generated groups.
V. SINGLING OUT THE CLIFFORD GROUP
- For t = 2, the stated alternatives include q prime with Gn isomorphic to a subgroup of the Clifford group, or Gn dense in SU(q^n).The classification draws on the cited results of Bannai et al., Guralnick and Tiep, and Sawicki and Karnas.Source: §V · p. 20
- For t = 3, the stated alternatives are q = 2 with Gn isomorphic to the full Clifford group, or Gn dense in SU(q^n).The alternatives apply under Proposition 3’s assumptions.Source: §V · p. 20
- For t ≥ 4, the generated groups Gn are dense in SU(q^n) under the proposition’s assumptions.The proposition assumes a finite gate set and that Gn are either all finite or all infinite, with Gn forming a unitary t-design for all sufficiently large n.Source: §V · p. 20
A. Proof of overlap lemmas
The overlap lemmas bound relationships among stochastic Lagrangian subspaces and use those bounds to control the Clifford frame operator. They also distinguish spectral-norm closeness from diamond-norm closeness.
A. Proof of overlap lemmas
- The Clifford frame operator is close to the projector onto the Clifford commutant in spectral norm.The text identifies this comparison as a step used later in the proof.Source: A. Proof of overlap lemmas · pp. 23–24
- The frame operator is not close to the commutant projector in diamond norm, so the proof constructs an orthogonalized basis instead.The constructed basis is obtained from the tensor-power basis.Source: A. Proof of overlap lemmas · p. 23
- The overlap lemma establishes nonnegative overlaps and gives a sum bound under n + 2 ≥ t + log2(t).The sum is over overlaps involving each stochastic Lagrangian subspace.Source: A. Proof of overlap lemmas · p. 23
B. Proof of Lemmas for Theorem 1
The proof bounds how a non-Clifford gate changes moment operators and constructs an orthogonal basis for the Clifford commutant. Haar symmetrization and overlap estimates supply the bounds used in the argument.
B. Proof of Lemmas for Theorem 1
- Clifford-commutant basis elements either lie in the unitary-group commutant or are far from it, supporting the overlap estimate.The constructed {Ej} form an orthogonal, unnormalized basis.Source: B. Proof of Lemmas for Theorem 1 · pp. 24, 27
- The overlap-bound constant 7/8 cannot be improved below 7/10, since an example T attains that bound.The paper gives the tightness analysis in Appendix C.Source: B. Proof of Lemmas for Theorem 1 · p. 25
- The moment-operator argument uses a universal measure whose restricted gaps are nonzero to obtain a positive gate-dependent bound c(K).The measure combines a uniform average over {H, S, S3} with ξK * ξK, where ξK samples {K, K†, 1}.Source: B. Proof of Lemmas for Theorem 1 · pp. 25–26
- For gates K with algebraic entries, the scaling can omit the additional log^2(t) overhead; this includes the T gate.The authors use a more general approach in the paper.Source: B. Proof of Lemmas for Theorem 1 · p. 26
C. Proof of Haar symmetrization Lemma 13
Haar symmetrization bounds overlaps by a discrete probability: whether components of a uniformly sampled stochastic Lagrangian have equal Hamming weight. The proof treats trivial and non-trivial defect spaces separately.
C. Proof of Haar symmetrization Lemma 13
- For non-trivial defect spaces, the overlap is bounded by the probability that a uniformly sampled element has components of equal Hamming weight, yielding an upper bound of 7/8.The proof uses the invariance of the uniform distribution under adding elements of the defect subspace.Source: C. Proof of Haar symmetrization Lemma 13 · pp. 30, 32
- For trivial defect spaces, the proof represents T as {(Oy, y)} and bounds weight preservation using the column weight r of O.The stated bound is 0 for even r; for orthogonal stochastic matrices the smallest non-trivial r is 5, giving 0.81.Source: C. Proof of Haar symmetrization Lemma 13 · p. 30
- For a non-trivial defect-space form with the stated coordinate structure, adding n changes both Hamming weights by ±1, so equal weights occur with probability zero.The first t−d components of a uniform vector from N⊥ are uniform, which supports the coordinate argument.Source: C. Proof of Haar symmetrization Lemma 13 · p. 32
D. Proof of Lemmas for Theorem 2
The proof converts a moment-operator gap condition into a relative approximate Clifford-design guarantee, then bounds the relevant Hamiltonian gap using local spectral-gap methods. The gap bound assumes n ≥ 12t.
D. Proof of Lemmas for Theorem 2
- If gCl(ν, t) ≤ ε, then ν is a relative ε2^(2tn)-approximate Clifford t-design.Source: D. Proof of Lemmas for Theorem 2 · p. 33
- The nontrivial condition in the local-gap argument requires ground-space structure, which the paper identifies through the Clifford commutant.The proof relates the ground-space projector to the Clifford projector and approximates it using the Clifford frame operator.Source: D. Proof of Lemmas for Theorem 2 · p. 35
- For n ≥ 12t, the Hamiltonian Hn,t has a spectral gap bounded below by the stated estimate.The proof invokes Nachtergaele’s lemma and verifies its conditions for the translation-invariant local Hamiltonian.Source: D. Proof of Lemmas for Theorem 2 · pp. 35, 37
VII. SUMMARY AND OPEN QUESTIONS
The paper establishes that system-size-independent non-Clifford gate counts suffice for additive-error designs, while identifying open questions about scaling and scope. The main boundaries concern the condition n = O(t^2), relative-error guarantees, and extension to qudits.
VII. SUMMARY AND OPEN QUESTIONS
- The construction’s scaling in t may be improvable, although its scaling in n is near optimal.The authors leave improved t-scaling as an open direction.Source: §VII · p. 37
- The proof requires n = O(t^2), because approximate orthogonality of Lagrangian subspaces is established only in that regime.The authors suspect the bound may be tight but cannot rule out proofs that avoid approximate orthogonality.Source: §VII · p. 37
- The system-size-independent guarantee applies to additive errors in the diamond norm, whereas relative-error bounds are not system-size independent.For relative errors, the bounds yield a quadratic advantage in non-Clifford gate count, and Ref. proves that scaling optimal.Source: §VII · p. 37
- The authors expect analogous system-size independence for qudits of arbitrary dimension with additive diamond-norm errors.This is an expectation, not a result established in the paper.Source: §VII · p. 37
Appendix A: Unitary t-designs
The appendices connect unitary designs to moment operators and representation theory, examine the tightness of converse estimates, and apply the construction to higher Rényi entropies.
Appendix A: Unitary t-designs
- A probability measure is a unitary t-design when its moment operator matches Haar’s; for unitary t-groups, this is characterized by matching irreducible-representation decompositions.Finite designs use the normalized counting measure, and the moment condition can be expressed as equality of twirls.Source: Appendix A · pp. 38–39
Appendix B: Representations of the unitary group
- Highest weights label irreducible representations of U(d), and tensor-product highest weights are bounded by sums of the factors’ weights.The appendix illustrates this using the defining representation of U(2) and its complex conjugate.Source: Appendix B · p. 39
Appendix C: Converse bounds for estimates in Section VI C
- Proposition 5’s estimates are tight in stated examples, while the diagonal-matrix projection in Eq. (123) can fail to be tight.The authors show the failure for cases saturating the bounds in Propositions 4 and 5.Source: Appendix C · p. 40
Appendix D: Saturation of higher Rényi-entropies in K-interleaved Clifford circuits
- For constant subsystem size and Rényi order, the construction yields classically simulable circuit ensembles with essentially minimal average higher purities.The appendix chooses the design order equal to the Rényi order and specifies a corresponding K-interleaved circuit depth.Source: Appendix D · pp. 42–43