Complexity & Black Holes

After a black hole thermalizes, its entropy stops growing, it has reached maximum entropy. Yet something remarkable continues: the black hole interior keeps growing. The Einstein-Rosen bridge connecting two sides of an eternal black hole stretches for an exponentially long time after thermalization. What controls this continued growth? Leonard Susskind proposed a radical answer: computational complexity.

This insight connects three seemingly disparate fields, gravity, information theory, and computational complexity, in a way that may reveal something deep about the nature of spacetime itself.

Entropy vs. Complexity

To understand why complexity matters for black holes, we must first understand how it differs from entropy. Consider a quantum system with $N$ qubits:

• Entropy measures the number of microstates consistent with the macroscopic description. It reaches its maximum value $S_{\max} \sim N$ after a time $t_{\text{therm}} \sim \beta \log N$.
• Complexity measures the minimum number of elementary quantum gates needed to prepare the state from a simple reference state. It continues to grow long after entropy has saturated, reaching its maximum $\mathcal{C}_{\max} \sim e^N$ after an extraordinarily long time $t \sim e^{e^N}$.

The vast gap between these timescales is the key observation. Long after the black hole looks thermally featureless from the outside, its interior geometry continues to evolve, becoming more and more complex.

Holographic Complexity Conjectures

Susskind and collaborators proposed concrete geometric formulas for the complexity of the boundary state:

Complexity = Volume (CV)

The complexity of the boundary state equals the volume of the maximal spatial slice $\Sigma_{\max}$ anchored to the boundary:

where $G_N$ is Newton's constant and $\ell$ is a length scale associated with the geometry (typically the AdS radius). The maximal slice is the one that maximizes the spatial volume, and crucially, this volume grows linearly with time for an exponentially long period, matching the expected behavior of complexity.

Complexity = Action (CA)

An alternative proposal identifies complexity with the gravitational action evaluated on the Wheeler-DeWitt patch, the causal diamond determined by the boundary time slice:

The Wheeler-DeWitt patch is the region of spacetime bounded by light sheets sent from the boundary. This formulation has the advantage of being coordinate-invariant and naturally incorporating contributions from the singularity.

Complexity = Anything (C = A)

In 2022, Belin, Myers, Ruan, Sarosi, and Speranza showed that many different bulk quantities satisfy all the expected properties of holographic complexity. Any functional of the bulk geometry that (1) grows linearly at late times, (2) is UV-divergent, and (3) satisfies a "switchback" condition qualifies. This "Complexity = Anything" result raises a profound question: is the holographic dual of complexity unique, or is the correspondence more flexible than expected?

Scrambling and Quantum Chaos

Before a system can develop complexity, it must first scramble. Scrambling is the process by which initially local quantum information spreads across all degrees of freedom.

The MSS Bound

Maldacena, Shenker, and Stanford (2016) proved a fundamental quantum bound on the rate of chaos. Chaos is measured by the Lyapunov exponent $\lambda_L$, which governs the exponential growth of out-of-time-order correlators (OTOCs):

The MSS bound states:

where $\beta = 1/T$ is the inverse temperature. Black holes saturate this bound, they are maximally chaotic. This saturation is a key diagnostic of holographic systems and a hallmark of quantum gravity.

The SYK Model

The Sachdev-Ye-Kitaev (SYK) model provides a concrete, solvable quantum-mechanical system where all of these ideas can be tested. It consists of $N$ Majorana fermions with random all-to-all interactions:

where the couplings $J_{ijkl}$ are drawn from a Gaussian distribution. Despite its simplicity, the SYK model exhibits remarkable properties:

• Maximal chaos: It saturates the MSS bound $\lambda_L = 2\pi/\beta$, just like a black hole.
• Holographic dual: At low energies, it is dual to Jackiw-Teitelboim (JT) gravity, a 2D dilaton gravity theory.
• Fast scrambling: Information scrambles in time $t_{\text{scr}} \sim \beta \log N$.
• Non-Fermi liquid: It describes a strongly interacting quantum system with no quasiparticles, bridging condensed matter and quantum gravity.

The Second Law of Complexity

Brown and Susskind proposed a "second law of complexity" analogous to the second law of thermodynamics:

This "law" is statistical, not absolute. The key differences from the thermodynamic second law are:

• Complexity grows for much longer than entropy (exponentially longer).
• The complexity maximum is doubly exponential: $\mathcal{C}_{\max} \sim e^S$.
• The second law of complexity may explain the arrow of time at a deeper level than the thermodynamic second law, since complexity growth persists long after thermal equilibrium is reached.

Python's Lunch

Brown, Gharibyan, Penington, and Susskind (2020) showed that the computational difficulty of reconstructing the interior of a black hole is geometrized by a structure they call the "Python's Lunch." In certain spacetimes, the wormhole contains a region where the cross-sectional area expands between two quantum extremal surfaces, a "bulge" reminiscent of a snake digesting its prey.

where $\Delta S = S_{\text{non-min}} - S_{\text{min}}$ is the entropy difference between the non-minimal and minimal quantum extremal surfaces. This geometrizes the difficulty of decoding Hawking radiation: the bigger the bulge, the harder it is to reconstruct the interior from the radiation.

Singularity Theorems from Complexity

A striking recent development (Mohan, 2025) uses the second law of complexity to prove a new type of singularity theorem for black holes. The classical Penrose singularity theorem relies on energy conditions (constraints on the stress-energy tensor). The new result replaces energy conditions with the existence of "trapped extremal surfaces" and the monotonicity of complexity, showing that null geodesic incompleteness follows from complexity growth inside globally hyperbolic black holes.

Experimental Signatures

In 2022, Jafferis, Zlokapa, Lykken, Kolchmeyer, Davis, Lauk, Neven, and Spiropulu implemented a sparse version of the SYK model on Google's Sycamore quantum processor. Using 9 qubits, they observed dynamics consistent with traversable wormhole teleportation, a protocol where quantum information passes through the wormhole. This remains actively debated: while it is the first experimental realization of a holographic system on a quantum computer, the small system size makes it difficult to distinguish holographic behavior from generic quantum dynamics.

Key Insights

• Complexity, not entropy, controls the growth of the black hole interior, this is the key insight linking computation to gravity.
• The CV and CA conjectures provide concrete geometric formulas for holographic complexity, though the "C = Anything" result raises questions about uniqueness.
• Black holes are the fastest scramblers in nature, saturating the MSS chaos bound $\lambda_L \leq 2\pi/\beta$.
• The SYK model is a solvable microscopic laboratory for testing complexity-gravity connections.
• The second law of complexity may explain the arrow of time at a deeper level than thermodynamics.
• Python's Lunch geometrizes the computational difficulty of decoding Hawking radiation.
• Complexity-based singularity theorems derive geometry from information, a striking hint that complexity and gravity are deeply intertwined.