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.

arXiv commentv3: 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 (45)

• Improved Simulation of Stabilizer Circuits
• Black holes as mirrors: quantum information in random subsystems
• Randomized Benchmarking of Quantum Gates
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Roads towards fault-tolerant universal quantum computation
• Scalable Noise Estimation with Random Unitary Operators
• The Resource Theory of Stabilizer Computation
• Characterizing Quantum Gates via Randomized Benchmarking
• Chaos and complexity by design
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Evenly distributed unitaries: on the structure of unitary designs
• Quantum Data Hiding
• Random Quantum Circuits are Approximate 2-designs
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Local random quantum circuits are approximate polynomial-designs
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Multiqubit Clifford groups are unitary 3-designs
• Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding
• 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
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• The spectral gap for some spin chains with discrete symmetry breaking
• A Partial Derandomization of PhaseLift using Spherical Designs
• Quantum Chaos is Quantum
• Convergence rates for arbitrary statistical moments of random quantum circuits
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Quantum State Tomography with Joint SIC POMs and Product SIC POMs
• Reexamination of optimal quantum state estimation of pure states
• Multipartite Entanglement in Stabilizer Tensor Networks
• The complexity of energy eigenstates as a mechanism for equilibration
• How to efficiently select an arbitrary Clifford group element
• Decoupling with unitary approximate two-designs
• Single T gate in a Clifford circuit drives transition to universal entanglement spectrum statistics
• Recovering quantum gates from few average gate fidelities
• Efficient Quantum Pseudorandomness
• Mixing properties of stochastic quantum Hamiltonians
• Isospectral twirling and quantum chaos
• Universality of single qudit gates
• Non-malleable encryption of quantum information
• Local random quantum circuits are approximate polynomial-designs - numerical results
• Representations of the multi-qubit Clifford group
• 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