Source-linked AI summary
Computational Complexity and Black Hole Horizons
Leonard Susskind
TL;DR
The paper asks how computationally difficult it is for Alice to send a firewall through an Einstein-Rosen bridge. It models black-hole dynamics using complexity, circuits, and gauge-theory operators, finding that unbottled Hawking radiation makes firewall production exponentially difficult, whereas bottling radiation can permit firewalls after exponentially long times. These conclusions are framed for carefully selected black-hole states and assumptions about complexity growth and reversibility.
Problem
The paper studies when a disturbance at Alice’s end sends a signal through an Einstein-Rosen bridge and how difficult that task is computationally.
Method
The paper relates near-horizon geometry to computational complexity using fast-scrambling qubit, circuit, and gauge-theory descriptions.
Results
For free-streaming radiation, the operator Alice must apply has maximal, exponential-in-entropy complexity, while bottling radiation permits firewalls through extremely complex operations or recurrences.
Takeaways & Limitations
The paper concludes that firewalls typically do not exist for plausible states representing real black-hole formation unless Alice performs an exceedingly complex operation.
Takeaways & Limitations
The model assumes a fine-tuned pre-thermofield-double state, and vertical entanglement reaches its maximum by the scrambling time even as the ERB continues growing.
Abstract
from arXiv · showhide
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.
1 ER=EPR and Computational Complexity
Entanglement can connect black holes through Einstein-Rosen bridges, allowing Alice’s actions to send particles to Bob. Computational complexity quantifies how difficult it is to create such a signal and relates that difficulty to distance from the horizon.
- ER=EPR: Entanglement between a black hole and its purification is interpreted through ER=EPR as an Einstein-Rosen bridge.Examples include an evaporating black hole after the Page time and the thermofield-double state of two non-interacting CFTs.
- ER=EPR: Alice can send particles through the bridge, and a sufficiently powerful blast would constitute a firewall at Bob’s end.The mechanism for producing such particles through the ERB was explicitly exhibited in prior work.
- Computational Complexity: The central problem is determining when Alice’s disturbance traverses the ERB and how difficult that task is.ER=EPR identifies the connection but does not determine the computational difficulty of sending a signal.
- Computational Complexity: Quantum computational complexity is the minimum number of simple unitary gates needed to implement a desired unitary operation on computational qubits.Here, a simple gate is taken to act on a fixed small number of qubits, such as two.
- Complexity and Horizons: The near-horizon region is modeled as onion-like layers whose CFT descriptions become increasingly complex toward and beyond the Planckian layer.The passage connects exponentially large complexity with Hawking radiation emerging from exponentially small distances.
2 Strings and Qubits
The paper models black-hole degrees of freedom using fast-scrambling qubits and gauge-theory Wilson loops. Wilson-loop evolution increases operator complexity exponentially until it spans the full string at the scrambling time.
- Strings and Qubits: The relevant black-hole degrees of freedom can be modeled as interacting qubits that form a fast scrambler, without requiring a string model.The Hayden-Preskill circuit model is offered as an example, while the string model connects qubits to gauge-theory concepts.
- Strings and Qubits: A minimal lattice gauge-theory model uses a single cell whose N^2 degrees of freedom can describe a Hawking-Page black hole.At the Hawking-Page transition, the cell has enough degrees of freedom to represent the black-hole entropy.
- Strings and Qubits: The quantum string maps to N^2 qubits, with each qubit representing how the electric flux changes direction along the string.Wilson loops act as approximately local gauge-invariant operators that modify a few adjacent qubits.
- Wilson Loops: Wilson loops become more complex under time evolution because longer loops and additional terms are generated.Decorated Wilson loops additionally insert electric operators through link-variable time derivatives.
- Strings and Scrambling: A single-plaquette Wilson loop evolves into a superposition whose longest contribution grows exponentially because new contributions bud along its length.The growth continues until the longest contribution reaches the full string length N^2.
- Strings and Scrambling: The time for a single-plaquette operator to involve the entire string defines the scrambling time, and the resulting object is a precursor.This interpretation applies to evolution toward both the future and the past.
3 Circuits and Complexity
Circuit models represent black-hole scrambling and quantify operator complexity through gate counts and circuit depth. Scrambling occurs at polynomial complexity, while complexity can continue growing toward an exponential maximum; precursor construction also depends on imperfect reversibility.
- Circuit Models: Hayden-Preskill circuits provide a tractable substitute for intractable chaotic black-hole dynamics using K qubits.For the long-string model, K is associated with the number of links, the gauge-group rank, and black-hole entropy.
- Scrambling: Scrambling requires about K log K gates in a series circuit and a depth scaling logarithmically with K in a parallel circuit.In the parallel model, K/2 two-qubit gates act simultaneously at each time step.
- Scrambling: Scrambling is reached when each qubit has indirectly interacted with every qubit, after interactions expand exponentially across the circuit.This circuit behavior parallels the exponential growth of Wilson loops and diffusion across a black-hole horizon.
- Complexity: Circuit complexity is the minimum gate count, while in a parallel circuit it equals width times depth and is not required to track output complexity linearly.The time-step is associated with the inverse temperature or inverse energy per qubit.
- Complexity: Complexity can grow beyond scrambling until it reaches a maximum bounded by an exponential number of gates in K.The assumed intermediate regime grows linearly for some time, followed by quasi-periodic behavior on still larger timescales.
- Precursors: A precursor is implemented by applying U†, W, and U, giving an upper complexity bound proportional to N^2t/l_ads.The paper assumes the lower bound has the same order, while noting possible cancellations between U and U†.
- Precursors: Inserting W prevents the exact cancellation present when the identity is inserted because chaotic dynamics amplify small perturbations.Figure 1 contrasts exact reversal with the perturbed evolution produced by inserting W.
4 Geometry and Complexity
The section identifies black-hole near-horizon layers with increasing computational complexity and derives a relation connecting geometric distance, complexity, and entropy. It then interprets complexity’s tendency to rise as a gravity-like dynamical behavior.
- 4.1 The Layered Stretched Horizon: Near-horizon layers correspond to different complexities: outer-edge operators are minimally complex, while complexity increases inward toward the Planckian layer.The stretched horizon is modeled as an onion-like structure with many layers.
- 4.1 The Layered Stretched Horizon: Boundary representations of bulk operators become more complex as the associated bulk point moves inward toward the horizon.The outermost operator is represented using dominantly single-plaquette Wilson loops, while deeper locations involve longer boundary time intervals and more complex representations.
- 4.1 The Layered Stretched Horizon: The distance-complexity relation is fundamental because its exponent measures complexity per bit of entropy, or complexity per qubit.This relation connects geometric distance from the horizon with computational complexity and entropy.
- 4.1 The Layered Stretched Horizon: At Planck distance, the complexity equals the scrambling complexity C∗, giving the Planck length an information-theoretic interpretation.The paper identifies the Planck-distance layer with the layer where complexity reaches the scrambling value.
- 4.2 Gravity and Complexity: The proposed complexity-based description resembles a second-order theory because complexity and its rate of change are treated as independent variables.A high-complexity, time-reversal-invariant operator can have zero complexity derivative, yet complexity increases under forward or backward evolution.
- 4.2 Gravity and Complexity: Complexity generally increases away from its minimum in both forward and backward time, while nonstationary trajectories turn around at a minimum.This behavior is used to represent excitations moving away from and then back toward the horizon.
5 The Two-Sided Case
The two-sided analysis treats ERB stretching as central to horizon stability and seeks a gauge-theory quantity that tracks it beyond scrambling. Computational complexity provides that candidate, while its post-recurrence fluctuations imply possible periods of firewall vulnerability.
- 5.1 Why Start with the Thermofield-Double State?: ERB stretching occurs in both eternal two-sided and one-sided collapse black holes, red-shifting and diluting interior perturbations near the horizon.The stretching is associated with expanding spacelike slices and is taken to stabilize smooth horizons.
- 5.1 Why Start with the Thermofield-Double State?: Smooth horizons with initially stretching interiors remain smooth, at least for an exponentially long recurrence time in AdS black holes.The motivation is that real black holes begin far from equilibrium with vacuum-like horizons and interiors.
- 5.2 Dual Description of Stretching: Vertical entanglement is too crude to represent ERB length because it saturates by the scrambling time while the classical ERB continues growing.The desired gauge-theory quantity must grow throughout the period in which classical evolution remains trustworthy.
- 5.2 Dual Description of Stretching: State complexity is defined as the minimum number of gates needed to prepare the state, using product states for one-sided systems and Bell-pair products for two-sided systems.This construction applies to either one-sided or two-sided black holes with maximal horizontal entanglement and minimal vertical entanglement.
- 5.2 Dual Description of Stretching: Complexity grows long past scrambling but eventually reaches a maximum at recurrence; on doubly exponential timescales, fluctuations can shrink the ERB and expose the horizon to firewalls unless the state is near the TFD.The proposed correspondence identifies the rate of complexity change with stretching, so decreasing complexity corresponds to shrinking periods.
6 Sending Firewalls is Hard
Creating a signal or firewall behind Bob’s horizon requires Alice to act through increasingly complex and finely tuned precursors. Simple positive-time actions do not reach Bob, while errors reduce the signal’s energy and effect.
- The setup: Alice’s task is to create a high-energy shockwave behind Bob’s horizon from a two-sided TFD state.The paper frames this as a computational-complexity question.
- The setup: Alice, Bob, and the precursor are characterized by launch time tA, jump time tB, and action time t, with TFD symmetry allowing tB = 0.The effect depends only on tA + tB.
- Sending the signal: For tB = 0, Alice must act at negative tA for her signal to reach Bob before the singularity.A positive-time simple action cannot reach Bob within the regime where the semiclassical Penrose diagram applies.
- Sending the signal: At tA = −t∗, the signal becomes a Planckian shockwave, while earlier launch times drive quantum corrections beyond control.The signal energy rises as |tA| approaches the scrambling time.
- Why it is hard: A positive-time signal requires a precursor with complexity ∼C∗ + t/lads, beyond scrambling complexity, and increasing time separation demands greater fine-tuning.The precursor’s complexity increases as the fictitious launch time is separated from Alice’s actual action time.
- Why it is hard: After a scrambling time, an accidental mistake on one qubit out of S can ruin Alice’s message, because errors delay the signal and lower its energy at Bob.The error is modeled by multiplying the precursor by a one-qubit operator, and the operator ordering matters.
- Why it is hard: Measuring all S qubits is still classified as a simple disturbance when the measurement has a simple product form.Such an operation is not significantly more complex than a single-qubit operator.
7 Trans-scrambling Complexity and Generic Black Holes
Complexity determines both how long a shockwave persists near Bob’s horizon and which black-hole states can be produced by collapse. Generic states require exponentially long preparation, so slowly formed states need not share generic firewall behavior.
- Sub-planckian distances: A precursor’s complexity determines the shockwave’s location on the t = 0 surface and the time at which it falls into the singularity.The shockwave is created by a simple operator’s fictitious launch at −t.
- Sub-planckian distances: The operational meaning of the distance l_a is the duration for which the shockwave or firewall persists near Bob’s horizon.This interpretation fails at maximum complexity, where the lifetime becomes the classical recurrence time.
- Generic black holes: Rapidly collapsing black holes access only a small, nongeneric subspace of the e^S possible states.Thus smooth horizons may occur for collapse-formed black holes even if generic black holes have firewalls.
- Generic black holes: Almost all states have exponentially large complexity and cannot be formed with fewer than e^S gates.States constructed over a time of order l_ads S therefore remain special rather than representative of generic states.
- Generic black holes: Before the classical recurrence time, increasing complexity can stretch the ERB and leave room to protect the horizon; after recurrence, stretching stops and the horizon becomes more vulnerable.The paper therefore finds no reason for black holes formed much faster than recurrence to have firewalls.
8 Continuation to Interior
The paper constructs interior observables by pulling bulk fields to a time-zero slice, reconstructing them from both boundary CFTs, and evolving the result to later times. The construction is formally possible, but late-time chaos and complexity make it impractical and require approximations.
- Initial construction: A two-sided CFT state represents an entire Wheeler–DeWitt history rather than a bulk state on one spatial slice.The construction begins with the WDW patch at tL = tR = 0.
- Initial construction: For a bulk point a away from the horizon, singularity, and upper corners, bulk equations pull φ(a) back to fields on the t = 0 surface.The allowed boost angle is much less than log S.
- Boundary reconstruction: HKLL then expresses the fields on the intermediate surface using local gauge-invariant fields on both left and right boundaries.Interior reconstruction differs from exterior reconstruction because both CFTs contribute and the bifurcate horizon enters the construction.
- Boundary reconstruction: The final evolution step expresses φ(a) as a nonlocal operator WLR(a) acting on both sides at t = 0, and this operator has relatively small complexity under the stated restrictions.Gauge-theory equations of motion are used to run the boundary fields back to t = 0.
- Late-time continuation: At late equal boundary time, boosting the WDW description first restores the original configuration and then advances the left boundary by 2t.The first step sets tR to t and tL to −t; the second pushes tL to t.
- Late-time continuation: When t >> t∗, the continuation drives left dependence into the trans-scrambling regime, shrinking a geometric segment δ to the Planck length at t = t∗.The relevant complexity growth appears geometrically as sub-Planckian distances.
- Limitations: The interior description is not obstructed in principle, but chaos and complexity make even simple late-time low-energy observables impractical to compute.The construction also neglects nonlinear bulk effects and gravitational back reaction, which are assumed negligible at low energy.
9 Comments on Recurrences and Evaporation
Recurrences and evaporation distinguish bottled-up two-sided systems from evaporating black holes: complexity remains polynomial in the former but becomes exponentially difficult for radiation-only operations in the latter.
- Recurrences: Classical and quantum recurrences may invalidate the assumed late-time classical geometry, with the quantum recurrence returning the two-sided system near the TFD state.The text says classical breakdown may occur by the classical recurrence time, while quantum recurrence requires breakdown.
- Recurrences: In a finite, bottled-up ADS system, recurrences recycle states with statistical weights independent of the starting point, allowing firewall-like fluctuations.The text compares these recurrences with Boltzmann fluctuations in finite cosmological systems.
- Two-sided ADS: For the two-sided ADS case, a left precursor has complexity of order t, hence polynomial when Alice acts after polynomial time.This conclusion depends on the two subsystems evolving separately without information transfer.
- Evaporating case: In the evaporating case, continuous transfer between black hole and radiation requires a radiation-only operator V that is maximally complex, of order e^R.V can isolate a radiation degree of freedom entangled with a black-hole qubit, but its complexity is much greater than ordinary evolution operators.
- Evaporating case: Distilling Rb therefore takes exponential time, likely exceeding the black hole’s lifetime and making generic environmental firewall production unlikely.The paper states that the obstacle is even larger for evaporating black holes than for eternal ADS black holes.
10 Conclusion
The conclusion contrasts possible firewalls from extreme operations or long bottling-up with the much less favorable evaporating case, and connects complexity to near-horizon geometry and gravity.
- Conclusion: Firewalls can arise through an extremely complex operation, bottling up the system until a classical recurrence, or prolonged black-hole formation.For slowly formed black holes, the suggested firewall duration is no longer than the formation time.
- Conclusion: In the two-sided ADS case, sending a firewall through the ERB requires polynomial complexity after polynomial time, although such operations are unlikely to occur naturally.This remains small compared with the maximum complexity.
- Conclusion: For unbottled radiation, Alice’s required operator has maximal, exponential-in-entropy complexity and recurrences do not occur, making evaporation potentially eliminate firewalls.The conclusion presents evaporation as unfavorable to firewall production.
- Typical black holes: The black-hole ensemble is restricted to smooth, relatively simple states with stretching interiors and complexity far below its maximum, conditions deemed plausible for collapse-formed black holes.The low-complexity condition in the bottled-up case follows when the time is much shorter than the classical recurrence time.
- Wider implications: The complexity–geometry connection may illuminate sub-Planckian distances and relate complexity growth to gravitational phenomena such as near-horizon forces and interior stretching.The paper presents these as possible wider applications rather than established results.
A The Meaning of Small Changes
The paper defines small quantum changes operationally as transitions to orthogonal states affecting very few degrees of freedom, distinguishing them from Hilbert-space proximity.
- Meaning of small changes: Quantum states that begin close in Hilbert space remain close under unitary evolution, so quantum chaos is not defined by exponential state divergence.The inner product’s time independence preserves quantum nearness.
- Meaning of small changes: A small change is an orthogonal-state transition in which very few degrees of freedom have changed.This is the paper’s operational meaning of a small change.
- Meaning of small changes: A unitary operator near the identity produces a nearby state, and subsequent circuit evolution preserves that quantum nearness.This differs from the paper’s small-change criterion based on orthogonality and locality in degrees of freedom.
- Meaning of small changes: A traceless single-qubit Pauli operator typically produces an orthogonal state while affecting only one degree of freedom, exemplifying a small change.The example separates physical locality of the change from metric distance in Hilbert space.