Quantum Error Correction, Complexity, and Chaos

Black-hole information can be recoverable in the mathematical sense yet remain inaccessible to any observer who must finish a computation before the hole evaporates. This chapter separates three questions that are often compressed into the word scrambling: whether an encoding protects a logical algebra, whether initially simple operators spread, and whether a decoder can be implemented with bounded time and energy. The central lesson is that quantum error correction, chaotic diagnostics, and computational complexity constrain different stages of one recovery protocol; none alone supplies a microscopic theory of an evaporating black hole.

Helpful background. Semiclassical Gravity supplies the evaporation time and weak-backreaction regime used as physical clocks; Quantum Information supplies channels, recovery maps, trace distance, and decoupling; Quantum Fields in Curved Spacetime supplies the fixed-background radiation process whose correlations are at issue; and Black-Hole Information supplies the systems, algebras, and fine-grained entropy questions carried into this chapter.

Codes, chaos, and clocks

Let an isometry $V:\mathcal H_L\to\mathcal H_P$ encode a logical system $L$ into physical degrees of freedom $P=X\otimes \bar X$. Losing $X$ defines an erasure channel. Recovery from $\bar X$ is an error-correction question: does there exist a channel $\mathcal R_{\bar X}$ for which

$$\left\lVert \mathcal R_{\bar X}\!\circ\operatorname{Tr}_{X} \left(V\rho_LV^\dagger\right)-\rho_L \right\rVert_1\le\varepsilon$$

for every allowed logical state? The code subspace, erased region, norm, and error $\varepsilon$ are part of the claim. In gravity, the physical factorization may itself be approximate because constraints require dressed operators, so a finite-dimensional code is a model of a declared algebra, not a proof that spacetime literally factors into tensor factors.

Scrambling asks how rapidly local information becomes delocalized among many degrees of freedom. A useful schematic diagnostic is growth of an initially simple operator or decay of a regulated out-of-time-order correlator (OTOC). Recoverability asks whether correlations have moved into an accessible subsystem. Feasibility asks for the gates, memory, precision, collection time, and energy needed to exploit those correlations. A state can therefore be highly scrambled and information-theoretically decodable while the best known decoder is physically useless.

Route through the chapter

The chapter proceeds from structural statements to operational limits.

1. Black Holes as Approximate Quantum Codes defines the logical algebra, erasure, recovery channel, and approximation norm. It explains why the code subspace cannot be enlarged without cost.
2. Scrambling and the Fast-Scrambling Scale derives logarithmic spreading from exponential operator growth while retaining the temperature and interaction assumptions.
3. Out-of-Time-Order Correlators and Lyapunov Growth states the thermal analyticity theorem and distinguishes its upper bound from universal saturation.
4. Hayden–Preskill Recovery derives a finite-dimensional decoupling estimate for an old hole and counts the new radiation needed beyond the message size.
5. Decoding Complexity and Harlow–Hayden Obstructions compares exact small-system enumeration with asymptotic hardness claims and the evaporation clock.
6. Complexity, Interiors, and Late-Time Dynamics asks what invariant, state-dependent prediction would turn a geometric complexity analogy into a testable physical proposal.

The recovery and complexity distinction is explicit in Harlow 2016, §§ 5.4 and 8.1 and Appendix E: existence of a decoding map does not imply an efficient circuit for it. Likewise, Hayden and Preskill’s decoupling calculation assumes an old hole, access to early radiation, and sufficiently mixing dynamics; its quantitative statement is in Hayden and Preskill 2007, § 3, equations (3)–(7).

Results and open questions through 2026-08-19

The evidence cutoff for this chapter is 2026-08-19. The rows below compare results with different logical force rather than treating them as interchangeable evidence for one broad slogan.

