When an old black hole emits one more qubit of Hawking radiation, the information needed to recover that qubit’s entangled partner is, in principle, already sitting in the earlier radiation. Whether anyone could actually extract it in time has been a central question since the firewall debate. A new preprint by Ezekiel Cochran and Atul Mantri (Virginia Tech) gives a sharp answer in an idealised model: if the black hole’s dynamics is a Haar-random unitary that the decoder can query, recovering even a single qubit with any constant advantage over guessing requires a number of queries proportional to the Hilbert-space dimension of what remains of the black hole, and that count is tight.
This article was drafted with Claude and fact-checked against the cited primary sources.
Why this paper is worth reading
The “computation versus firewalls” line of work, starting with Harlow and Hayden (2013), argued that the decoding task behind the firewall paradox of Almheiri, Marolf, Polchinski and Sully is likely too hard to finish before the black hole evaporates. Those arguments rest on complexity assumptions and give worst-case hardness. This paper instead proves an unconditional query lower bound in an explicit oracle model, matches it with an existing algorithm, and then turns the same hardness into cryptography: an EFI pair and quantum commitments built from a public Haar-random oracle.
What the paper does
The setup follows the Hayden–Preskill picture. A reference qubit B is maximally entangled with one of n input qubits; the other n−1 inputs start in |0⟩. A Haar-random unitary U acts on all n qubits, and the output is split into radiation R and the remaining black hole H. The decoder receives R (never B or H) and must output a qubit A that is entangled with B. It may query U, with arbitrary computation between queries.
Success is measured by the Haar-averaged squared Bell-state fidelity between B and A. Outputting a qubit that ignores R scores exactly 1/4, so the question is what it costs to beat 1/4 by any fixed margin δ.
The main results, stated for |R| ≥ |H| and for decoders whose circuit and initial auxiliary state are chosen independently of the sampled U, are:
Forward-only access: Ω(2|H|) queries are required.
All four query types (U, U†, U*, UT, including controlled versions and a coherent choice among them): Ω(min{2|H|, 2n/16}) queries are required. The two bounds coincide when |H| ≤ n/16.
The same bounds hold for a fixed decoder that succeeds only on a constant fraction of Haar oracles.
Matching upper bound: for |R| ≥ |H| + 1, specialising the Uhlmann-transformation algorithm of Utsumi, Nakata, Wang and Takagi gives a decoder using O(2|H|) forward and inverse queries at fixed error, with Haar-averaged fidelity at least 1 − 2·2(|H|−|R|)/2 − ε.
So in the regime where the black hole retains at most one sixteenth of the qubits, the query complexity of radiation decoding is pinned down: Θ(2|H|), for any fixed target fidelity between 1/4 and 1.
The key idea
Rather than analysing decoders directly, the authors study an easier distinguishing task. A distinguisher receives the joint state on BR and query access to U, and must tell whether that state came from the real experiment or is simply maximally mixed. Any good decoder yields a good distinguisher: run the decoder and test BA for the Bell state. In the real experiment this accepts with the decoder’s fidelity; in the mixed experiment it accepts with probability exactly 1/4. A decoding advantage of f − 1/4 therefore becomes a distinguishing advantage of (f − 1/4)/2 with the same queries.
The intuition for hardness is that the real BR state has low rank (it is purified by the hidden register H, so its rank is at most 2|H|), yet the only handle a decoder has on the hidden part H is through queries to a random unitary that reveal almost nothing about it per call.
How the proof works
The technical engine is the path-recording oracle of Ma and Huang, extended to all four query types by Schuster et al. It replaces Haar queries with explicit maps that write a “record” of queried input–output pairs into hidden registers, with a provable approximation error. For forward-only queries that error is O(q2/2n); for all four types it is O(q2/2n/8). The second figure is where the 2n/16 cutoff in the main theorem comes from.
In the recording picture, the real and mixed experiments differ only in where one input–output pair, the “challenge pair” produced when U prepared the radiation, is stored: inside the oracle’s record (real) or in a separate untouched register (mixed). The authors introduce an insertion map J, following the merge-map method of Ananth et al., that moves the challenge pair into the record and exactly maps the mixed initial state onto the real one. Two error sources then have to be controlled:
J is not an isometry. After insertion the record “forgets” which pair was the challenge, which can create interference between query histories. Because the algorithm never touches H, its weights cannot correlate with the hidden label, and the resulting error is bounded by counting at most q recorded pairs.
J does not commute with queries. Inserting the challenge first can block or enable a coordinate that a creation or deletion step would otherwise use. The authors bound the commutator of J with each primitive creation and deletion map and sum the errors over the q queries in a hybrid argument.
Both errors scale with q/2|H|, which gives the Ω(2|H|) lower bound once the Haar-approximation errors are added back.
Why it matters
The paper gives three applications from the same comparison:
EFI from a public Haar oracle. With |H| = λ, |R| = 2λ and n = 3λ, the real BR state and the maximally mixed state are efficiently preparable, have trace distance at least 1 − 2−λ−1, and yet any algorithm with oracle-independent circuit and advice making polynomially many queries has expected absolute distinguishing gap O((q+1)2·2−λ/16).
Quantum commitments. Via the construction of Brakerski, Canetti and Qian, the EFI pair gives a computationally hiding, statistically binding bit commitment with perfect correctness. The Haar encoding also gives a direct one-qubit commitment: send R, later reveal H. The authors prove computational hiding and statistical swap binding (advantage at most 2·2−λ/2), using one forward query to commit and one inverse query to verify.
A tight Uhlmann lower bound. On a fixed-target family with |R| = 15|H|, any Uhlmann transformation achieving squared-fidelity error up to 1/8 needs Ω(r) preparation queries, where r = 21+|H| is the relevant rank, matching the known O(r) upper bound, even with all four query types.
Technical perspective (interpretation)
My reading is that the most useful contribution is less the black-hole framing than the clean, quantitative hardness of distinguishing low-rank radiation from noise under the strongest natural access model. The Kim–Tang–Preskill hypothesis that low-rank radiation is computationally indistinguishable from maximally mixed has been used as a working assumption; the paper describes its bounds as a quantitative analogue of that hypothesis in the Haar-random oracle model. Including U* and UT access matters: the efficient Yoshida–Kitaev decoder uses conjugate access (when it also holds a partner of the initial black hole), and conjugate queries are known to give exponential advantages in other tasks. Showing they do not help here is a substantive point.
It is also notable that the cryptography needs no secret key. The commitment uses only the public oracle and quantum communication, which speaks to a question raised by Schuster et al. about whether natural, publicly known scrambling dynamics can carry cryptographic properties.
Limitations and open questions
It is an oracle result. The bounds are about query access to an ideal Haar-random unitary, not about real black-hole dynamics or efficiently implementable scramblers. The authors themselves note that complexity-based hardness is a worst-case statement rather than a statement about every physical black hole.
Oracle-independent decoders. The lower bound assumes the decoder’s circuit and auxiliary state are chosen independently of the sampled U. Decoders with U-dependent advice are outside its scope.
Regime. The results assume |R| ≥ |H|, and the all-four-query bound is tight only for |H| ≤ n/16; beyond that the 2n/16 cutoff is an artefact of the Haar approximation used in the proof.
Queries, not gates. The bounds count oracle queries and allow unbounded computation in between, so they say nothing additional about gate complexity.
Cryptography is relative to the oracle. Security is stated as an expected gap over a public Haar oracle against oracle-independent algorithms. Instantiating it with a concrete family of unitaries would need further assumptions.
Preprint status. This is a 67-page v1 preprint that has not yet been peer reviewed. The authors include an AI disclosure: they state that Claude and ChatGPT models helped draft and edit proofs, that they replaced the AI-generated drafts with simpler proofs of their own, and that they checked all proofs and take full responsibility.
Paper information
Title: Black Hole Radiation Decoding in the Haar Random Oracle Model
Authors: Ezekiel Cochran, Atul Mantri (Department of Computer Science, Virginia Tech)
arXiv: 2610.07124v1 [quant-ph], also cs.CC and cs.CR; submitted 5 October 2026; 67 pages, 4 figures
Code/data: none (theory paper)
Primary sources
arXiv abstract page: arxiv.org/abs/2610.07124
Full text (HTML): arxiv.org/html/2610.07124v1