The Second Law of Quantum Complexity
arXiv:1701.01107 · doi:10.1103/PhysRevD.97.086015
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 qubits, and the positional entropy of a related classical system with 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.
arXiv commentv2: minor improvements
References in corpus (22)
- A bound on chaos
- Gapless Spin-Fluid Ground State in a Random Quantum Heisenberg Magnet
- Comments on the Sachdev-Ye-Kitaev model
- Black Holes: Complementarity or Firewalls?
- Black holes as mirrors: quantum information in random subsystems
- Fast Scramblers
- On the Power of One Bit of Quantum Information
- Complexity Equals Action
- Complexity and Shock Wave Geometries
- The Spectrum in the Sachdev-Ye-Kitaev Model
- Complexity, action, and black holes
- The Resource Theory of Quantum States Out of Thermal Equilibrium
- Computational capacity of the universe
- The Resource Theory of Stabilizer Computation
- Multiple Shocks
- Chaos and complexity by design
- Towards the fast scrambling conjecture
- Loschmidt Echo
- Quantum Complexity and Negative Curvature
- The Typical-State Paradox: Diagnosing Horizons with Complexity
- Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
- Holographic fluctuations and the principle of minimal complexity
Cited by in corpus (217)
- Measurement-Induced Phase Transitions in the Dynamics of Entanglement
- Chaos and complexity by design
- 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 -designs in depth
- 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/CFT
- 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
- Cosmological Krylov Complexity
- Circuit Complexity From Cosmological Islands
- Complexity of Holographic Superconductors
- Dynamical phase transitions in sampling complexity
- Noncommuting conserved charges in quantum thermodynamics and beyond
- Holographic Complexity in dS
- Circuit Complexity for Fermionic Thermofield Double states
- Complexity in the presence of a boundary
- Quantum complexity in gravity, quantum field theory, and quantum information science
- Holographic Complexity of Quantum Black Holes
- Holographic complexity of anisotropic black branes
- Learning efficient decoders for quasi-chaotic quantum scramblers
- Entanglement of Purification and Multiboundary Wormhole Geometries
- Characterizing complexity of many-body quantum dynamics by higher-order eigenstate thermalization
- Complexity from the Reduced Density Matrix: a new Diagnostic for Chaos
- Quantum aspects of chaos and complexity from bouncing cosmology: A study with two-mode single field squeezed state formalism
- Uncomplexity and Black Hole Geometry
- Time evolution of the complexity in chaotic systems: concrete examples
- Isospectral twirling and quantum chaos
- Binding Complexity and Multiparty Entanglement
- Thoughts on Holographic Complexity and its Basis-dependence
- Quantum State Complexity in Computationally Tractable Quantum Circuits
- Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
- On Some Universal Features of the Holographic Quantum Complexity of Bulk Singularities
- Learning quantum states and unitaries of bounded gate complexity
- Nonanalyticity of circuit complexity across topological phase transitions
- Locality from the Spectrum
- Bounds on quantum evolution complexity via lattice cryptography
- Supergroup Structure of Jackiw-Teitelboim Supergravity
- Dynamical quantum ergodicity from energy level statistics
- 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
- A Quantum Complexity Lowerbound from Differential Geometry
- Modified "complexity equals action" conjecture
- Investigating two counting methods of the holographic complexity
- Holographic complexity in charged Vaidya black hole
- Evolutions of entanglement and complexity after a thermal quench in massive gravity theory
- A Generalized Momentum/Complexity Correspondence
- Proof of a Momentum/Complexity Correspondence
- On the time dependence of holographic complexity for charged AdS black holes with scalar hair
- Kasner interiors from analytic hairy black holes
- Chaos and Complexity from Quantum Neural Network: A study with Diffusion Metric in Machine Learning
- Magnetotransport and Complexity of Holographic Metal-Insulator Transitions
- Complexity of operators generated by quantum mechanical Hamiltonians
- Saturation of Thermal Complexity of Purification
- Evolution of Holographic Complexity Near Critical Point
- Complexity Geometry and Schwarzian Dynamics
- Revisit on holographic complexity in two-dimensional gravity
- Holographic complexity for black branes with momentum relaxation
- Holographic complexity of charged Taub-NUT-AdS black holes
- Exact universal bounds on quantum dynamics and fast scrambling
- Holographic Subregion Complexity in General Vaidya Geometry
- Generalized Volume-Complexity For Two-Sided Hyperscaling Violating Black Branes
- Complexity and order in approximate quantum error-correcting codes
- Holographic complexity of the electromagnetic black hole
- Non-perturbative Overlaps in JT Gravity: From Spectral Form Factor to Generating Functions of Complexity
- A quantum circuit interpretation of evaporating black hole geometry
- Efficient Unitary T-designs from Random Sums
- Efficient unitary designs and pseudorandom unitaries from permutations
- Universality in long-distance geometry and quantum complexity
- Q-curvature and Path Integral Complexity
- Bulk reconstruction of metrics inside black holes by complexity
- Quantifying the difference between many-body quantum states
- Estimating the randomness of quantum circuit ensembles up to 50 qubits
- Primordial Gravitational Wave Circuit Complexity
- Complexity and Multi-boundary Wormholes
- Subregion complexity in holographic thermalization with dS boundary
- Hilbert-Space Ergodicity in Driven Quantum Systems: Obstructions and Designs
- Circuit Complexity in
- Complexity growth in Gubser-Rocha models with momentum relaxation
- Stringy Effects and the Role of the Singularity in Holographic Complexity
- The Universe from a Single Particle
- Quantum Chaos on Complexity Geometry
- To be unitary-invariant or not?: a simple but non-trivial proposal for the complexity between states in quantum mechanics/field theory
- Towards the Web of Quantum Chaos Diagnostics
- Quantum complexity and the virial theorem
- Complexity measures in QFT and constrained geometric actions
- Complexity-constrained quantum thermodynamics
- Complexity is not Enough for Randomness
- Subregion complexity and confinement-deconfinement transition in a holographic QCD model
- Sectional curvatures distribution of complexity geometry
- Free Independence and the Noncrossing Partition Lattice in Dual-Unitary Quantum Circuits
- Holographic complexity of rotating black holes with conical deficits
- Quantum Complexity and Chaos in Young Black Holes
- Complexity and uncomplexity during energy injection
- Complexity Growth, Butterfly Velocity and Black hole Thermodynamics
- Polynomial Equivalence of Complexity Geometries
- Saturation and recurrence of quantum complexity in random local quantum dynamics
- Holographic Complexity in a Charged Supersymmetric Black Holes
- Quantum complexity phase transitions in monitored random circuits
- Complexity growth for topological black holes by holographic method
- The Universe from a Single Particle III
- Wavefunction branching: when you can't tell pure states from mixed states
- Properties of the (Un)Complexity of Subsystems
- The Universe from a Single Particle II
- Complexity in algebraic QFT
- Generalized holographic complexity of rotating black holes
- Lightcone Bounds for Quantum Circuit Mapping via Uncomplexity
- Effects of the acceleration on holographic complexity
- Universal distributions of overlaps from generic dynamics in quantum many-body systems
- Note on stability and holographic subregion complexity
- Complexity from Spinning Primaries
- Toward the nonequilibrium thermodynamic analog of complexity and the Jarzynski identity
- Gauge fields and quantum entanglement
- Weighting gates in circuit complexity and holography
- Black Holes at Exp-time
- Circuit Complexity From Supersymmetric Quantum Field Theory With Morse Function
- Towards a theory of machine learning
- Macroscopic Reality from Quantum Complexity
- Coherence and Imaginarity as Resources in Quantum Circuit Complexity
- The Complexity of Being Entangled
- Kolmogorov complexity as intrinsic entropy of a pure state: Perspective from entanglement in free fermion systems
- Holographic complexity growth for a charged AdS-dilaton black holes with fixed and dynamical boundary respectively
- Causality Constraint on Circuit Complexity from
- Entanglement and Chaos in De Sitter Holography: An SYK Example
- Complexity in One- and Two-Qubit Systems
- Wasserstein Complexity of Quantum Circuits
- Holographic Kolmogorov-Sinai entropy and the quantum Lyapunov spectrum
- Random Circuits in the Black Hole Interior
- Complexity growth rate, grand potential and partition function
- Cosmological Complexity in K-essence
- Resource and stability near a critical point from the quantum information perspective
- Krylov complexity of purification
- How smooth is quantum complexity?
- Quantum Cellular Automata, Black Hole Thermodynamics, and the Laws of Quantum Complexity
- Quantum fluctuation on the worldsheet of probe string in BTZ black hole
- On the Hardness of Detecting Macroscopic Superpositions
- Benchmarking quantum chaos from geometric complexity
- What kind of "complexity" is dual to holographic complexity?
- Subsystem Complexity and Measurements in Holography
- Quantifying High-Order Interdependencies in Entangled Quantum States
- Krylov Spread Complexity of Quantum-Walks
- Resource-Dependent Complexity of Quantum Channels
- Universal Time Evolution of Holographic and Quantum Complexity
- Quantum information in Riemannian spaces
- On the reconstruction map in JT gravity
- Lie groups for quantum complexity and barren plateau theory
- Numerical evidence for the non-Abelian eigenstate thermalization hypothesis
- Estimating time in quantum chaotic systems and black holes
- Holographic complexity of rotating black holes
- Geometry of quantum complexity
- Non-Universality from Conserved Superoperators in Unitary Circuits
- Optimal quantum reservoir learning in proximity to universality
- On the stabilizer complexity of Hawking radiation
- Finite complexity of the de Sitter vacuum
- Probing the Black Hole Interior with Holographic Entanglement Entropy and the Role of AdS/BCFT Correspondence
- Holographic Complexity in Charged Accelerating Black Holes
- Holographic and QFT Complexity with angular momentum
- Complexity, chaos and the moving D3-brane
- Attention to Quantum Complexity
- Toward a physically motivated notion of Gaussian complexity geometry
- Circuit complexity and functionality: a thermodynamic perspective
- Wavefunction branches demand a definition!
- Resilience-Runtime Tradeoff Relations for Quantum Algorithms
- Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians
- Holographic Subregion Complexity and Fidelity Susceptibility in Noncommutative Yang--Mills Theory
- Realizing Unitary -designs with a Single Quench
- Vacuum Branching, Dark Energy, Dark Matter
- Anticoncentration is (almost) all you need
- Comparing quantum complexity and quantum fidelity
- Area and volume as emergent phenomena from entangled qubits
- Quantum Information Approaches to Quantum Gravity
- Searching for emergent spacetime in spin glasses
- Holographic Interpretation of Relative State Complexity
- Quantum origin of the Minkowski space
- Chaotic D1-D5 Black Hole Dynamics through Networks
- Probing the localization effects in Krylov basis
- A New Look at the -formulation of the Strong Cosmic Censorship Conjecture
- On a Matrix Ensemble for Arbitrary Complex Quantum Systems