Computational complexity and black hole horizons
2016/01/01 by Leonard Susskind · 784 citations
Physics and Astronomy · #Algorithm #Astronomy #Black Holes and Theoretical Physics #Black hole (networking) #Charged black hole #Computational complexity theory #Computer science #Computer security #Cosmology and Gravitation Theories #Event horizon #Extremal black hole #Firewall (physics) #Horizon #Noncommutative and Quantum Gravity Theories #Physics #Scrambling #Theoretical computer science #Theoretical physics
paper · doi:10.1002/prop.201500092
published in Fortschritte der Physik 64(1), 24-43 (Wiley)
openalex publication_date 2016/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Abstract
Computational complexity is essential to understanding the properties of black hole horizons. The problem of Alice creating a firewall behind the horizon of Bob's black hole is a problem of computational complexity. In general we find that while creating firewalls is possible, it is extremely difficult and probably impossible for black holes that form in sudden collapse, and then evaporate. On the other hand if the radiation is bottled up then after an exponentially long period of time firewalls may be common. It is possible that gravity will provide tools to study problems of complexity; especially the range of complexity between scrambling and exponential complexity.
Citations
Cited by
- Grand Canonical vs Canonical Krylov Complexity in Double-Scaled Complex SYK Model
- Holographic Complexity Equals Bulk Action?
- Page transition for the complexity of an evaporating black hole
- Holographic Learning from Fermionic Spectra: Application to Strange Metal Phenomenology
- The Normalised Wigner Negativity Rate as a Second-Moment Probe of Infall in AdS3
- The Information Content of Krylov Observables: A Machine Learning Approach
- Circuit and Krylov complexity of primordial perturbations of modified gravity in inflation
- Non-perturbative saturation of Krylov complexity, and its implications in quantum gravity
- Growth and collapse of subsystem complexity under random unitary circuits
- Finite Cutoff Jackiw–Teitelboim (JT) Gravity: Baby Universes, Matrix Dual, and (Krylov) Complexity
- The Philosophy and Physics of Duality
- Complexity measures in QFT and constrained geometric actions
- The Construction Interpretation: Conceptual Roads to Quantum Gravity
- Black hole chemistry: The first 15 years
- DeComp2: Description Complexity aware Decomposition
- Entanglement Entropy and Complexity of Multicomponent Universe from Holography
- Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality
- Revival Dynamics from Equilibrium States: Scars from Chords in SYK
- Lanczos Meets Orthogonal Polynomials
- Holographic Fisher Information Metric in Schrödinger Spacetime
- Probing the Singularity of Scalar-Haired Black Holes with Holographic Complexity
- Krylov complexity in quantum field theory, and beyond
- The Scrooge ensemble in many-body quantum systems
- Explicit Connections Between Krylov and Nielsen Complexity
- Application of Solving Inverse Scattering Problem in Holographic Bulk Reconstruction
- Spread and circuit complexity as a measure of particle content and phase space fluctuations
- Quantum Complexity of Nonlocal Field Theories
- Timelike Holographic Complexity
- The Geometry of Quantum Complexity in Open Systems
- Complexity, chaos and the moving D3-brane
- Evaporating Black Hole Interior and Complexity Evolution
- Cosmological Complexity in K-essence
- Complexity in One- and Two-Qubit Systems
- Searching for emergent spacetime in spin glasses
- Generating pseudo-random unitaries with a Floquet driven chaotic quantum system
- Holography of K-complexity: Switchbacks and Shockwaves
- De Sitter holographic complexity from Krylov complexity in DSSYK
- Aspects of holographic complexity and volume of the black holes
- Evolution With(out) Time: Relational Holography & BPS Complexity Growth in N=2 Double-Scaled SYK
- Tripartite entanglement in the HaPPY code is not holographic
- Entanglement Entropy and Complexity in Dyonic Quantum Black Holes
- Lower bounds on the complexity of preparing mixed states
- Black Hole Entropy and Complexity Growth in Horndeski Gravity within the AdS/BCFT Framework
- Quantum circuit complexity for linearly polarized light
- Chaotic D1-D5 Black Hole Dynamics through Networks
- Gravity Dual of Quantum Information Metric
- Exact Relation Between Wehrl-Rényi Entropy and Many-Body Entanglement
- Complexity and order in approximate quantum error-correcting codes
- Krylov Complexity for Open Quantum System: Dissipation and Decoherence
- Late Time Correlation Functions, Baby Universes, and ETH in JT Gravity
- Gluon scattering amplitudes with instantons and minimal surfaces with topology change
- More on Holographic Volumes, Entanglement, and Complexity
- Probing the Black Hole Interior with Holographic Entanglement Entropy and the Role of AdS/BCFT Correspondence
- De Sitter Complexity Grows Linearly in the Static Patch
- The Firewall Paradox
- The Second Law of Quantum Complexity
- Quantum circuit complexity and unsupervised machine learning of topological order
- The Cost of Nonlocality: A Dynamical Performance Equation of Energy-Entanglement-Complexity
- Universal Time Evolution of Holographic and Quantum Complexity
- CFT Complexity and Penalty Factors
- Planckian bound on quantum dynamical entropy
- What kind of "complexity" is dual to holographic complexity?
- A thermofield-double model of Uhlmann anholonomy
- Quantum Cellular Automata, Black Hole Thermodynamics, and the Laws of Quantum Complexity
- A simple analysis of the mixed-state information metric in AdS3/CFT2
- Complexity Growth of Dyonic Black holes with Quartic Field Strength Corrections
- Wigner's friend's black hole adventure: an argument for complementarity?
- On tests for baby universes in AdS/CFT
- On the reconstruction map in JT gravity
- Geometry of Chord Intertwiner, Multiple Shocks and Switchback in Double-Scaled SYK
- The quantum measurement problem: a review of recent trends
- The Holography of Spread Complexity: A Story of Observers
- Complexity equals anything for multi-horizon black holes
- Is Complexity an Illusion?
- Holographic complexity growth for a charged AdS-dilaton black holes with fixed and dynamical boundary respectively
- Wigner negativity, random matrices and gravity
- Black hole chemistry: thermodynamics with Lambda
- Building the Holographic Dictionary of the DSSYK from Chords, Complexity & Wormholes with Matter
- Holographic entanglement entropy and complexity for the cosmological braneworld model
- Time dependent Interface in AdS Black Hole Spacetime
- Emergent Gravity in a Holographic Universe
- Rethinking quantum information in gravity and fields
- Dear Qubitzers, GR=QM
- On the energy balance of Newtonian Gravitation
- Does boundary distinguish complexities?
- Complexity and shock wave geometries
- Building tensor networks for holographic states
- The ghost in the radiation: robust encodings of the black hole interior
- Holographic complexity is nonlocal
- Circuit complexity for fermionic thermofield double states
- Complexity and typical microstates
- Holographic complexity of “black” non-susy D3-brane and the high temperature limit
- Subregion holographic complexity and renormalization group flows
- Subsystem complexity after a local quantum quench
- Deep learning and AdS/QCD
- On the time dependence of holographic complexity in a dynamical Einstein-dilaton model
- Localized shocks
- Conformal bootstrap to Rényi entropy in 2D Liouville and super-Liouville CFTs
- Chemistry and complexity for solitons in AdS 5
- Average Spread Complexity and the Higher-Order Level Spacing
- Thoughts on holographic complexity and its basis dependence
- Butterflies with rotation and charge
- Complexity and entanglement for thermofield double states
- Complexity growth with Lifshitz scaling and hyperscaling violation
- Action growth for black holes in modified gravity
- Dual field theories of quantum computation
- Post-quench evolution of complexity and entanglement in a topological system
- Complexity change under conformal transformations in AdS3/CFT2
- WdW-patches in AdS3 and complexity change under conformal transformations II
- Lorentzian Threads as Gatelines and Holographic Complexity
- Complexity for an open quantum system
- Comments on joint terms in gravitational action
- Diving into traversable wormholes
- Complexity growth in flat spacetimes
- A bound on holographic entanglement entropy from inverse mean curvature flow
- Black Hole Singularities from Holographic Complexity
- Quantum State Complexity in Computationally Tractable Quantum Circuits
- Fast-forwarding of Hamiltonians and exponentially precise measurements. [europepmc]
- Solvable models of quantum black holes: a review on Jackiw-Teitelboim gravity. [europepmc]
- Universality in long-distance geometry and quantum complexity. [europepmc]
- Interior Microstates and Black Hole Entropy. [europepmc]
Related