PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Computation vs. Firewalls

Daniel Harlow, Patrick Hayden

arXiv:1301.4504v4hep-thgr-qcquant-ph

TL;DR

The paper asks whether AMPS firewall thought experiments can be carried out within physically available times. It argues that decoding is generally exponentially hard in black-hole entropy and shows that evaporation, recurrence, confinement, or signal-return constraints prevent the experiments in broad classes of black holes.

  • Problem

    AMPS argued that unitarity and limited locality are inconsistent with a smooth horizon for an observer falling into an old black hole, but the feasibility of the required experiment remains contested.

    Source: §1 · p. 3

  • Method

    The paper analyzes the computational complexity of decoding Hawking radiation and examines physical realizations including boxed Schwarzschild black holes, AdS black holes, and near-extremal throats.

    Source: §1 · p. 4, §4.2 · p. 32, §5.1 · p. 42

  • Results

    The required decoding is argued to take exponential time in the entropy of the remaining black hole, while recurrence, evaporation, confinement, or signal-return times prevent the AMPS experiment across several black-hole settings.

    Source: §1 · pp. 4, 7, §5.1 · p. 42, §5.3 · p. 46

  • Takeaways & Limitations

    The analysis makes the feasibility of firewall experiments depend on global computational and communication constraints, including recurrence and the difficulty of returning signals through a throat.

    Source: §1 · pp. 4, 7, §5.3 · p. 46

    The claim that Hawking-radiation decoding is generally exponential is presented as a conjecture rather than a rigorous theorem, and some proposed computational shortcuts cannot be fully excluded.

    Source: §1 · p. 4, §3.4 · p. 26

Abstract

from arXiv · show

In this paper we discuss quantum computational restrictions on the types of thought experiments recently used by Almheiri, Marolf, Polchinski, and Sully to argue against the smoothness of black hole horizons. We argue that the quantum computations required to do these experiments take a time which is exponential in the entropy of the black hole under study, and we show that for a wide variety of black holes this prevents the experiments from being done. We interpret our results as motivating a broader type of non-locality than is usually considered in the context of black hole thought experiments, and claim that once this type of non-locality is allowed there may be no need for firewalls. Our results do not threaten the unitarity of of black hole evaporation or the ability of advanced civilizations to test it.

1 Introduction

The paper argues that the AMPS firewall experiment is not operationally realizable because decoding Hawking radiation generally requires exponentially long quantum computation. It proposes computational accessibility as a stronger validity criterion for effective field theory, potentially avoiding firewalls without threatening evaporation unitarity.

1 Introduction

  • The AMPS experiment requires an infalling observer to extract information from Hawking radiation through a sophisticated nonlocal measurement before entering the black hole.The paper argues that this measurement is not operationally realizable even in principle.Source: §1 · p. 3
  • For a Schwarzschild black hole, the observer must decode n ∼ M^2 bits in time T ∼ n^3/2, whereas generic unitary transformations on an n-bit Hilbert space require exponential time.The relevant decoding operation is argued to be unlikely to have the special structure needed for faster implementation.Source: §1 · pp. 3–4
  • For more general black holes, exponential decoding times can prevent the AMPS experiment through recurrence phenomena, fragmentation, or other physical constraints before computation is completed.The paper specifically discusses Reissner–Nordstrom and large AdS black holes, where recurrence or fragmentation limits the available computation time.Source: §1 · pp. 4, 6, 7
  • The paper proposes that spacelike-separated low-energy observables inaccessible to one observer’s available time or memory need not correspond to distinct commuting operators on one Hilbert space.This computational criterion is stronger than the corresponding causal criterion and can apply even when both observables lie within an observer’s past lightcone.Source: §1 · pp. 4–5
  • The computational proposal is intended to avoid firewall paradoxes while preserving black-hole evaporation unitarity for an asymptotic observer with sufficient time and memory.The new EFT restrictions apply to an infalling observer such as Alice, not necessarily to Charlie at infinity.Source: §1 · pp. 5–6
  • The paper distinguishes its computational argument from earlier proposals involving strong or standard complementarity and from noncomputational arguments about the impossibility of the experiment.It presents the computational-complexity analysis as stronger than one earlier argument and potentially sufficient to avoid cloning and acausality paradoxes.Source: §1 · p. 6
  • In a long-throat geometry, redshift may accelerate decoding relative to evaporation, but sending the result back to the black hole can take longer than its recurrence time.The authors present this as a robust conspiracy preventing the AMPS experiment across a wide variety of probes.Source: §1 · p. 7
  • The authors acknowledge that external manipulation of a quantum-gravity simulation could pause evolution and decode radiation, but argue this does not address the intended question about isolated nonsingular evolution.In the throat setup, physical restrictions still prevent observers from overcoming decoding complexity.Source: §1 · pp. 7–8