Model or argument and evidence	Controlled result	Scope or limitation
Finite code subspace and erasure recovery in Almheiri, Dong, and Harlow 2015, §§ 2–4	Redundant boundary representations realize exact error correction in the idealized algebraic setting and motivate approximate recovery.	The code subspace and factorization are declared; this is not a construction for every black-hole microstate.
Random-unitary old-hole model in Hayden and Preskill 2007, § 3, equations (3)–(7)	Decoupling makes a small injected message recoverable after only a small radiation overhead.	Haar-like mixing, early-radiation access, and an information-theoretic decoder are assumptions.
Thermal analytic OTOC in Maldacena, Shenker, and Stanford 2016, §§ 2–4	Under boundedness, analyticity, and factorization, the early growth exponent obeys $\lambda_L\le 2\pi/\beta$.	Free and integrable systems need not have an exponential window, and saturation is not part of the theorem.
Circuit-complexity obstruction in Harlow and Hayden 2013, §§ 2–4	Complexity assumptions can make the AMPS distillation task take longer than the relevant black-hole lifetime.	The strongest exponential lower bound is conditional, circuit-model dependent, and not a universal theorem about every decoder.

One competing position treats rapid scrambling plus decoupling as the decisive mechanism: information is present in the radiation, so an inefficient observer does not threaten unitarity. A more conservative position demands a feasible, gravitationally dressed protocol before interpreting that correlation as an operational escape from an interior consistency problem. The controlled finite-system theorems support recoverability under named assumptions; it remains unresolved whether realistic evaporation dynamics and quantum gravity provide the same encoding, access model, and complexity protection.

What the results do not establish

An OTOC is ordering- and regulator-dependent, and its early exponential window does not by itself measure entropy production. A decoupling theorem proves closeness in a stated norm averaged over an ensemble or design; it does not write down a low-depth decoder. A complexity conjecture can protect an observer from completing a paradoxical experiment without explaining how the interior is encoded. Conversely, failure to find an efficient algorithm is not a proof of fundamental information loss.

This chapter does not redevelop generic quantum-information theory, stable black-hole thermodynamics, or explicit string and holographic constructions. Those subjects remain separate; here they enter only through declared encodings, clocks, and controlled limits. Every later comparison therefore keeps four labels visible: theorem, finite model, semiclassical extrapolation, and conjectured microscopic interpretation.

The conclusions could change after a rigorous average-case decoder lower bound changes the complexity claim, or a controlled evaporating model supplies a different recovery channel, or a gravitational protocol demonstrates bounded-energy decoding before evaporation while retaining the stated error and backreaction limits.

Check your understanding

Suppose a theorem gives a recovery channel with trace-distance error $\varepsilon=10^{-6}$, but every known implementation uses $2^S$ elementary gates while the available proper time permits only a polynomial in $S$. Which claims have and have not been established?

Solution

The theorem establishes information-theoretic recoverability for the declared code, erasure, state class, and norm. It does not establish feasible recovery: the gate count exceeds the stated time budget unless an algorithm with a better scaling is found. The complexity observation also does not prove information loss or a smooth interior; it only blocks this implementation of the protocol under the assumed computational and physical clock models.

References

• Almheiri, Ahmed, Xi Dong, and Daniel Harlow. 2015. “Bulk Locality and Quantum Error Correction in AdS/CFT.” Journal of High Energy Physics 04, 163. arXiv:1411.7041.
• Harlow, Daniel, and Patrick Hayden. 2013. “Quantum Computation versus Firewalls.” Journal of High Energy Physics 06, 085. arXiv:1301.4504.
• Harlow, Daniel. 2016. “Jerusalem Lectures on Black Holes and Quantum Information.” Reviews of Modern Physics 88, 015002. arXiv:1409.1231.
• Hayden, Patrick, and John Preskill. 2007. “Black Holes as Mirrors: Quantum Information in Random Subsystems.” Journal of High Energy Physics 09, 120. arXiv:0708.4025.
• Maldacena, Juan, Stephen H. Shenker, and Douglas Stanford. 2016. “A Bound on Chaos.” Journal of High Energy Physics 08, 106. arXiv:1503.01409.