In certain universes, everything that happens inside a region of space is completely described by a quantum system living on its boundary, the way a hologram stores a 3D picture on a flat film. The translation between the two is strange. A point deep inside is not stored in any one place on the boundary. It is spread out redundantly, like a message protected by an error-correcting code, so you can lose part of the boundary and still recover it. Take that seriously, and the question of what happens to information that falls into a black hole becomes a question about decoding. Decoding can be very hard.
Area is entanglement
AdS/CFT says that quantum gravity in anti-de Sitter space is the same theory as a conformal field
theory on its boundary, written in different variables. In 2006 Ryu and Takayanagi proposed that
the entanglement entropy of a boundary region A equals the area of the minimal bulk
surface anchored on the edge of A, divided by 4GN. For a
two-dimensional CFT this reproduces the Calabrese–Cardy formula exactly, with the central charge
set by Newton's constant through c = 3R/2GN. The formula has since been
derived from the gravitational path integral, made covariant, and corrected at one loop by the
entanglement of bulk fields. Its modern form, due to Engelhardt and Wall, extremizes a
generalized entropy:
S(A) = minX extX [ Area(X) / 4GN + Sbulk(ΣX) ]
The figure is a constant-time slice of AdS3, drawn as the Poincaré disk, where minimal
surfaces are geodesics: arcs of circles that meet the rim at right angles. Pick two boundary regions.
There are two ways to join their four endpoints with geodesics, and the entropy of
A∪B is set by whichever pair is shorter. The choice flips abruptly, and when it does,
so does which part of the bulk the boundary regions own.
Two regions, two candidate surfaces
The shaded region is the entanglement wedge: the bulk region between a
boundary region and its minimal surface. Dong, Harlow and Wall showed that any bulk operator in the
entanglement wedge of A can be rebuilt from operators on A alone, and
Cotler and collaborators gave an explicit recovery map. With the surfaces joined, A
and B together own a region deep in the bulk that neither owns by itself.
Space as a code
Almheiri, Dong and Harlow noticed that this is exactly how a quantum error-correcting code behaves.
Split the boundary into thirds A, B, C. The point at the
centre of the disk lies outside what any single third can see, yet it can be reconstructed from
A∪B, from B∪C, or from A∪C. The simplest code with that
property is the three-qutrit secret-sharing code: any two qutrits recover the message, and any one
of them alone is maximally mixed. In this language the bulk is the logical space, the boundary is
the physical space, and depth into the bulk measures how much of the boundary you need to hold to
recover a piece of information.
Pastawski, Yoshida, Harlow and Preskill then built explicit codes of this kind out of perfect tensors, tensors that are maximally entangled across every way of splitting their legs, tiled over the hyperbolic disk. The Ryu–Takayanagi formula holds exactly in many of them. They are tensor networks, the same objects that describe low-energy states of spin chains, which is the subject of Writing down a ground state.
Black holes, 2019 edition
Hawking's calculation says a black hole radiates thermally, and that each emitted quantum is entangled with a partner that stays behind the horizon. The entropy of the radiation then grows for as long as the black hole shines. When it has evaporated completely, a pure state has turned into a mixed one, and information is lost. Page pointed out in 1993 that if evaporation is unitary, the entropy of the radiation has to turn over once the black hole has given up about half its entropy. That turnover is the Page curve, and the moment it happens is the Page time.
Two further results made the problem sharp. Hayden and Preskill showed that after the Page time, anything thrown into the black hole comes back out in the radiation very quickly, assuming fast scrambling dynamics and an observer who controls the radiation. Almheiri, Marolf, Polchinski and Sully argued that three things cannot all be true: the radiation is pure, ordinary field theory holds near the horizon, and an infalling observer sees nothing unusual. Their most conservative way out was a firewall at the horizon.
In 2019 Penington, and separately Almheiri, Engelhardt, Marolf and Maxfield, applied the quantum extremal surface formula to an evaporating black hole. At the Page time the surface jumps to just inside the horizon, and the entropy follows the Page curve. The region behind that surface, now counted as part of the radiation, is an island. Two groups then derived the island rule from the gravitational path integral, where it comes from replica wormholes.
S(Rad) = minX extX [ Area(X) / 4GN + S(ΣRad ∪ ΣIsland) ]
The Page curve
Schematic, for a four-dimensional black hole evaporating into empty space: its mass falls as (1 − t/tevap)1/3, so its entropy falls as the 2/3 power. Hawking's curve keeps rising because each emitted quantum is entangled with a partner behind the horizon. The radiation cannot be more entangled with the black hole than the black hole has room for, so a unitary evaporation has to turn over. The island formula produces exactly that turn.
The island formula gets the entropy of the radiation right. It says nothing about how anyone would actually get the information out, and that turns out to be the more interesting question.
Getting it out
To test the firewall argument, an observer has to collect the radiation, decode it far enough to extract the qubit entangled with a mode near the horizon, and then jump in. Harlow and Hayden asked in 2013 how long the decoding takes. They conjectured, without being able to prove it, that it is in general exponential in the entropy of the remaining black hole, while in four dimensions the black hole evaporates in a time that scales only as that entropy to the 3/2 power. Their evidence was complexity-theoretic: a polynomial-time decoder for every correctable form of noise would imply QSZK = BQP. Aaronson later sharpened this. An efficient decoder would put SZK inside BQP, and if injective one-way functions exist that quantum computers cannot invert, decoding is hard.
Longer than the black hole lasts
The lifetime is the standard estimate tevap ≈ 5120π (M/mP)3 tP for emission into massless fields, which gives about 1067 years for a solar mass. The decoding bar assumes a computer that performs one operation per Planck time and needs 2S of them. The lifetime has about a hundred digits. The decoding time has about 1076.
Complexity has kept showing up since. Susskind proposed that the growing volume of the wormhole behind a black hole's horizon measures the complexity of the boundary state, and Brown and collaborators made a version of that proposal with the gravitational action instead. The Python's lunch of Brown, Gharibyan, Penington and Susskind estimates the cost of reconstructing the interior as exponential in the difference between the largest and smallest areas along the way. Bouland, Fefferman and Vazirani argued that if the CFT's dynamics is pseudorandom, which they conjecture and support with a query lower bound, then either the AdS/CFT dictionary is exponentially complex or the quantum extended Church–Turing thesis fails in quantum gravity. Akers, Engelhardt, Harlow, Penington and Vardhan described the late-time interior with non-isometric codes whose consistency is protected by computational complexity.
The newest work treats gravity and cryptography as two views of one thing. Brakerski showed that hardness of decoding black-hole radiation is existentially equivalent to quantum cryptography such as bit commitment. Engelhardt and collaborators proved a form of cryptographic censorship: if the boundary time evolution is approximately pseudorandom on a code subspace, the bulk must have an event horizon. Akers and collaborators found states that obey the Ryu–Takayanagi formula for different geometries yet are computationally indistinguishable, so reconstructing the geometry can be hard even when reconstructing operators is easy. Underneath several of these results sits one computational problem.
The Uhlmann transformation problem
Take two pure states |C⟩ and |D⟩ on systems A and
B, with reduced states ρ and σ on A.
Uhlmann's theorem says that the best overlap you can reach by acting on B alone equals
the fidelity of the A sides:
F(ρ, σ) = maxU |⟨D| (id ⊗ U) |C⟩|²
The theorem promises that the unitary U exists. Bostanci, Efron, Metger, Poremba, Qian
and Yuen asked how hard it is to apply. In the Uhlmann transformation
problem you are given the circuits that prepare |C⟩ and |D⟩ on 2n
qubits, and a register B that may be entangled with something you cannot touch. The
task is to apply the Uhlmann unitary to B coherently, so that |C⟩ becomes
|D⟩ and the entanglement with the outside survives.
Find the Uhlmann unitary
Two entangled states of qubits A and B:
|ψ⟩ = cos θ|00⟩ + sin θ|11⟩, and a target |φ⟩ of the same form whose B
side has been turned by a hidden angle. You may only act on B. Uhlmann's theorem says the best
overlap you can reach equals the fidelity of the two A sides, and here it reduces to
|cos(θ − θ′)|. With one qubit on B, one dial finds the optimum. With n qubits on B
the optimal unitary is a 2n × 2n matrix, and whether it can be applied
efficiently is the Uhlmann transformation problem.
To study this they built a complexity theory of unitary synthesis, with classes such as unitaryBQP and unitaryPSPACE, average-case versions like avgUnitaryBQP, and zero-knowledge classes avgUnitaryHVPZK and avgUnitaryHVSZK. Uhlmann with fidelity exactly one is complete for avgUnitaryHVPZK. Completeness for the statistical zero-knowledge class is conjectured, and would follow from a unitary version of the polarization lemma that nobody has proved. A succinct version, where the circuits can have exponential size, is complete for avgUnitaryPSPACE and for avgUnitaryQIP, so those two classes are equal.
The applications are what make it more than a definition. Uhlmann is hard on average exactly when secure quantum commitments exist. Decoding a decodable noisy channel is efficient exactly when Uhlmann is. Breaking any falsifiable quantum cryptographic assumption reduces to succinct Uhlmann, unless the assumption is secure against unbounded adversaries. And the Harlow–Hayden decoding task is efficient exactly when a distributional version of Uhlmann is. The firewall question, quantum cryptography and quantum Shannon theory all route through the same transformation.
Why we need quantum input complexity theory
A decision problem takes a string of bits and returns one bit. The Uhlmann problem takes a quantum
register, possibly entangled with a system outside your control, and has to transform it in place.
Its input is quantum and so is its output, and there is no way to write "apply
Ux to this register without disturbing its entanglement with the outside" as
a language. Bostanci and coauthors say it directly: these tasks cannot easily be characterized using
traditional complexity theory, which focuses on tasks with classical inputs and outputs.
The gap is real, and there is evidence for it. Kretschmer gave a quantum oracle relative to which BQP = QMA and yet pseudorandom states and unitaries exist. Kretschmer, Qian, Sinha and Tal gave a classical oracle relative to which P = NP and pseudorandom states still exist. Quantum cryptography, and the hardness of problems like Uhlmann, can survive collapses of classical complexity classes that would destroy classical cryptography. Aaronson points out that we do not even know whether P = PSPACE would make Harlow–Hayden decoding easy.
States and unitaries also behave differently from each other. Aaronson and Kuperberg asked in 2007 whether every n-qubit unitary can be implemented with polynomially many queries to some classical oracle. Rosenthal showed that every state can be prepared in polynomial time with a single query to a classical oracle. Lombardi, Ma and Wright showed that one query is not enough for unitaries, even approximately, although one-query algorithms can decide any language and prepare any state. For states, Metger and Yuen proved statePSPACE = stateQIP, a quantum-output analogue of QIP = PSPACE.
These are the questions I find most interesting. Is Uhlmann complete for avgUnitaryHVSZK, and is there a unitary polarization lemma? What is the right notion of reduction when the input is a state that cannot be copied? Which classical theorems carry over to quantum inputs, and which fail? The worst-case version of avgUnitaryQIP = avgUnitaryPSPACE is still open. And on the physics side, if decoding Hawking radiation is Uhlmann-hard, what exactly is that hardness protecting?
About the figures. The disk is a constant-time slice of pure AdS3, and
geodesic lengths use the vacuum formula (c/3) log[(L/πε) sin(πℓ/L)] with a cut-off
ε = L/1000. The cut-off cancels in the comparison, so where the surfaces jump does not
depend on it. The Page curve is schematic. The decoding bar assumes exactly 2S steps,
which is a conjecture about the typical case and not a theorem. The Uhlmann toy uses real rotations,
which are enough for these states.
Sources
- Ryu, Takayanagi. Holographic derivation of entanglement entropy from AdS/CFT (2006). hep-th/0603001
- Hubeny, Rangamani, Takayanagi. A covariant holographic entanglement entropy proposal (2007). arXiv:0705.0016
- Lewkowycz, Maldacena. Generalized gravitational entropy (2013). arXiv:1304.4926
- Faulkner, Lewkowycz, Maldacena. Quantum corrections to holographic entanglement entropy (2013). arXiv:1307.2892
- Engelhardt, Wall. Quantum extremal surfaces (2014). arXiv:1408.3203
- Calabrese, Cardy. Entanglement entropy and quantum field theory (2004). hep-th/0405152
- Almheiri, Dong, Harlow. Bulk locality and quantum error correction in AdS/CFT (2014). arXiv:1411.7041
- Pastawski, Yoshida, Harlow, Preskill. Holographic quantum error-correcting codes (2015). HaPPY. arXiv:1503.06237
- Dong, Harlow, Wall. Reconstruction of bulk operators within the entanglement wedge (2016). arXiv:1601.05416
- Cotler, Hayden, Penington, Salton, Swingle, Walter. Entanglement wedge reconstruction via universal recovery channels (2017). arXiv:1704.05839
- Page. Information in black hole radiation (1993). hep-th/9306083
- Hayden, Preskill. Black holes as mirrors (2007). arXiv:0708.4025
- Almheiri, Marolf, Polchinski, Sully. Black holes: complementarity or firewalls? (2012). arXiv:1207.3123
- Penington. Entanglement wedge reconstruction and the information paradox (2019). arXiv:1905.08255
- Almheiri, Engelhardt, Marolf, Maxfield. The entropy of bulk quantum fields and the entanglement wedge of an evaporating black hole (2019). arXiv:1905.08762
- Almheiri, Mahajan, Maldacena, Zhao. The Page curve of Hawking radiation from semiclassical geometry (2019). Islands. arXiv:1908.10996
- Penington, Shenker, Stanford, Yang. Replica wormholes and the black hole interior (2019). arXiv:1911.11977
- Almheiri, Hartman, Maldacena, Shaghoulian, Tajdini. Replica wormholes and the entropy of Hawking radiation (2019). arXiv:1911.12333
- Almheiri, Hartman, Maldacena, Shaghoulian, Tajdini. The entropy of Hawking radiation (2020). Review. arXiv:2006.06872
- Harlow, Hayden. Quantum computation vs. firewalls (2013). arXiv:1301.4504
- Aaronson. The complexity of quantum states and transformations: from quantum money to black holes (2016). Lecture notes; Lecture 6. arXiv:1607.05256
- Susskind. Computational complexity and black hole horizons (2014). arXiv:1402.5674
- Stanford, Susskind. Complexity and shock wave geometries (2014). arXiv:1406.2678
- Brown, Roberts, Susskind, Swingle, Zhao. Holographic complexity equals bulk action? (2015). arXiv:1509.07876
- Brown, Gharibyan, Penington, Susskind. The Python's lunch: geometric obstructions to decoding Hawking radiation (2019). arXiv:1912.00228
- Bouland, Fefferman, Vazirani. Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality (2019). arXiv:1910.14646
- Akers, Engelhardt, Harlow, Penington, Vardhan. The black hole interior from non-isometric codes and complexity (2022). arXiv:2207.06536
- Brakerski. Black-hole radiation decoding is quantum cryptography (2022). arXiv:2211.05491
- Engelhardt, Folkestad, Levine, Verheijden, Yang. Cryptographic censorship (2024). arXiv:2402.03425
- Akers, Bouland, Chen, Kohler, Metger, Vazirani. Holographic pseudoentanglement and the complexity of the AdS/CFT dictionary (2024). arXiv:2411.04978
- Bostanci, Efron, Metger, Poremba, Qian, Yuen. Unitary complexity and the Uhlmann transformation problem (2023; v3 2025). arXiv:2306.13073
- Kretschmer. Quantum pseudorandomness and classical complexity (2021). arXiv:2103.09320
- Kretschmer, Qian, Sinha, Tal. Quantum cryptography in Algorithmica (2022). arXiv:2212.00879
- Aaronson, Kuperberg. Quantum versus classical proofs and advice (2007). The unitary synthesis problem. quant-ph/0604056
- Rosenthal. Efficient quantum state synthesis with one query (2023). arXiv:2306.01723
- Lombardi, Ma, Wright. A one-query lower bound for unitary synthesis and breaking quantum cryptography (2023). arXiv:2310.08870
- Metger, Yuen. stateQIP = statePSPACE (2023). arXiv:2301.07730