2 The Firewall Argument

The AMPS argument combines unitary evaporation, semiclassical factorizations, and shared observer-accessible physics to infer that an old black hole cannot have both the expected exterior entanglement and a smooth horizon. The proposed escape is that Alice cannot perform the required nonlocal measurement of the radiation quickly enough, motivating modified observer-dependent quantum mechanics or broader nonlocality.

2.1 A Quantum Black Hole from the Outside

  • The AMPS setup assumes unitary evaporation, semiclassical subfactorizations of the exterior Hilbert space, and horizon-scale modes whose dimensions track the black-hole area.The radiation factor grows while the black-hole and near-horizon factors shrink as evaporation proceeds.Source: §2.1 · p. 9
  • After the Page time, the near-horizon system BH is close to maximally mixed and therefore maximally entangled with a subspace of the Hawking radiation.This follows from the radiation becoming larger than the combined black-hole and near-horizon subsystem.Source: §2.1 · pp. 9–10

2.2 A Quantum Black Hole from the Inside

  • Alice’s description shares B and R with Charlie while adding interior modes A, so the overlap rule requires both observers to agree on experiments involving those shared factors.Alice’s horizon factor differs from Charlie’s black-hole horizon factor, and the intermediate region has no operational meaning for her.Source: §2.2 · p. 11
  • Because B must be entangled with both the early radiation partner RB and interior modes A, entanglement monogamy and strong subadditivity produce the AMPS contradiction.The mutual information IAB = 0 implies that A and B factorize, inconsistent with the highly entangled state required for a smooth horizon; one interpretation is a firewall.Source: §2.2 · pp. 11–13

2.3 A Way Out?

  • The crucial measurement of RB requires carefully engineered nonlocal superpositions of many Hawking quanta, and Alice may not have time to perform it before entering the black hole.Charlie has unlimited time outside, whereas Alice must complete the measurement before evaporation or before her fall prevents access.Source: §2.3 · p. 13
  • Limiting Alice’s access to RB could permit B to remain entangled with A, through strong complementarity or an embedded “A = RB” construction, without requiring a firewall.The paper presents these as modifications of Alice’s quantum mechanics whose credibility is restored by computational restrictions.Source: §2.3 · pp. 13–14

3 The AMPS Experiment as a Quantum Computation

This section formulates the AMPS decoding task as a quantum-computation problem and examines the constraints on its feasibility. It argues that limited access to the black hole’s qubits leaves generic decoding exponentially costly, with only a vanishingly small fraction of initial states efficiently decodable.

3 The AMPS Experiment as a Quantum Computation

  • Alice must implement U_R† on the Hawking radiation to expose the entanglement with H_B, making the AMPS experiment a quantum-computation problem.The relevant unitary is defined only on a restricted subspace, and its action outside that subspace may be chosen to simplify computation.Source: §3 · p. 15

3.1 Quantum Computing is Hard

  • Without special structure in the computer–radiation dynamics, Alice’s success probability is extraordinarily small, and waiting for a favorable recurrence can require about 10^101040 years for an astrophysical black hole.Varying computer size does not help, while exploiting structured time or size dependence can reduce the double-exponential bound to a single exponential in radiation entropy.Source: §3.1 · p. 18

3.2 Implementing a General Unitary Transformation with Quantum Gates

  • The quantum circuit model implements generic n-qubit unitaries in single-exponential time, while the restricted action defining U_R suggests a decoding cost scaling like 2^(k+m+n).Local gates and the Solovay–Kitaev theorem achieve the single-exponential bound; generic transformations require scaling like 2^(2n), and locality-based modifications do not change that main scaling.Source: §3.2 · pp. 22–23

3.3 Why is Alice’s Computation Slower than the Black Hole Dynamics?

  • Although a Schwarzschild black hole produces the relevant state in time scaling as n^(3/2), this does not imply that Alice can implement U_R† comparably quickly.The analysis introduces an adiabatic evaporation model and assumes the full dynamics U_dyn can be generated by a polynomial-sized circuit, asking whether that implies a small circuit for U_R.Source: §3.3 · pp. 23–24
  • Because Alice lacks access to the black hole and interior qubits, she cannot time-reverse the dynamics to extract R_B polynomially and generally requires about 2^(n+k+m) gates.Small circuits can move the radiation’s quantum information to a stable memory, but testing its entanglement still requires undoing U_R; the construction also assumes a relatively simple microscopic-to-macroscopic mapping for low-energy exterior fields.Source: §3.3 · pp. 24–26

