Decoding Complexity and Harlow–Hayden Obstructions

Information-theoretic recovery and physically completed decoding are different claims. A Hayden–Preskill channel may guarantee that a diary is encoded in the early and late radiation, yet the circuit that extracts it can require more elementary operations than an observer can perform before the black hole evaporates. Harlow and Hayden turn this gap into a proposed obstruction to a firewall-distillation experiment. The obstruction is conditional on an access model, a circuit model, and complexity assumptions; finite numerical growth is not a proof of a universal exponential lower bound.

Required background. Quantum Information supplies recovery channels, circuit size, and error norms; Gauge Theory and String-Theory Preparation supplies the holographic and large-system setting in which the decoding problem is posed.

Helpful background. Semiclassical Gravity supplies the evaporation clock and energy budget; Quantum Fields in Curved Spacetime supplies the radiation modes available to an exterior collector; and Black-Hole Information supplies the recovery and interior-consistency questions.

The decoding task and its physical deadline

Let $R$ denote collected Hawking radiation and let $B$ denote the remaining hole. After a specified scrambling unitary, information-theoretic recovery means that a channel $\mathcal D_R$ exists with error

$$\sup_{\rho_{MN}} \left\lVert (\mathcal D_R\otimes I_N)(\rho_{RN})-\rho_{MN} \right\rVert_1\le\varepsilon,$$

where $M$ is the message and $N$ its reference. Feasible recovery adds a resource inequality,

$$D_{\rm dec}\,t_{\rm gate}+t_{\rm collect}+t_{\rm verify} \lt t_{\rm available},$$

plus bounds on memory, precision, energy, and backreaction. The right-hand side may be an evaporation time, an infaller’s causal deadline, or another named clock. It cannot be chosen after seeing the algorithm.

Harlow and Hayden formulate the radiation-distillation task and its relation to computational hardness in Harlow and Hayden 2013, §§ 2–4. Their argument distinguishes a map that exists by decoupling from a decoder that can be synthesized efficiently. The strong conclusion depends on complexity-theoretic conjectures and on how the evaporation dynamics is represented as a circuit.

A finite counting benchmark

The retained calculation compares two deliberately simple decoder classes. For a $k$-bit basis-state message, a completely unstructured reversible decoder could be any permutation of $m=2^k$ basis labels, giving $m!$ candidates and as many worst-case blind trials up to an order-one factor. A decoder known to be an invertible linear map over $\mathbb F_2$ can instead be inverted by Gaussian elimination using at most an order-$k^3$ arithmetic count. We use $k^3$ as a scaling proxy, not an exact count of an implemented elimination routine. Blind trials also require a verification oracle and do not have the same cost as individual arithmetic operations. This is a classical slice of a quantum problem, useful only for verifying how structural promises change a search space.

The exact logarithmic candidate count is

$$L_k=\log_2\!\left[(2^k)!\right].$$

Stirling’s approximation provides an independent benchmark,

$$L_k^{\rm St} =\frac{m\log m-m+\tfrac12\log(2\pi m)}{\log2}, \qquad m=2^k.$$

Message qubits $k$	Basis dimension $m$	Blind candidate count $\log_2(m!)$	Elimination scaling proxy $\log_2(k^3)$	Relative Stirling error
1	2	1.00000000	0.00000000	5.9642e-2
2	4	4.58496250	3.00000000	6.5420e-3
3	8	15.29920802	4.75488750	9.8177e-4
4	16	44.25014047	6.00000000	1.6979e-4
5	32	117.66326365	6.96578428	3.1929e-5

The decreasing independent approximation error checks the exact factorial calculation under five size refinements. Direct enumeration is performed only for $k\le3$, where it is cheap, and is checked against $m!$. The table does not measure a quantum decoder runtime and cannot establish asymptotic hardness.

Reproducible reference calculation

The reference environment is CPython 3.11.9 using only the standard library; no third-party package is needed. No random seed or floating solver is needed. Save the program as hh_decoder_counts.py. The program emits every resource row, checks exact enumeration for the three smallest cases, compares lgamma with an independent logarithmic sum to a tolerance of $10^{-12}$ at all five sizes, verifies decreasing Stirling error, and exits nonzero if a benchmark fails.

import itertools
import math


def enumerated_permutations(dimension):
    return sum(1 for _ in itertools.permutations(range(dimension)))


def row(message_qubits):
    dimension = 2 ** message_qubits
    exact = math.lgamma(dimension + 1) / math.log(2.0)
    stirling = (dimension * math.log(dimension) - dimension
                + 0.5 * math.log(2.0 * math.pi * dimension)) / math.log(2.0)
    relative_error = abs(stirling - exact) / exact
    structured_log = math.log2(message_qubits ** 3)
    return message_qubits, dimension, exact, structured_log, relative_error


def main():
    rows = [row(k) for k in range(1, 6)]
    for k in range(1, 4):
        dimension = 2 ** k
        assert enumerated_permutations(dimension) == math.factorial(dimension)
    for k, dimension, exact, _, _ in rows:
        reference = sum(math.log2(j) for j in range(1, dimension + 1))
        assert abs(exact - reference) < 1.0e-12
    errors = [entry[-1] for entry in rows]
    assert all(later < earlier for earlier, later in zip(errors, errors[1:]))
    for entry in rows:
        print(entry[0], entry[1], f"{entry[2]:.8f}",
              f"{entry[3]:.8f}", f"{entry[4]:.4e}")


if __name__ == "__main__":
    main()

Run it from the directory in which it was saved:

python3.11 -m venv .venv-hh
. .venv-hh/bin/activate
python hh_decoder_counts.py

What the benchmark says—and does not say

The factorial-versus-structured comparison makes one defensible point: a promise about decoder structure can change an impossible blind search into a polynomial algorithm. A physical claim must therefore state whether the observer knows the microscopic unitary, has oracle access to it, can collect coherent radiation, and may use a structured inverse. Harlow’s complexity review develops the relevant distinctions in Harlow 2016, Appendix E, while the original recovery theorem’s scrambling and efficiency qualifications appear in Hayden and Preskill 2007, §§ 4–5.

Several failure modes matter. Exact enumeration becomes infeasible long before a macroscopic entropy is reached. Finite-size trends do not prove a worst-case or average-case lower bound. Noise and incomplete access can make the target channel unrecoverable rather than merely hard. An algorithm with acceptable gate count may still demand exponentially precise control, enormous coherent memory, or energy that backreacts on the geometry. Conversely, a special microscopic code may admit a structured decoder that defeats blind-search intuition.

The Harlow–Hayden proposal can protect a causal experiment only if its decoding lower bound survives the physically relevant distribution of black-hole dynamics and if every alternative protocol respects the same access and error criteria. Generic complexity theory, stable thermodynamics, and explicit string constructions remain outside this comparison.

Exercises

For $k=5$, compare the two logarithmic operation counts in the table and convert each back to a count. Explain why their finite contrast is neither a proof of exponential quantum decoding hardness nor evidence that the structured algorithm applies to Hawking radiation.

Solution

The blind count has logarithm $117.66$, so it is about $2^{117.66}=32!$ candidate trials; the structured count has logarithm $6.97$, so it is $2^{6.97}=125$ for the $k^3$ scaling proxy. The second number is not a measured runtime or an exact elimination count, and one candidate trial may require many operations to verify. Their contrast illustrates the value of a structural promise, but it samples only basis permutations and assumes a known linear decoder. A quantum radiation channel acts on amplitudes, may be noisy, and need not have that promise. Establishing hardness requires a reduction or lower bound in the declared circuit and input distribution, followed by a physical time, energy, and backreaction analysis.

References

• 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.