Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$

Abstract

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(n{t}^{10.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 $\Omega (n^{-1}{t}^{-9.5})$. We improve this lower bound to $\Omega (n^{-1}{t}^{-4-o(1)})$, where the $o(1)$ term goes to $0$ as $t\to \infty$. A direct consequence of this scaling is that random quantum circuits generate approximate unitary $t$-designs in depth $O(n{t}^{5+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.

21 pages, 1 figure, v2: typos corrected and new references, v3: minor corrections, version accepted in Quantum

References in corpus (6)

• Black holes as mirrors: quantum information in random subsystems
• Randomized Benchmarking of Quantum Gates
• Evenly distributed unitaries: on the structure of unitary designs
• The mother of all protocols: Restructuring quantum information's family tree
• Unitary designs from statistical mechanics in random quantum circuits
• On the convergence to equilibrium of Kac's random walk on matrices

Cited by in corpus (55)

• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Computational advantage of quantum random sampling
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Quantifying nonstabilizerness of matrix product states
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• Measuring nonstabilizerness via multifractal flatness
• Pauli Spectrum and Non-stabilizerness of Typical Quantum Many-Body States
• Magic spreading in random quantum circuits
• Efficient quantum algorithms for stabilizer entropies
• Towards large-scale quantum optimization solvers with few qubits
• Quantum complexity in gravity, quantum field theory, and quantum information science
• Pseudomagic Quantum States
• Translation symmetry restoration under random unitary dynamics
• Learning quantum states and unitaries of bounded gate complexity
• Query-optimal estimation of unitary channels in diamond distance
• Efficient estimation of trainability for variational quantum circuits
• Quantum Convolutional Neural Networks are Effectively Classically Simulable
• Quantum neural networks form Gaussian processes
• Designs via Free Probability
• Computing exact moments of local random quantum circuits via tensor networks
• Efficient Unitary T-designs from Random Sums
• Efficient unitary designs and pseudorandom unitaries from permutations
• Long-range nonstabilizerness and phases of matter
• Exactly solvable many-body dynamics from space-time duality
• Quantum and Classical Dynamics with Random Permutation Circuits
• Unitary k-designs from random number-conserving quantum circuits
• A nonstabilizerness monotone from stabilizerness asymmetry
• Complexity-constrained quantum thermodynamics
• Complexity is not Enough for Randomness
• Characterization of randomness in quantum circuits of continuous gate sets
• Optimal Conversion from Classical to Quantum Randomness via Quantum Chaos
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Quantum complexity phase transitions in monitored random circuits
• Designs from magic-augmented Clifford circuits
• Fundamental limits on quantum cloning from the no-signalling principle
• Non-Clifford Cost of Random Unitaries
• Efficient approximate unitary designs from random Pauli rotations
• On the average-case complexity of learning output distributions of quantum circuits
• Non-Haar random circuits form unitary designs as fast as Haar random circuits
• Exact spectral gaps of random one-dimensional quantum circuits
• Architectures and random properties of symplectic quantum circuits
• Variational Microcanonical Estimator
• Random Projection using Random Quantum Circuits
• On Computational Complexity of Unitary and State Design Properties
• Non-stabilizerness and entanglement from cat-state injection
• Generalized group designs: constructing novel unitary 2-, 3- and 4-designs
• Realizing Unitary $k$-designs with a Single Quench
• More global randomness from less-random local gates
• Linear-optical protocols for mitigating and suppressing noise in bosonic systems
• Hamiltonian-reconstruction distance as a success metric for the Variational Quantum Eigensolver
• Moments of Quantum Channel Ensembles
• Duality theory for Clifford tensor powers
• Shallow quantum circuit for generating extremely low-entangled approximate state designs
• Anti-concentration is (almost) all you need
• Sample Optimal and Memory Efficient Quantum State Tomography