3.4 Two Counting Arguments

  • Even direct time reversal would require roughly the evaporation time and may take longer for an old black hole, so runtime alone is not treated as a sufficient firewall argument.The authors note that general polynomial algorithms can sometimes be accelerated through problem-specific tricks or parallelization.Source: §3.4 · p. 26
  • For generic initial states, the vast majority require generic U_R operators that take time of order 2^(n+k+m) to implement, so only a vanishingly small fraction are polynomial-time decodable.The number of possible initial states is comparable to the number of elements in the relevant unitary coset, forcing most states to correspond to hard decodings.Source: §3.4 · pp. 26–27
  • Even if one seeks a basis whose elements are easy to decode, coarse-graining makes the resulting U_R operators a doubly-exponentially small fraction of the relevant coset.Writing n+k+m = S_initial/log 2 + Δn with Δn > 0, the initial-state set is double exponential in n+k+m−Δn; even Δn = 1 makes polynomial-size decoding doubly exponentially unlikely under random independent U_R choices.Source: §3.4 · p. 27

4 Quantum Coding and Error Correction

This section recasts Alice’s black-hole decoding task as quantum error correction, examining how radiation loss can be tolerated while decoding may remain computationally difficult. It considers general and stabilizer codes, computational complexity connections, and the conditions under which efficient correction is possible.

4.1 Review of Error Correcting Codes

  • Quantum error correction protects information by redundantly and nonlocally encoding k logical qubits in an n-qubit code subspace; Shor’s nine-qubit code corrects any single-Pauli error.The procedure identifies errors through check-operator measurements and applies a corresponding correction.Source: §4.1 · pp. 28–29
  • For general encoding transformations, conjugating simple physical errors can produce a larger and less useful error set, so the standard check-operator procedure need not yield an efficient correction algorithm.This limitation arises because the encoding may be simple in the logical basis but unnatural in the computational basis.Source: §4.1 · pp. 31–32

4.2 Computational Complexity, Stabilizer Codes, and NP-Hardness

  • General error correction may require exponential time because selecting a correction among 2^n+k errors consistent with a syndrome is computationally impractical.The encoding transformation can be easy to implement, while choosing the most likely correction remains hard.Source: §4.2 · p. 32
  • For stabilizer codes in an erasure channel, correction is polynomial-time when 2l < n − k, using Gaussian elimination on the syndrome equation.When this inequality is violated, correction is impossible for the channel; for typical stabilizer codes, it also characterizes correctability.Source: §4.2 · p. 33
  • Stabilizer decoding for a more general channel is NP-complete in a related construction, indicating exponential-time correction even when the noise and encoding circuits have polynomial size.The stated proof requires k to grow with n, while the authors expect hardness also at fixed k and large n.Source: §4.2 · p. 34

4.3 Alice’s Task as Error Correction

  • Alice’s task can be recast as decoding a quantum code [3], but the simplest formulation is uninformative because its state can be decoded by applying U†R, whose complexity is unspecified.Introducing an auxiliary system B′ makes the code space k-dimensional and ties recovery to unscrambling the entanglement between B′ and R.Source: §4.3 · pp. 35–36
  • For Alice’s code, correcting erasures of B and H generally requires a circuit of size 2^2l, where l is the number of erased qubits.The encoding map need not define a stabilizer code, so the efficient erasure correction available for stabilizer codes does not generally apply.Source: §4.3 · p. 36
  • The correction procedure can be faster than the gate-count estimate because it operates on fictitious B′, but generic channel correction does not yield a comparable circuit for U_R.Thus, channel correction is no easier to convert into an implementation of U_R than the reverse direction.Source: §4.3 · p. 36
  • Alice can lose all gravitons and still recover the entanglement accurately, although correcting these practical errors adds computational difficulty.Without computational-complexity constraints, graviton detection alone does not prevent the AMPS experiment.Source: §4.3 · p. 37

