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.

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

References in corpus (36)

• 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
• Scalable Noise Estimation with Random Unitary Operators
• Characterizing Quantum Gates via Randomized Benchmarking
• Evenly distributed unitaries: on the structure of unitary designs
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• The Second Law of Quantum Complexity
• The mother of all protocols: Restructuring quantum information's family tree
• Multiqubit Clifford groups are unitary 3-designs
• Linear growth of quantum circuit complexity
• Approximation by Quantum Circuits
• Models of quantum complexity growth
• How many entries of a typical orthogonal matrix can be approximated by independent normals?
• Bounds on the Lambert function and their application to the outage analysis of user cooperation
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• The spectral gap for some spin chains with discrete symmetry breaking
• Hadamard-free circuits expose the structure of the Clifford group
• Quantum Chaos is Quantum
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Single T gate in a Clifford circuit drives transition to universal entanglement spectrum statistics
• Unitary designs from statistical mechanics in random quantum circuits
• Efficient Quantum Pseudorandomness
• Mixing properties of stochastic quantum Hamiltonians
• Quantum union bounds for sequential projective measurements
• Transitions in entanglement complexity in random quantum circuits by measurements
• Efficient Simulation of Random Quantum States and Operators
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• A simple proof of the detectability lemma and spectral gap amplification
• On the convergence to equilibrium of Kac's random walk on matrices
• Efficient quantum pseudorandomness with simple graph states
• The invariants of the Clifford groups
• Rank-deficient representations in the Theta correspondence over finite fields arise from quantum codes
• Random walks in compact groups

Cited by in corpus (56)

• 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
• Measuring nonstabilizerness via multifractal flatness
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• Magic spreading in random quantum circuits
• Pauli Spectrum and Non-stabilizerness of Typical Quantum Many-Body States
• Efficient quantum algorithms for stabilizer entropies
• Towards large-scale quantum optimization solvers with few qubits
• Pseudomagic Quantum States
• Quantum complexity in gravity, quantum field theory, and quantum information science
• Translation symmetry restoration under random unitary dynamics
• A semi-agnostic ansatz with variable structure for quantum machine learning
• 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
• Designs via Free Probability
• Computing exact moments of local random quantum circuits via tensor networks
• Quantum neural networks form Gaussian processes
• 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
• Unitary k-designs from random number-conserving quantum circuits
• A nonstabilizerness monotone from stabilizerness asymmetry
• Quantum and Classical Dynamics with Random Permutation Circuits
• Complexity is not Enough for Randomness
• Complexity-constrained quantum thermodynamics
• 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-Haar random circuits form unitary designs as fast as Haar random circuits
• 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
• Exact spectral gaps of random one-dimensional quantum circuits
• Architectures and random properties of symplectic quantum circuits
• Random Projection using Random Quantum Circuits
• Variational Microcanonical Estimator
• 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
• Moments of Quantum Channel Ensembles
• Sample Optimal and Memory Efficient Quantum State Tomography
• Duality theory for Clifford tensor powers
• Shallow quantum circuit for generating extremely low-entangled approximate state designs
• Anticoncentration is (almost) all you need
• Hamiltonian-reconstruction distance as a success metric for the Variational Quantum Eigensolver
• Realizing Unitary $k$-designs with a Single Quench
• Linear-optical protocols for mitigating and suppressing noise in bosonic systems
• More global randomness from less-random local gates