Linear growth of quantum circuit complexity
arXiv:2106.05305 · doi:10.1038/s41567-022-01539-6
Abstract
Quantifying quantum states' complexity is a key problem in various subfields of science, from quantum computing to black-hole physics. We prove a prominent conjecture by Brown and Susskind about how random quantum circuits' complexity increases. Consider constructing a unitary from Haar-random two-qubit quantum gates. Implementing the unitary exactly requires a circuit of some minimal number of gates - the unitary's exact circuit complexity. We prove that this complexity grows linearly with the number of random gates, with unit probability, until saturating after exponentially many random gates. Our proof is surprisingly short, given the established difficulty of lower-bounding the exact circuit complexity. Our strategy combines differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.
arXiv comment18 pages, 7 figures, replaced by final version
References in corpus (40)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Nonequilibrium dynamics of closed interacting quantum systems
- A bound on chaos
- Eternal Black Holes in AdS
- Black holes and the butterfly effect
- Improved Simulation of Stabilizer Circuits
- Black holes as mirrors: quantum information in random subsystems
- Quantum many-body systems out of equilibrium
- Complexity Equals Action
- Quantum Error Correction and Orthogonal Geometry
- Complexity and Shock Wave Geometries
- Stabilizer Codes and Quantum Error Correction
- Operator Spreading in Random Unitary Circuits
- Exact and Approximate Unitary 2-Designs: Constructions and Applications
- Complexity, action, and black holes
- Measurement-driven entanglement transition in hybrid quantum circuits
- Quantum Computation as Geometry
- Instantaneous non-local computation of low T-depth quantum circuits
- The Heisenberg Representation of Quantum Computers
- Unitary-projective entanglement dynamics
- A blueprint for demonstrating quantum supremacy with superconducting qubits
- Chaos and complexity by design
- Evenly distributed unitaries: on the structure of unitary designs
- Local random quantum circuits are approximate polynomial-designs
- The Second Law of Quantum Complexity
- Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
- Complexity and entanglement for thermofield double states
- Multiqubit Clifford groups are unitary 3-designs
- Optimal control, geometry, and quantum computing
- Approximation by Quantum Circuits
- Models of quantum complexity growth
- Switchbacks and the Bridge to Nowhere
- Unitary designs from statistical mechanics in random quantum circuits
- Entangling power and quantum circuit complexity
- Efficient Quantum Pseudorandomness
- Mixing properties of stochastic quantum Hamiltonians
- Semidefinite programs for completely bounded norms
- Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
- Resource theory of quantum uncomplexity
- Black Holes and Complexity Classes
Cited by in corpus (90)
- Quantum chaos and the complexity of spread of states
- Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
- Quantum Computational Complexity -- From Quantum Information to Black Holes and Back
- Quantum Dynamics in Krylov Space: Methods and Applications
- Random quantum circuits are approximate unitary -designs in depth
- Hamiltonian variational ansatz without barren plateaus
- Spectral and Krylov Complexity in Billiard Systems
- Efficient unitary designs with a system-size independent number of non-Clifford gates
- Tight bounds on the convergence of noisy random circuits to the uniform distribution
- Spread and Spectral Complexity in Quantum Spin Chains: from Integrability to Chaos
- Quantum Phase Recognition via Quantum Kernel Methods
- General Bounds on Holographic Complexity
- Complete Hilbert-Space Ergodicity in Quantum Dynamics of Generalized Fibonacci Drives
- Learning quantum states and unitaries of bounded gate complexity
- Complexity=Anything: Singularity Probes
- A single -gate makes distribution learning hard
- Variational waveguide QED simulators
- Resource theory of quantum uncomplexity
- Quantum Complexity as Hydrodynamics
- Crystalline Quantum Circuits
- Is Action Complexity better for de Sitter space in Jackiw-Teitelboim gravity?
- Krylov spread complexity as holographic complexity beyond JT gravity
- Magic Resources of the Heisenberg Picture
- Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric
- Classical Splitting of Parametrized Quantum Circuits
- Kasner interiors from analytic hairy black holes
- Designs via Free Probability
- From observations to complexity of quantum states via unsupervised learning
- On the role of entanglement in qudit-based circuit compression
- Entanglement asymmetry dynamics in random quantum circuits
- Non-perturbative Overlaps in JT Gravity: From Spectral Form Factor to Generating Functions of Complexity
- Universality in long-distance geometry and quantum complexity
- Quantum Error Correction from Complexity in Brownian SYK
- Estimating the randomness of quantum circuit ensembles up to 50 qubits
- Circuit Complexity in
- Data-driven discovery of statistically relevant information in quantum simulators
- Bridging Entanglement and Magic Resources within Operator Space
- Hilbert-Space Ergodicity in Driven Quantum Systems: Obstructions and Designs
- Unitary k-designs from random number-conserving quantum circuits
- Complexity is not Enough for Randomness
- Complexity via Replica Trick
- Complexity-constrained quantum thermodynamics
- Free Independence and the Noncrossing Partition Lattice in Dual-Unitary Quantum Circuits
- Tensor network decompositions for absolutely maximally entangled states
- Phase transitions in a non-Hermitian Su-Schrieffer-Heeger model via Krylov spread complexity
- Fermionic Magic Resources of Quantum Many-Body Systems
- Understanding holographic error correction via unique algebras and atomic examples
- Krylov complexity in quantum many-body scars of spin-1 models
- Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU() Symmetry
- Unraveling long-time quantum dynamics using flow equations
- Krylov Complexity of Fermionic and Bosonic Gaussian States
- On the saturation of late-time growth of complexity in supersymmetric JT gravity
- Saturation and recurrence of quantum complexity in random local quantum dynamics
- Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
- Quantum complexity phase transitions in monitored random circuits
- Wavefunction branching: when you can't tell pure states from mixed states
- Complexity in algebraic QFT
- Universal Early-Time Growth in Quantum Circuit Complexity
- Universal distributions of overlaps from generic dynamics in quantum many-body systems
- Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
- Non-Haar random circuits form unitary designs as fast as Haar random circuits
- Non-Clifford Cost of Random Unitaries
- Late-Time Saturation of Black Hole Complexity
- Wasserstein Complexity of Quantum Circuits
- Sampling Problems on a Quantum Computer
- Random Circuits in the Black Hole Interior
- Matrix concentration inequalities and efficiency of random universal sets of quantum gates
- Quantifying High-Order Interdependencies in Entangled Quantum States
- Quantum circuit complexity and unsupervised machine learning of topological order
- Resource-Dependent Complexity of Quantum Channels
- Universal Time Evolution of Holographic and Quantum Complexity
- Subsystem Complexity and Measurements in Holography
- Continuous-variable designs and design-based shadow tomography from random lattices
- A recipe for local simulation of strongly-correlated fermionic matter on quantum computers: the 2D Fermi-Hubbard model
- Non-Universality from Conserved Superoperators in Unitary Circuits
- Circuit complexity and functionality: a thermodynamic perspective
- Toward a physically motivated notion of Gaussian complexity geometry
- Attention to Quantum Complexity
- On the stabilizer complexity of Hawking radiation
- Fast suppression of classification error in variational quantum circuits
- Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians
- Resilience-Runtime Tradeoff Relations for Quantum Algorithms
- More global randomness from less-random local gates
- Integrable fishnet circuits and Brownian solitons
- Circuit Complexity for Coherent-Thermal States in Bosonic String Theory
- Comparing quantum complexity and quantum fidelity
- Topologically driven no-superposing theorem with a tight error bound
- Probing the localization effects in Krylov basis
- Area and volume as emergent phenomena from entangled qubits
- Hamiltonian simulation with explicit formulas for Digital-Analog Quantum Computing