4.4 Error Correction and Zero-Knowledge Proofs

  • Error Correctability is QSZK-complete, with a zero-knowledge proof in which an unbounded prover performs correction while a polynomial-time verifier checks maximal entanglement.The problem asks whether maximal entanglement with B can be decoded from R for a state generated by a polynomial-sized U_dyn.Source: §4.4 · pp. 38–39
  • Efficiently finding correction procedures for every correctable U_dyn would imply QSZK = BQP, although deciding correctability may be easier than performing correction.This implication applies even though the verifier’s task and the actual decoding task have different computational requirements.Source: §4.4 · p. 39
  • Error Correctability remains QSZK-complete when B is a single qubit, unlike the earlier stabilizer-decoding NP-hardness argument that fails for order-one k.This addresses concerns that the NP-complete Coset Weights route or its decoding strategy might not apply in the relevant regime.Source: §4.4 · pp. 37, 39
  • Under the assumption that non-Abelian hidden-subgroup problems lack efficient quantum algorithms, the MRV construction yields efficiently encoded codes whose decoding unitary cannot be implemented in polynomial time.The construction reproduces the relevant black-hole-like recovery properties while making inversion, and therefore decoding, hard.Source: §4.4 · p. 40
  • Quantum computers require exponentially many queries for the 1-to-1 versus 2-to-1 problem despite its zero-knowledge protocol, constraining arguments that QSZK has small circuits.Any efficient-circuit demonstration would need to exploit special internal structure rather than directly transform the protocol into a circuit.Source: §4.4 · pp. 40–41
  • The section concludes that Alice’s task is likely at least QSZK-hard and that implementing U_R† would very surprisingly not require exponential time.The authors do not prove NP-hardness at fixed k, but practical errors such as graviton loss further increase the decoding challenge.Source: §4.4 · p. 41

5 More General Black Holes

This section examines whether more general black-hole geometries can remain available for Alice’s exponentially hard decoding experiment, focusing on how boxes, charge, near-extremal throats, evaporation, and signal times affect the necessary timing constraints. It finds that the strong AMPS experiment is ruled out in this setup, while the weak version remains uncertain but seriously doubtful.

5 More General Black Holes

  • Schwarzschild black holes evaporate in entropy^(3/2) time, far too quickly for Alice’s exponentially long computation.The section therefore considers boxes, charge, and more general throat geometries as ways to slow evaporation.Source: §5 · p. 41

5.1 Schwarzschild in a Box

  • A reflecting box cannot safely preserve a Schwarzschild black hole for the required time because recurrences can produce destructive objects, while enlarging the box permits evaporation.AdS avoids ordinary evaporation, but Alice and her equipment must also survive recurrence-scale hazards; a throat geometry is proposed to combine Minkowski and AdS advantages.Source: §5.1 · pp. 42–43

5.2 Reissner-Nordstrom

  • Charged Reissner-Nordstrom black holes are no use to Alice: quantum-gravity instability occurs before exp(S0), and total evaporation time remains polynomial in S0.For E0 ≤ Q, the initial entropy is order Q^2 and instability occurs after order Q^7; for E0 ≫ Q, the Schwarzschild regime is recovered.Source: §5.2 · p. 44

5.3 Near Extremal AdS Throat

  • A near-extremal AdS throat can independently tune decay time through its crossover radius and outsource computation to the Minkowski region for a large redshift enhancement.However, sending the result back requires exponentially low-energy signals with exponentially small absorption probability, so feasibility requires further analysis.Source: §5.3 · pp. 45–46

5.3.1 The Brane Setup

  • A planar D3-brane construction realizes a throat that is AdS5 × S5 near the branes and ten-dimensional Minkowski space far away.Finite temperature and compact spatial directions produce a finite-entropy black hole; antiperiodic fermion boundary conditions stabilize the throat by breaking supersymmetry.Source: §5.3.1 · pp. 46–47

5.3.2 Hawking-Page Transition for Toroidal Black Holes

  • The toroidal black brane eventually transitions to an AdS soliton as it cools, leaving no horizon and preventing Alice from testing AMPS.The black brane dominates at temperatures above L^-1, while the soliton dominates below L^-1; the microcanonical instability occurs somewhat lower.Source: §5.3.2 · pp. 48–50

