Local random quantum circuits are approximate polynomial-designs

Abstract

We prove that local random quantum circuits acting on n qubits composed of O(t^{10} n^2) many nearest neighbor two-qubit gates form an approximate unitary t-design. Previously it was unknown whether random quantum circuits were a t-design for any t > 3. The proof is based on an interplay of techniques from quantum many-body theory, representation theory, and the theory of Markov chains. In particular we employ a result of Nachtergaele for lower bounding the spectral gap of frustration-free quantum local Hamiltonians; a quasi-orthogonality property of permutation matrices; a result of Oliveira which extends to the unitary group the path-coupling method for bounding the mixing time of random walks; and a result of Bourgain and Gamburd showing that dense subgroups of the special unitary group, composed of elements with algebraic entries, are infty-copy tensor-product expanders. We also consider pseudo-randomness properties of local random quantum circuits of small depth and prove that circuits of depth O(t^{10}n) constitute a quantum t-copy tensor-product expander. The proof also rests on techniques from quantum many-body theory, in particular on the detectability lemma of Aharonov, Arad, Landau, and Vazirani. We give applications of the results to cryptography, equilibration of closed quantum dynamics, and the generation of topological order. In particular we show the following pseudo-randomness property of generic quantum circuits: Almost every circuit U of size O(n^k) on n qubits cannot be distinguished from a Haar uniform unitary by circuits of size O(n^{(k-9)/11}) that are given oracle access to U.

39 pages, no figures. v2. exponent of t went up. v3. small changes, almost identical to published version. v4. further fixes to proofs, results mostly unchanged

References in corpus (16)

• Non-Abelian Anyons and Topological Quantum Computation
• Black holes as mirrors: quantum information in random subsystems
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• Foundation of Statistical Mechanics under experimentally realistic conditions
• Strong and weak thermalization of infinite non-integrable quantum systems
• Aspects of generic entanglement
• Randomizing quantum states: Constructions and applications
• Absence of Thermalization in Nonintegrable Systems
• The mother of all protocols: Restructuring quantum information's family tree
• Quantum logarithmic Sobolev inequalities and rapid mixing
• Unitary designs and codes
• Exact convergence times for generation of random bipartite entanglement
• Emergence of typical entanglement in two-party random processes
• Comment on the paper "Random Quantum Circuits are Approximate 2-designs"
• Efficient algorithm for multi-qudit twirling for ensemble quantum computation
• On the convergence to equilibrium of Kac's random walk on matrices

Cited by in corpus (241)

