Efficient unitary designs with a system-size independent number of non-Clifford gates

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/\epsilon ))$ many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an $\epsilon$-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.

v3: version published in Communications in Mathematical Physics, title changed; v2: improved presentation, added consequences of the main result and fixed typos; 46 pages, 1 figure

References in corpus (11)

• Black holes as mirrors: quantum information in random subsystems
• Randomized Benchmarking of Quantum Gates
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Evenly distributed unitaries: on the structure of unitary designs
• Linear growth of quantum circuit complexity
• Optimizing quantum process tomography with unitary 2-designs
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Models of quantum complexity growth
• Quantum Chaos is Quantum
• Isospectral twirling and quantum chaos
• Unitary $t$-designs from $relaxed$ seeds

Cited by in corpus (39)

• Scalable measures of magic resource for quantum computers
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Thrifty shadow estimation: re-using quantum circuits and bounding tails
• Magic-induced computational separation in entanglement theory
• Magic of quantum hypergraph states
• Magic Resources of the Heisenberg Picture
• Black holes as clouded mirrors: the Hayden-Preskill protocol with symmetry
• Probing quantum complexity via universal saturation of stabilizer entropies
• Efficient mutual magic and magic capacity with matrix product states
• Spectral Properties Versus Magic Generation in $T$-doped Random Clifford Circuits
• Benchmarking quantum gates and circuits
• Bridging Entanglement and Magic Resources within Operator Space
• Entanglement phase diagrams from partial transpose moments
• Absence of localization in two-dimensional Clifford circuits
• Quantum and Classical Dynamics with Random Permutation Circuits
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
• Disentangling magic states with classically simulable quantum circuits
• Low-depth random Clifford circuits for quantum coding against Pauli noise using a tensor-network decoder
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Quantifying multiparticle entanglement with randomized measurements
• Designs from magic-augmented Clifford circuits
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• On the Computational Hardness of Quantum One-Wayness
• Efficient approximate unitary designs from random Pauli rotations
• Non-Clifford Cost of Random Unitaries
• Architectures and random properties of symplectic quantum circuits
• Single-copy stabilizer testing
• Randomized measurements for multi-parameter quantum metrology
• Information scrambling in quantum walks: Discrete-time formulation of Krylov complexity
• On Computational Complexity of Unitary and State Design Properties
• Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudo-Magic States
• Bridging Classical and Quantum Information Scrambling with the Operator Entanglement Spectrum
• Error Crafting in Mixed Quantum Gate Synthesis
• Adaptively secure unitary designs with constant non-Clifford cost
• Convexity of noncontextual wirings and how they order the set of correlations
• Duality theory for Clifford tensor powers
• Hamiltonian-reconstruction distance as a success metric for the Variational Quantum Eigensolver