5.3.3 Time Scales

  • To keep entropy fixed while making the temperature exponentially small, the throat length must become exponentially large, while the AdS radius remains bounded polynomially in S0.Messages require exponentially low energy and therefore exponentially small absorption probability; the time-scale analysis compares signaling and decay with exponentially large computation and recurrence times.Source: §5.3.3 · pp. 50–51
  • The evaporation time is always the same order in temperature as the time to send any signal, although prefactors can allow tmsg < tevap.This comparison alone does not rule out the experiment.Source: §5.3.3 · p. 53
  • All three requirements—computation, signaling, and recurrence timing—can be satisfied only when the black-hole temperature is exponentially small in the entropy.The computation time is taken to scale as e2S0, with Alice starting just after the Page time.Source: §5.3.3 · pp. 53–54
  • For the general computation model α = 2, the experiment requires b < 1, but scalar fields obey b = 2∆ and the unitarity bound ∆> 1 precludes this condition.The string and free scalar cases are therefore not close to satisfying the required inequality.Source: §5.3.3 · p. 54
  • Even if improved algorithms reduced α below 3/2, this would only make string communication possible in principle and would not suffice for the full AMPS experiment.Sending the purifying quantum state requires preserving coherence, transmitting apparatus, and repeatedly overcoming reflection and error-correction failures.Source: §5.3.3 · pp. 54–55
  • The strong AMPS experiment, in which Alice carries the black-hole purification, cannot be performed in this setup because repeated partial reflection eventually causes error-correction failure.Slightly more than half of the purification can be transmitted at each attempt, but maintaining the correct state through repeated attempts eventually fails.Source: §5.3.3 · p. 55
  • The weak AMPS experiment remains unresolved for α < 2, but backreaction prevents exponentially many signal copies from overcoming the exponential message time, casting serious doubt on its feasibility.Classical records are easier to transmit than the purification, yet strings would become exponentially dense and available scalar modes provide no exponential improvement.Source: §5.3.3 · p. 55

6 The Structure of the Hilbert Space

The paper considers how computational inaccessibility of Hawking-radiation information supports a single-Hilbert-space description of black-hole interiors without firewalls. It develops an A = R_B interpretation in which interior operators become state-dependent and highly nonlocal after the Page time.

Conceptual status

  • Strong complementarity remains conceptually unsatisfying because its observer-dependent descriptions lack a precise relationship, motivating an embedding in AdS/CFT.The paper presents its single-Hilbert-space proposal as a way to understand such ambiguities as arising from observables that are not precisely well-defined.Source: §6 · pp. 56–57

State dependence

  • The bulk-operator construction becomes sensitive to the entire boundary history and quantum state as the operator approaches the horizon.The operator is obtained by integrating a CFT operator over the lightcone boundary with a position-dependent kernel.Source: Figure 6 · p. 57

A single Hilbert space

  • The proposal uses a single CFT Hilbert space with mutually commuting operator sets C_n for Charlie and A_n for Alice, matched where their descriptions must agree.The construction aims to embed strong complementarity into a sharp framework rather than assigning each observer an unrelated quantum mechanics.Source: §6 · pp. 56–57

A = R_B

  • After the Page time, the relevant interior operators A_n act from Charlie’s perspective on the complicated radiation subfactor R_B that purifies the near-horizon modes B.Before the Page time, Charlie can instead interpret these operators as complicated operators on the remaining black hole.Source: §6 · p. 58

Strong complementarity

  • Computational inability to decode R_B avoids the apparent cloning problem by allowing interior and radiation descriptions to remain perspective-dependent within one quantum theory.Low-energy manipulations of the radiation would otherwise make a distant radiation observable indistinguishable from a behind-the-horizon observable, enabling acausal communication.Source: §6 · p. 58

A The Absorption Probability for a Nambu-Goto String

This appendix computes the low-energy absorption probability for transverse oscillations of a string in an extremal black three-brane geometry. It uses matched approximate solutions across overlapping radial regions and obtains a result consistent with earlier work.

Setup

  • The calculation concerns low-energy absorption by transverse oscillations of a Nambu-Goto string stretching down an extremal black three-brane geometry.The method follows the massless-scalar analysis of Klebanov and agrees with Maldacena and Callan.Source: A The Absorption Probability for a… · p. 59
  • The string is parametrized in static gauge, restricted to S5 oscillations, and analyzed using modes of definite frequency ω.The resulting equation of motion is then solved in appropriate radial regimes.Source: A The Absorption Probability for a… · pp. 59–60

Matched asymptotics

  • For ωR ≪ 1, an intermediate approximate solution is matched to the inner and outer solutions across overlapping regions.The matching fixes the coefficients needed to impose the absorption condition.Source: A The Absorption Probability for a… · p. 60

Result

  • The absorption probability is obtained from the squared ratio of wave coefficients and is consistent with.The calculation switches back from the dimensionless radial variable to r before evaluating the coefficient ratio.Source: A The Absorption Probability for a… · p. 61
Loading 1301.4504v4…