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.
18 pages, 7 figures, replaced by final version
References in corpus (12)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Black holes as mirrors: quantum information in random subsystems
- Complexity and Shock Wave Geometries
- Quantum Computation as Geometry
- Evenly distributed unitaries: on the structure of unitary designs
- Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
- Optimal control, geometry, and quantum computing
- Switchbacks and the Bridge to Nowhere
- Unitary designs from statistical mechanics in random quantum circuits
- Entangling power and quantum circuit complexity
- Semidefinite programs for completely bounded norms
- Resource theory of quantum uncomplexity
Cited by in corpus (89)
- 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
- 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
- Complete Hilbert-Space Ergodicity in Quantum Dynamics of Generalized Fibonacci Drives
- General Bounds on Holographic Complexity
- Complexity=Anything: Singularity Probes
- Learning quantum states and unitaries of bounded gate complexity
- A single -gate makes distribution learning hard
- Variational waveguide QED simulators
- Quantum Complexity as Hydrodynamics
- Crystalline Quantum Circuits
- Resource theory of quantum uncomplexity
- 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
- Kasner interiors from analytic hairy black holes
- Classical Splitting of Parametrized Quantum Circuits
- Designs via Free Probability
- From observations to complexity of quantum states via unsupervised learning
- On the role of entanglement in qudit-based circuit compression
- Non-perturbative Overlaps in JT Gravity: From Spectral Form Factor to Generating Functions of Complexity
- Entanglement asymmetry dynamics in random quantum circuits
- 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
- Data-driven discovery of statistically relevant information in quantum simulators
- Circuit Complexity in
- 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-constrained quantum thermodynamics
- Complexity via Replica Trick
- Complexity is not Enough for Randomness
- Krylov complexity in quantum many-body scars of spin-1 models
- Phase transitions in a non-Hermitian Su-Schrieffer-Heeger model via Krylov spread complexity
- Tensor network decompositions for absolutely maximally entangled states
- Fermionic Magic Resources of Quantum Many-Body Systems
- Understanding holographic error correction via unique algebras and atomic examples
- Free Independence and the Noncrossing Partition Lattice in Dual-Unitary Quantum Circuits
- Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU() Symmetry
- Krylov Complexity of Fermionic and Bosonic Gaussian States
- Unraveling long-time quantum dynamics using flow equations
- On the saturation of late-time growth of complexity in supersymmetric JT gravity
- Saturation and recurrence of quantum complexity in random local quantum dynamics
- Wavefunction branching: when you can't tell pure states from mixed states
- Complexity in algebraic QFT
- Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
- Quantum complexity phase transitions in monitored random circuits
- Universal distributions of overlaps from generic dynamics in quantum many-body systems
- Universal Early-Time Growth in Quantum Circuit Complexity
- Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
- Non-Clifford Cost of Random Unitaries
- Non-Haar random circuits form unitary designs as fast as Haar random circuits
- Sampling Problems on a Quantum Computer
- Late-Time Saturation of Black Hole Complexity
- Wasserstein Complexity of Quantum Circuits
- Matrix concentration inequalities and efficiency of random universal sets of quantum gates
- Random Circuits in the Black Hole Interior
- A recipe for local simulation of strongly-correlated fermionic matter on quantum computers: the 2D Fermi-Hubbard model
- Resource-Dependent Complexity of Quantum Channels
- Continuous-variable designs and design-based shadow tomography from random lattices
- Universal Time Evolution of Holographic and Quantum Complexity
- Quantum circuit complexity and unsupervised machine learning of topological order
- Quantifying High-Order Interdependencies in Entangled Quantum States
- Subsystem Complexity and Measurements in Holography
- Non-Universality from Conserved Superoperators in Unitary Circuits
- Toward a physically motivated notion of Gaussian complexity geometry
- Attention to Quantum Complexity
- On the stabilizer complexity of Hawking radiation
- Circuit complexity and functionality: a thermodynamic perspective
- 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
- Comparing quantum complexity and quantum fidelity
- Circuit Complexity for Coherent-Thermal States in Bosonic String Theory
- Probing the localization effects in Krylov basis
- Topologically driven no-superposing theorem with a tight error bound
- Area and volume as emergent phenomena from entangled qubits
- Hamiltonian simulation with explicit formulas for Digital-Analog Quantum Computing