• Variational Quantum Algorithms
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• The role of quantum information in thermodynamics --- a topical review
• Operator Spreading in Random Unitary Circuits
• Quantum Entanglement Growth Under Random Unitary Dynamics
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Random Quantum Circuits
• Quantum Error Correction in Scrambling Dynamics and Measurement-Induced Phase Transition
• Dynamical purification phase transitions induced by quantum measurements
• Absence of Barren Plateaus in Quantum Convolutional Neural Networks
• Diffusive hydrodynamics of out-of-time-ordered correlators with charge conservation
• Emergent statistical mechanics of entanglement in random unitary circuits
• Chaos, Complexity, and Random Matrices
• Rényi Entropies from Random Quenches in Atomic Hubbard and Spin Models
• Effect of barren plateaus on gradient-free optimization
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Trainability of Dissipative Perceptron-Based Quantum Neural Networks
• Onset of Random Matrix Behavior in Scrambling Systems
• Preparing random states and benchmarking with many-body quantum chaos
• Linear growth of quantum circuit complexity
• Many-body quantum magic
• Large gradients via correlation in random parameterized quantum circuits
• Computational advantage of quantum random sampling
• Equivalence of quantum barren plateaus to cost concentration and narrow gorges
• The entanglement membrane in chaotic many-body systems
• Barren plateaus preclude learning scramblers
• Theory of quantum system certification: a tutorial
• 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
• Universal behavior beyond multifractality of wave-functions at measurement--induced phase transitions
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Models of quantum complexity growth
• Direct randomized benchmarking for multi-qubit devices
• On barren plateaus and cost function locality in variational quantum algorithms
• Scalable measures of magic resource for quantum computers
• Exact emergent quantum state designs from quantum chaotic dynamics
• Expressibility of the alternating layered ansatz for quantum computation
• Unitary $n$-designs via random quenches in atomic Hubbard and Spin models: Application to the measurement of Rényi entropies
• Emergent quantum state designs from individual many-body wavefunctions
• Architectures for quantum simulation showing a quantum speedup
• Symmetry restoration and quantum Mpemba effect in symmetric random circuits
• Quantum chaos in the Brownian SYK model with large finite $N$: OTOCs and tripartite information
• How Dynamical Quantum Memories Forget
• 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
• A volumetric framework for quantum computer benchmarks
• Open Quantum Symmetric Simple Exclusion Process
• A Random Unitary Circuit Model for Black Hole Evaporation
• Entanglement dynamics in hybrid quantum circuits
• On the practical usefulness of the Hardware Efficient Ansatz
• Characterizing multipartite entanglement with moments of random correlations
• Scrambling and Complexity in Phase Space
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• Variational Quantum Eigensolver for Frustrated Quantum Systems
• Information scrambling in chaotic systems with dissipation
• Complexity Growth in Integrable and Chaotic Models
• Quantum coding with low-depth random circuits
• Magic spreading in random quantum circuits
• Pauli Spectrum and Non-stabilizerness of Typical Quantum Many-Body States
• Efficient quantum algorithms for stabilizer entropies
• Driven quantum dynamics: will it blend?
• Entanglement growth in diffusive systems
• Anticoncentration theorems for schemes showing a quantum speedup
• Generative quantum machine learning via denoising diffusion probabilistic models
• Symmetry-resolved Page curves
• Equilibrium Fluctuations in Maximally Noisy Extended Quantum Systems
• Quantum scrambling with classical shadows
• Re-examining the quantum volume test: Ideal distributions, compiler optimizations, confidence intervals, and scalable resource estimations
• Entanglement, quantum randomness, and complexity beyond scrambling
• Code properties from holographic geometries
• 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
• Sample complexity of device-independently certified "quantum supremacy"
• Qubit-efficient encoding schemes for binary optimisation problems
• Towards large-scale quantum optimization solvers with few qubits
• Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Projected Least-Squares Quantum Process Tomography
• Generalized Entanglement Entropies of Quantum Designs
• Complete entropic inequalities for quantum Markov chains
• From stochastic spin chains to quantum Kardar-Parisi-Zhang dynamics
• Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm
• Quantum circuits for exact unitary $t$-designs and applications to higher-order randomized benchmarking
• Quantum complexity in gravity, quantum field theory, and quantum information science
• Unitary $2$-designs from random $X$- and $Z$-diagonal unitaries
• Almost Markovian processes from closed dynamics
• Unforgeable Quantum Encryption
• Noise and the frontier of quantum supremacy
• Characterizing complexity of many-body quantum dynamics by higher-order eigenstate thermalization
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Dynamics of Fluctuations in Quantum Simple Exclusion Processes
• Fastest local entanglement scrambler, multistage thermalization, and a non-Hermitian phantom
• Quantum State Complexity in Computationally Tractable Quantum Circuits
• Random Matrix Theory of the Isospectral twirling
• A Separation of Out-of-time-ordered Correlation and Entanglement
• Translation symmetry restoration under random unitary dynamics
• A semi-agnostic ansatz with variable structure for quantum machine learning
• Near-optimal covariant quantum error-correcting codes from random unitaries with symmetries
• Analysing quantum systems with randomised measurements
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Learning quantum states and unitaries of bounded gate complexity
• Error-resilience Phase Transitions in Encoding-Decoding Quantum Circuits
• Measurement induced entanglement transition in two dimensional shallow circuit
• Optimal Universal Quantum Error Correction via Bounded Reference Frames
• Guaranteed recovery of quantum processes from few measurements
• Entanglement entropy production in Quantum Neural Networks
• Emergent statistical mechanics from properties of disordered random matrix product states
• Entanglement measures of bipartite quantum gates and their thermalization under arbitrary interaction strength
• Bell sampling from quantum circuits
• Correlation length in random MPS and PEPS
• Generating Haar-uniform Randomness using Stochastic Quantum Walks on a Photonic Chip
• Engineered dissipation to mitigate barren plateaus
• Efficient quantum pseudorandomness with simple graph states
• Query-optimal estimation of unitary channels in diamond distance
• Markovianization with approximate unitary designs
• Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
• Can the Macroscopic Fluctuation Theory be Quantized?
• Efficient estimation of trainability for variational quantum circuits
• Black holes as clouded mirrors: the Hayden-Preskill protocol with symmetry
• Growth of genuine multipartite entanglement in random unitary circuits
• Quantum Convolutional Neural Networks are Effectively Classically Simulable
• Schrödinger-Heisenberg Variational Quantum Algorithms
• Improved local spectral gap thresholds for lattices of finite dimension
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Isometric tensor network optimization for extensive Hamiltonians is free of barren plateaus
• Computing exact moments of local random quantum circuits via tensor networks
• Universal fluctuations around typicality for quantum ergodic systems
• Multiphoton Tomography with Linear Optics and Photon Counting
• Quantum State Tomography for Matrix Product Density Operators
• Anticoncentration and state design of random tensor networks
• Efficient simulation of random states and random unitaries
• Quantifying scrambling in quantum neural networks
• Fluctuations of subsystem entropies at late times
• Randomized Benchmarking in the Analogue Setting
• Mitigated barren plateaus in the time-nonlocal optimization of analog quantum-algorithm protocols
• Efficient unitary designs and pseudorandom unitaries from permutations
• Efficient Unitary T-designs from Random Sums
• The principle of majorization: application to random quantum circuits
• Sampling and scrambling on a chain of superconducting qubits
• Estimating the randomness of quantum circuit ensembles up to 50 qubits
• Decoupling with random diagonal unitaries
• On the explicit constructions of certain unitary $t$-designs
• Mixing and localisation in random time-periodic quantum circuits of Clifford unitaries
• Clifford Group and Unitary Designs under Symmetry
• Quantum simulation using noisy unitary circuits and measurements
• Nonlocal growth of quantum conditional mutual information under decoherence
• Purity of thermal mixed quantum states
• Weak approximate unitary designs and applications to quantum encryption
• Unitary k-designs from random number-conserving quantum circuits
• Quantum and Classical Dynamics with Random Permutation Circuits
• Laziness, Barren Plateau, and Noise in Machine Learning
• Energy-dependent barren plateau in bosonic variational quantum circuits
• Approximate orthogonality of permutation operators, with application to quantum information
• Designs from Local Random Quantum Circuits with SU(d) Symmetry
• Extracting randomness from magic quantum states
• Complexity-constrained quantum thermodynamics
• Thermalization in Kitaev's quantum double models via Tensor Network techniques
• Operational Quantum Average-Case Distances
• Unitary Designs of Symmetric Local Random Circuits
• Complexity is not Enough for Randomness
• Asymmetric butterfly velocities in 2-local Hamiltonians
• Purity decay rate in random circuits with different configurations of gates
• Exploring Quantum Average-Case Distances: proofs, properties, and examples
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• Linear Cross Entropy Benchmarking with Clifford Circuits
• Absence of barren plateaus and scaling of gradients in the energy optimization of isometric tensor network states
• Cross-Platform Verification in Quantum Networks
• Free Independence and the Noncrossing Partition Lattice in Dual-Unitary Quantum Circuits
• Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU($d$) Symmetry
• Characterization of randomness in quantum circuits of continuous gate sets
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Saturation and recurrence of quantum complexity in random local quantum dynamics
• Sparse random Hamiltonians are quantumly easy
• Local, Expressive, Quantum-Number-Preserving VQE Ansatze for Fermionic Systems
• Verifiable measurement-based quantum random sampling with trapped ions
• Halving the Cost of Quantum Algorithms with Randomization
• Optimal Conversion from Classical to Quantum Randomness via Quantum Chaos
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Holographic deep thermalization for secure and efficient quantum random state generation
• Efficient witnessing and testing of magic in mixed quantum states
• Problem-tailored Simulation of Energy Transport on Noisy Quantum Computers
• Approximating quantum channels by completely positive maps with small Kraus rank
• Local random quantum circuits: ensemble CP maps and swap algebras
• Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement
• Quantum complexity phase transitions in monitored random circuits
• Hopf algebras and solvable unitary circuits
• Designs from magic-augmented Clifford circuits
• Universal distributions of overlaps from generic dynamics in quantum many-body systems
• Phase transitions in sampling and error correction in local Brownian circuits
• Effective field theory of random quantum circuits
• Unitary $t$-designs from $relaxed$ seeds
• Emergent Quantum Mechanics at the Boundary of a Local Classical Lattice Model
• Efficient approximate unitary designs from random Pauli rotations
• Non-Haar random circuits form unitary designs as fast as Haar random circuits
• Generic Entanglement Entropy for Quantum States with Symmetry
• Emergent unitary designs for encoded qubits from coherent errors and syndrome measurements
• The Quantum Supremacy Tsirelson Inequality
• Quantum Merkle Trees
• On the Computational Hardness of Quantum One-Wayness
• Non-Clifford Cost of Random Unitaries
• On the average-case complexity of learning output distributions of quantum circuits
• Tensor-Programmable Quantum Circuits for Solving Differential Equations
• Variational Microcanonical Estimator
• Architectures and random properties of symplectic quantum circuits
• Random Projection using Random Quantum Circuits
• Fault tolerant quantum data locking
• Exact spectral gaps of random one-dimensional quantum circuits
• Random Circuits in the Black Hole Interior
• Resource-Efficient Cross-Platform Verification with Modular Superconducting Devices
• A Theory of Direct Randomized Benchmarking
• Randomized measurements for multi-parameter quantum metrology
• Benchmarking the performance of a high-Q cavity qudit using random unitaries
• Implementation of single-qubit measurement-based t-designs using IBM processors
• Pseudochaotic Many-Body Dynamics as a Pseudorandom State Generator
• On Computational Complexity of Unitary and State Design Properties
• Field theory of charge sharpening in symmetric monitored quantum circuits
• Attention to Quantum Complexity
• Non-Universality from Conserved Superoperators in Unitary Circuits
• A Hierarchy of Spectral Gap Certificates for Frustration-Free Spin Systems
• Fundamental solutions of heat equation on unitary groups establish an improved relation between $\epsilon$-nets and approximate unitary $t$-designs
• Generalized group designs: constructing novel unitary 2-, 3- and 4-designs
• Entanglement dynamics from universal low-lying modes
• Dynamical cluster-based strategy for improving tensor network algorithms in quantum circuit simulations
• Shallow quantum circuit for generating extremely low-entangled approximate state designs
• A graph-theoretic approach to chaos and complexity in quantum systems
• On the query complexity of unitary channel certification
• Equivalence between exponential concentration in quantum machine learning kernels and barren plateaus in variational algorithms
• Adaptively secure unitary designs with constant non-Clifford cost
• Anticoncentration is (almost) all you need
• Realizing Unitary $k$-designs with a Single Quench
• Moments of Quantum Channel Ensembles
• Run-length certificates in quantum learning: sample complexity and noise thresholds
• Linear-optical protocols for mitigating and suppressing noise in bosonic systems
• Quantum Private Broadcasting
• More global randomness from less-random local gates
• Hamiltonian-reconstruction distance as a success metric for the Variational Quantum Eigensolver
• Investigating the effect of noise channels on the quality of unitary t-designs
• Optimal quantum (tensor product) expanders from unitary designs
• Approximate Quantum Error Correction with 1D Log-Depth Circuits
• Comparing quantum complexity and quantum fidelity