Random Quantum Circuits are Approximate 2-designs

Abstract

Given a universal gate set on two qubits, it is well known that applying random gates from the set to random pairs of qubits will eventually yield an approximately Haar-distributed unitary. However, this requires exponential time. We show that random circuits of only polynomial length will approximate the first and second moments of the Haar distribution, thus forming approximate 1- and 2-designs. Previous constructions required longer circuits and worked only for specific gate sets. As a corollary of our main result, we also improve previous bounds on the convergence rate of random walks on the Clifford group.

48 pages, 1 figure. Typo in bibliography fixed

References in corpus (10)

• Black holes as mirrors: quantum information in random subsystems
• Evenly distributed unitaries: on the structure of unitary designs
• The mother of all protocols: Restructuring quantum information's family tree
• Quantum Copy-Protection and Quantum Money
• A decoupling approach to the quantum capacity
• Emergence of typical entanglement in two-party random processes
• Optimal two-qubit gate for generation of random bipartite entanglement
• Information-disturbance tradeoff in quantum measurement on the uniform ensemble and on the mutually unbiased bases
• Superpolynomial speedups based on almost any quantum circuit
• Simple Permutations Mix Even Better

Cited by in corpus (231)

• Variational Quantum Algorithms
• A bound on chaos
• Barren plateaus in quantum neural network training landscapes
• Characterizing Quantum Supremacy in Near-Term Devices
• Fast Scramblers
• The role of quantum information in thermodynamics --- a topical review
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Random Quantum Circuits
• Unitary-projective entanglement dynamics
• Chaos and complexity by design
• Towards the fast scrambling conjecture
• Absence of Barren Plateaus in Quantum Convolutional Neural Networks
• Layerwise learning for quantum neural networks
• Local random quantum circuits are approximate polynomial-designs
• Diffusive hydrodynamics of out-of-time-ordered correlators with charge conservation
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Emergent statistical mechanics of entanglement in random unitary circuits
• Effect of barren plateaus on gradient-free optimization
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• A semiclassical ramp in SYK and in gravity
• Multiqubit Clifford groups are unitary 3-designs
• Quantum Copy-Protection and Quantum Money
• Onset of Random Matrix Behavior in Scrambling Systems
• Preparing random states and benchmarking with many-body quantum chaos
• Quantum Machine Learning for Chemistry and Physics
• Computational advantage of quantum random sampling
• Entanglement Devised Barren Plateau Mitigation
• The entanglement membrane in chaotic many-body systems
• 64-Qubit Quantum Circuit Simulation
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Efficient measure for the expressivity of variational quantum algorithms
• Unitary designs and codes
• Emergent quantum state designs from individual many-body wavefunctions
• Quantum Algorithmic Measurement
• Architectures for quantum simulation showing a quantum speedup
• Decoupling with random quantum circuits
• Quantum Chaos is Quantum
• Recent advances for quantum classifiers
• Convergence rates for arbitrary statistical moments of random quantum circuits
• Quantum chaos in the Brownian SYK model with large finite $N$: OTOCs and tripartite information
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Random quantum circuits anti-concentrate in log depth
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Efficient and feasible state tomography of quantum many-body systems
• A polynomial-time classical algorithm for noisy random circuit sampling
• A Random Unitary Circuit Model for Black Hole Evaporation
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Quantum entanglement in random physical states
• Scrambling and Complexity in Phase Space
• Decoupling with unitary approximate two-designs
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
• Information scrambling in chaotic systems with dissipation
• Chaos in Classical D0-Brane Mechanics
• Quantum coding with low-depth random circuits
• Unitary designs from statistical mechanics in random quantum circuits
• Large Deviation Bounds for k-designs
• Absence of fast scrambling in thermodynamically stable long-range interacting systems
• Anticoncentration theorems for schemes showing a quantum speedup
• The Clifford group fails gracefully to be a unitary 4-design
• Re-examining the quantum volume test: Ideal distributions, compiler optimizations, confidence intervals, and scalable resource estimations
• The Presence and Absence of Barren Plateaus in Tensor-network Based Machine Learning
• Efficient Quantum Pseudorandomness
• Phase transitions and metastability in the distribution of the bipartite entanglement of a large quantum system
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Mixing properties of stochastic quantum Hamiltonians
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Scrambling speed of random quantum circuits
• Information propagation through quantum chains with fluctuating disorder
• Subsystem dynamics under random Hamiltonian evolution
• Sample complexity of device-independently certified "quantum supremacy"
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators
• Triviality of quantum trajectories close to a directed percolation transition
• Toward Trainability of Quantum Neural Networks
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Temporal Entanglement in Chaotic Quantum Circuits
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Expressibility and trainability of parameterized analog quantum systems for machine learning applications
• Entanglement Typicality
• Mitigating Barren Plateaus with Transfer-learning-inspired Parameter Initializations
• Quantum circuits for exact unitary $t$-designs and applications to higher-order randomized benchmarking
• Complete entropic inequalities for quantum Markov chains
• Unitary $2$-designs from random $X$- and $Z$-diagonal unitaries
• Comment on the paper "Random Quantum Circuits are Approximate 2-designs"
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Noise and the frontier of quantum supremacy
• Generating a state $t$-design by diagonal quantum circuits
• Transport and entanglement growth in long-range random Clifford circuits
• Random unitary maps for quantum state reconstruction
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Isospectral twirling and quantum chaos
• Fastest local entanglement scrambler, multistage thermalization, and a non-Hermitian phantom
• Random Matrix Theory of the Isospectral twirling
• Diagonal quantum circuits: their computational power and applications
• Randomized compiling for scalable quantum computing on a noisy superconducting quantum processor
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• A Separation of Out-of-time-ordered Correlation and Entanglement
• Efficient Quantum Tensor Product Expanders and k-designs
• A semi-agnostic ansatz with variable structure for quantum machine learning
• Translation symmetry restoration under random unitary dynamics
• Exponential data encoding for quantum supervised learning
• Approximate Randomized Benchmarking for Finite Groups
• Shadow tomography from emergent state designs in analog quantum simulators
• Analysing quantum systems with randomised measurements
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Near-optimal covariant quantum error-correcting codes from random unitaries with symmetries
• Spectral decoupling in many-body quantum chaos
• Solvable non-Hermitian skin effect in many-body unitary dynamics
• Optimal Universal Quantum Error Correction via Bounded Reference Frames
• Entanglement entropy production in Quantum Neural Networks
• Entanglement measures of bipartite quantum gates and their thermalization under arbitrary interaction strength
• Quantum to Classical Randomness Extractors
• Scrambling and quantum chaos indicators from long-time properties of operator distributions
• Generating Haar-uniform Randomness using Stochastic Quantum Walks on a Photonic Chip
• Ensembles of physical states and random quantum circuits on graphs
• Efficient quantum pseudorandomness with simple graph states
• Short random circuits define good quantum error correcting codes
• Stringy effects in scrambling
• Markovianization with approximate unitary designs
• Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
• Tackling Sampling Noise in Physical Systems for Machine Learning Applications: Fundamental Limits and Eigentasks
• Efficient estimation of trainability for variational quantum circuits
• Quantum Convolutional Neural Networks are Effectively Classically Simulable
• Explaining Quantum Circuits with Shapley Values: Towards Explainable Quantum Machine Learning
• Local random quantum circuits are approximate polynomial-designs - numerical results
• Operator growth in random quantum circuits with symmetry
• Computing exact moments of local random quantum circuits via tensor networks
• An exponentially-growing family of universal quantum circuits
• Quantum neural networks form Gaussian processes
• Designs via Free Probability
• Randomized gap and amplitude estimation
• Real-time correlators in chaotic quantum many-body systems
• Quantum Side Information: Uncertainty Relations, Extractors, Channel Simulations
• Quantum Causal Influence
• Theory of Ergodic Quantum Processes
• Quantifying scrambling in quantum neural networks
• Dependence of a quantum mechanical system on its own initial state and the initial state of the environment it interacts with
• Random circuits by measurements on weighted graph states
• Fluctuations of subsystem entropies at late times
• Randomized Benchmarking in the Analogue Setting
• Observation of entanglement negativity transition of pseudo-random mixed states
• Near-linear constructions of exact unitary 2-designs
• Phantom relaxation rate of the average purity evolution in random circuits due to Jordan non-Hermitian skin effect and magic sums
• Practical verification protocols for analog quantum simulators
• Automatic quantum circuit encoding of a given arbitrary quantum state
• Efficient Unitary T-designs from Random Sums
• Measuring the distance between quantum many-body wave functions
• Modeling the Performance of Early Fault-Tolerant Quantum Algorithms
• Efficient unitary designs and pseudorandom unitaries from permutations
• Experimental Implementation of Efficient Quantum Pseudorandomness on a 12-spin System
• Unraveling the emergence of quantum state designs in systems with symmetry
• Generalized quantum microcanonical ensemble from random matrix product states
• One-Shot Randomized and Nonrandomized Partial Decoupling
• Decoupling with random diagonal unitaries
• Estimating the randomness of quantum circuit ensembles up to 50 qubits
• Impact of the form of weighted networks on the quantum extreme reservoir computation
• On the explicit constructions of certain unitary $t$-designs
• Sample-efficient verification of continuously-parameterized quantum gates for small quantum processors
• Pure state thermodynamics with matrix product states
• Pseudo-randomness and Learning in Quantum Computation
• Purity of thermal mixed quantum states
• Mixing and localisation in random time-periodic quantum circuits of Clifford unitaries
• Quantum simulation using noisy unitary circuits and measurements
• Unitary k-designs from random number-conserving quantum circuits
• Quantum and Classical Dynamics with Random Permutation Circuits
• Superpolynomial speedups based on almost any quantum circuit
• Designs from Local Random Quantum Circuits with SU(d) Symmetry
• Absence of localization in two-dimensional Clifford circuits
• Extracting randomness from magic quantum states
• Asymmetric butterfly velocities in 2-local Hamiltonians
• Complexity is not Enough for Randomness
• Kerdock Codes Determine Unitary 2-Designs
• Virtual distillation with noise dilution
• Testing randomness with photons
• Purity decay rate in random circuits with different configurations of gates
• Free Independence and the Noncrossing Partition Lattice in Dual-Unitary Quantum Circuits
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• The SWITCH test for discriminating quantum evolutions
• Linear Cross Entropy Benchmarking with Clifford Circuits
• Saturation and recurrence of quantum complexity in random local quantum dynamics
• Quantum supremacy in driven quantum many-body systems
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Halving the Cost of Quantum Algorithms with Randomization
• Local random quantum circuits: ensemble CP maps and swap algebras
• Quantum circuit for three-qubit random states
• Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement
• Unitary $t$-designs from $relaxed$ seeds
• Context Aware Fidelity Estimation
• Variational Optimization for Quantum Problems using Deep Generative Networks
• Effective field theory of random quantum circuits
• Universal distributions of overlaps from generic dynamics in quantum many-body systems
• Thermal states of random quantum many-body systems
• 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
• Generic Entanglement Entropy for Quantum States with Symmetry
• On the average-case complexity of learning output distributions of quantum circuits
• Efficient achievability for quantum protocols using decoupling theorems
• Noise Induced Universal Diffusive Transport in Fermionic Chains
• Exact spectral gaps of random one-dimensional quantum circuits
• Fidelity decay and error accumulation in random quantum circuits
• Random Circuits in the Black Hole Interior
• A Variational Quantum Algorithm For Approximating Convex Roofs
• Fault tolerant quantum data locking
• Random Projection using Random Quantum Circuits
• Quantum simulation and ground state preparation for the honeycomb Kitaev model
• Charge-conserving unitaries typically generate optimal covariant quantum error-correcting codes
• Optimized numerical gradient and Hessian estimation for variational quantum algorithms
• Propagation of correlations in Local Random Quantum Circuits
• Implementation of single-qubit measurement-based t-designs using IBM processors
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• qLEET: Visualizing Loss Landscapes, Expressibility, Entangling Power and Training Trajectories for Parameterized Quantum Circuits
• Robustness of optimized numerical estimation schemes for noisy variational quantum algorithms
• Machine Learning Kernel Method from a Quantum Generative Model
• Sampling and the complexity of nature
• Simulating typical entanglement with many-body Hamiltonian dynamics
• Non-Universality from Conserved Superoperators in Unitary Circuits
• Entanglement dynamics from universal low-lying modes
• Equilibration and Typicality in Quantum Processes
• High-expressibility Quantum Neural Networks using only classical resources
• More global randomness from less-random local gates
• Investigating the effect of noise channels on the quality of unitary t-designs
• Run-length certificates in quantum learning: sample complexity and noise thresholds
• Non-Equilibrium Quantum Many-Body Physics with Quantum Circuits
• Realizing Unitary $k$-designs with a Single Quench
• Anticoncentration is (almost) all you need
• Adaptively secure unitary designs with constant non-Clifford cost
• Quantum Oracle Separations from Complex but Easily Specified States
• Dynamical cluster-based strategy for improving tensor network algorithms in quantum circuit simulations
• Linear-optical protocols for mitigating and suppressing noise in bosonic systems
• Holographic Interpretation of Relative State Complexity