The Second Law of Quantum Complexity

Abstract

We give arguments for the existence of a thermodynamics of quantum complexity that includes a "Second Law of Complexity". To guide us, we derive a correspondence between the computational (circuit) complexity of a quantum system of $K$ qubits, and the positional entropy of a related classical system with $2^K$ degrees of freedom. We also argue that the kinetic entropy of the classical system is equivalent to the Kolmogorov complexity of the quantum Hamiltonian. We observe that the expected pattern of growth of the complexity of the quantum system parallels the growth of entropy of the classical system. We argue that the property of having less-than-maximal complexity (uncomplexity) is a resource that can be expended to perform directed quantum computation. Although this paper is not primarily about black holes, we find a surprising interpretation of the uncomplexity-resource as the accessible volume of spacetime behind a black hole horizon.

v2: minor improvements

References in corpus (4)

• Black holes as mirrors: quantum information in random subsystems
• Complexity and Shock Wave Geometries
• Loschmidt Echo
• Quantum Complexity and Negative Curvature

Cited by in corpus (216)

• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Circuit Complexity in Fermionic Field Theory
• Complexity and entanglement for thermofield double states
• Quantum Computation as Gravity
• Operator complexity: a journey to the edge of Krylov space
• Solvable Models of Quantum Black Holes: A Review on Jackiw-Teitelboim Gravity
• Circuit complexity in interacting QFTs and RG flows
• Linear growth of quantum circuit complexity
• Many-body quantum magic
• Holographic Complexity in Vaidya Spacetimes II
• Quantum Computational Complexity -- From Quantum Information to Black Holes and Back
• Circuit Complexity for Coherent States
• Time Evolution of Complexity: A Critique of Three Methods
• Models of quantum complexity growth
• Black holes, complexity and quantum chaos
• Universal chaotic dynamics from Krylov space
• Holographic Complexity in Vaidya Spacetimes I
• Quantum Dynamics in Krylov Space: Methods and Applications
• Emergent quantum state designs from individual many-body wavefunctions
• Complexity of Mixed States in QFT and Holography
• Complexity and the bulk volume, a new York time story
• Holographic Complexity Equals Which Action?
• The Complexity Geometry of a Single Qubit
• The First Law of Complexity
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Holographic Subregion Complexity from Kinematic Space
• Geometry of Complexity in Conformal Field Theory
• Complexity Growth Rate in Lovelock Gravity
• Cosmological Complexity
• Krylov Complexity in Quantum Field Theory
• Holographic Complexity for Defects Distinguishes Action from Volume
• Hamiltonian variational ansatz without barren plateaus
• Subregion Action and Complexity
• Complexity Growth in Integrable and Chaotic Models
• Complexity change under conformal transformations in AdS${}_3$/CFT${}_2$
• Complexity of the AdS Soliton
• Entangling power and quantum circuit complexity
• Holographic Complexity and Volume
• Evolution of complexity following a quantum quench in free field theory
• Sewing spacetime with Lorentzian threads: complexity and the emergence of time in quantum gravity
• Aspects of The First Law of Complexity
• On the time dependence of holographic complexity in a dynamical Einstein-dilaton model
• Entanglement, quantum randomness, and complexity beyond scrambling
• Post-Quench Evolution of Complexity and Entanglement in a Topological System
• Action growth rate for a higher curvature gravitational theory
• Complexity of Holographic Superconductors
• Dynamical phase transitions in sampling complexity
• Circuit Complexity From Cosmological Islands
• Cosmological Krylov Complexity
• Noncommuting conserved charges in quantum thermodynamics and beyond
• Holographic Complexity in dS${}_{d+1}$
• Circuit Complexity for Fermionic Thermofield Double states
• Quantum complexity in gravity, quantum field theory, and quantum information science
• Complexity in the presence of a boundary
• Entanglement of Purification and Multiboundary Wormhole Geometries
• Holographic complexity of anisotropic black branes
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Holographic Complexity of Quantum Black Holes
• Characterizing complexity of many-body quantum dynamics by higher-order eigenstate thermalization
• Complexity from the Reduced Density Matrix: a new Diagnostic for Chaos
• Uncomplexity and Black Hole Geometry
• Quantum aspects of chaos and complexity from bouncing cosmology: A study with two-mode single field squeezed state formalism
• Time evolution of the complexity in chaotic systems: concrete examples
• Isospectral twirling and quantum chaos
• Quantum State Complexity in Computationally Tractable Quantum Circuits
• Binding Complexity and Multiparty Entanglement
• Thoughts on Holographic Complexity and its Basis-dependence
• On Some Universal Features of the Holographic Quantum Complexity of Bulk Singularities
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Learning quantum states and unitaries of bounded gate complexity
• Nonanalyticity of circuit complexity across topological phase transitions
• Locality from the Spectrum
• Supergroup Structure of Jackiw-Teitelboim Supergravity
• Dynamical quantum ergodicity from energy level statistics
• Bounds on quantum evolution complexity via lattice cryptography
• Integrability and complexity in quantum spin chains
• Resource theory of quantum uncomplexity
• Quantum Complexity as Hydrodynamics
• Complexity growth of rotating black holes with a probe string
• Investigating two counting methods of the holographic complexity
• A Quantum Complexity Lowerbound from Differential Geometry
• Modified "complexity equals action" conjecture
• Holographic complexity in charged Vaidya black hole
• Proof of a Momentum/Complexity Correspondence
• A Generalized Momentum/Complexity Correspondence
• Evolutions of entanglement and complexity after a thermal quench in massive gravity theory
• On the time dependence of holographic complexity for charged AdS black holes with scalar hair
• Chaos and Complexity from Quantum Neural Network: A study with Diffusion Metric in Machine Learning
• Kasner interiors from analytic hairy black holes
• Magnetotransport and Complexity of Holographic Metal-Insulator Transitions
• Complexity Geometry and Schwarzian Dynamics
• Complexity of operators generated by quantum mechanical Hamiltonians
• Evolution of Holographic Complexity Near Critical Point
• Saturation of Thermal Complexity of Purification
• Holographic complexity of charged Taub-NUT-AdS black holes
• Holographic complexity for black branes with momentum relaxation
• Revisit on holographic complexity in two-dimensional gravity
• Generalized Volume-Complexity For Two-Sided Hyperscaling Violating Black Branes
• Exact universal bounds on quantum dynamics and fast scrambling
• Holographic Subregion Complexity in General Vaidya Geometry
• Complexity and order in approximate quantum error-correcting codes
• Efficient Unitary T-designs from Random Sums
• Q-curvature and Path Integral Complexity
• Bulk reconstruction of metrics inside black holes by complexity
• A quantum circuit interpretation of evaporating black hole geometry
• Quantifying the difference between many-body quantum states
• Universality in long-distance geometry and quantum complexity
• Non-perturbative Overlaps in JT Gravity: From Spectral Form Factor to Generating Functions of Complexity
• Holographic complexity of the electromagnetic black hole
• Efficient unitary designs and pseudorandom unitaries from permutations
• Estimating the randomness of quantum circuit ensembles up to 50 qubits
• Complexity and Multi-boundary Wormholes
• Primordial Gravitational Wave Circuit Complexity
• Subregion complexity in holographic thermalization with dS boundary
• Circuit Complexity in ${\mathcal{Z}}_2$ $\mathcal{EEF}\mathcal{T}$
• Hilbert-Space Ergodicity in Driven Quantum Systems: Obstructions and Designs
• Complexity growth in Gubser-Rocha models with momentum relaxation
• The Universe from a Single Particle
• Stringy Effects and the Role of the Singularity in Holographic Complexity
• Complexity measures in QFT and constrained geometric actions
• Sectional curvatures distribution of complexity geometry
• Complexity is not Enough for Randomness
• Subregion complexity and confinement-deconfinement transition in a holographic QCD model
• Complexity-constrained quantum thermodynamics
• Quantum Chaos on Complexity Geometry
• Quantum complexity and the virial theorem
• Towards the Web of Quantum Chaos Diagnostics
• To be unitary-invariant or not?: a simple but non-trivial proposal for the complexity between states in quantum mechanics/field theory
• Quantum Complexity and Chaos in Young Black Holes
• Free Independence and the Noncrossing Partition Lattice in Dual-Unitary Quantum Circuits
• Complexity and uncomplexity during energy injection
• Holographic complexity of rotating black holes with conical deficits
• Complexity Growth, Butterfly Velocity and Black hole Thermodynamics
• Saturation and recurrence of quantum complexity in random local quantum dynamics
• Holographic Complexity in a Charged Supersymmetric Black Holes
• Polynomial Equivalence of Complexity Geometries
• Properties of the (Un)Complexity of Subsystems
• Wavefunction branching: when you can't tell pure states from mixed states
• Quantum complexity phase transitions in monitored random circuits
• Complexity in algebraic QFT
• The Universe from a Single Particle III
• Complexity growth for topological black holes by holographic method
• The Universe from a Single Particle II
• Black Holes at Exp-time
• Effects of the acceleration on holographic complexity
• Generalized holographic complexity of rotating black holes
• Note on stability and holographic subregion complexity
• Weighting gates in circuit complexity and holography
• Complexity from Spinning Primaries
• Toward the nonequilibrium thermodynamic analog of complexity and the Jarzynski identity
• Universal distributions of overlaps from generic dynamics in quantum many-body systems
• Lightcone Bounds for Quantum Circuit Mapping via Uncomplexity
• Gauge fields and quantum entanglement
• Macroscopic Reality from Quantum Complexity
• Entanglement and Chaos in De Sitter Holography: An SYK Example
• The Complexity of Being Entangled
• Holographic complexity growth for a charged AdS-dilaton black holes with fixed and dynamical boundary respectively
• Kolmogorov complexity as intrinsic entropy of a pure state: Perspective from entanglement in free fermion systems
• Towards a theory of machine learning
• Coherence and Imaginarity as Resources in Quantum Circuit Complexity
• Causality Constraint on Circuit Complexity from $COSMOEFT$
• Circuit Complexity From Supersymmetric Quantum Field Theory With Morse Function
• Complexity in One- and Two-Qubit Systems
• Holographic Kolmogorov-Sinai entropy and the quantum Lyapunov spectrum
• Complexity growth rate, grand potential and partition function
• Random Circuits in the Black Hole Interior
• Wasserstein Complexity of Quantum Circuits
• On the Hardness of Detecting Macroscopic Superpositions
• Subsystem Complexity and Measurements in Holography
• Cosmological Complexity in K-essence
• What kind of "complexity" is dual to holographic complexity?
• How smooth is quantum complexity?
• Krylov complexity of purification
• Benchmarking quantum chaos from geometric complexity
• Krylov Spread Complexity of Quantum-Walks
• Quantifying High-Order Interdependencies in Entangled Quantum States
• Resource and stability near a critical point from the quantum information perspective
• Quantum fluctuation on the worldsheet of probe string in BTZ black hole
• Resource-Dependent Complexity of Quantum Channels
• Quantum Cellular Automata, Black Hole Thermodynamics, and the Laws of Quantum Complexity
• Universal Time Evolution of Holographic and Quantum Complexity
• Toward a physically motivated notion of Gaussian complexity geometry
• Holographic and QFT Complexity with angular momentum
• Attention to Quantum Complexity
• Numerical evidence for the non-Abelian eigenstate thermalization hypothesis
• On the reconstruction map in JT gravity
• Finite complexity of the de Sitter vacuum
• Non-Universality from Conserved Superoperators in Unitary Circuits
• Complexity, chaos and the moving D3-brane
• Lie groups for quantum complexity and barren plateau theory
• Geometry of quantum complexity
• Optimal quantum reservoir learning in proximity to universality
• On the stabilizer complexity of Hawking radiation
• Estimating time in quantum chaotic systems and black holes
• Circuit complexity and functionality: a thermodynamic perspective
• Holographic complexity of rotating black holes
• Probing the Black Hole Interior with Holographic Entanglement Entropy and the Role of AdS/BCFT Correspondence
• Quantum information in Riemannian spaces
• Holographic Complexity in Charged Accelerating Black Holes
• A New Look at the $C^0$-formulation of the Strong Cosmic Censorship Conjecture
• Holographic Interpretation of Relative State Complexity
• Resilience-Runtime Tradeoff Relations for Quantum Algorithms
• Vacuum Branching, Dark Energy, Dark Matter
• Comparing quantum complexity and quantum fidelity
• Quantum origin of the Minkowski space
• Probing the localization effects in Krylov basis
• Area and volume as emergent phenomena from entangled qubits
• On a Matrix Ensemble for Arbitrary Complex Quantum Systems
• Searching for emergent spacetime in spin glasses
• Anticoncentration is (almost) all you need
• Realizing Unitary $k$-designs with a Single Quench
• Holographic Subregion Complexity and Fidelity Susceptibility in Noncommutative Yang--Mills Theory
• Wavefunction branches demand a definition!
• Quantum Information Approaches to Quantum Gravity
• Chaotic D1-D5 Black Hole Dynamics through Networks
• Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians