Horizons Protect Church-Turing

Leonard Susskind

RECORD

Horizons Protect Church-Turing

Leonard Susskind

High Energy Physics - Theory · Submitted 3 Mar 2020

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim A viable reformulation requires that the thesis only applies to observers who have access to the holographic boundary of space.

how it is stated · hedged possibility 0.57 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,894 input tokens.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.33 · human participants 0.02 · controlled comparison 0.03 · randomized assignment 0.01 · states quantitative result 0.04 · compares with prior results 0.64 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

The quantum-Extended Church-Turing thesis is a principle of physics as well as computer science. It asserts that the laws of physics will prevent the construction of a machine that can efficiently determine the results of any calculation which cannot be done efficiently by a quantum Turing machine (or a universal quantum circuit). In this note I will argue that an observer falling into a black hole can learn the result of such a calculation in a very short time, thereby seemingly violating the thesis. A viable reformulation requires that the thesis only applies to observers who have access to the holographic boundary of space. The properties of the horizon play a crucial a role in protecting the thesis. The arguments are closely related to, and were partially motivated by a recent paper by Bouland, Fefferman, and Vazirani, and by a question raised by Aaronson.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	The quantum-Extended Church-Turing thesis is a principle of physics as well as computer science.	background 1.00	0.04	0.03	asserted 1.00
s1	It asserts that the laws of physics will prevent the construction of a machine that can efficiently determine the results of any calculation which cannot be done efficiently by a quantum Turing machine (or a universal quantum circuit).	background 1.00	0.04	0.05	asserted 0.99
s2	In this note I will argue that an observer falling into a black hole can learn the result of such a calculation in a very short time, thereby seemingly violating the thesis.	contribution 0.47	0.32	0.19	hedged possibility 0.61
s3	A viable reformulation requires that the thesis only applies to observers who have access to the holographic boundary of space.	contribution 0.46	0.54	0.67	hedged possibility 0.57
s4	The properties of the horizon play a crucial a role in protecting the thesis.	interpretation 0.64	0.40	0.31	asserted 1.00
s5	The arguments are closely related to, and were partially motivated by a recent paper by Bouland, Fefferman, and Vazirani, and by a question raised by Aaronson.	background 1.00	0.14	0.02	asserted 0.87

What kind of paper the classifier reports this is: position or commentary 1.00 · evidence from argument 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original abstract

The quantum-Extended Church-Turing thesis is a principle of physics as well as computer science. It asserts that the laws of physics will prevent the construction of a machine that can efficiently determine the results of any calculation which cannot be done efficiently by a quantum Turing machine (or a universal quantum circuit). In this note I will argue that an observer falling into a black hole can learn the result of such a calculation in a very short time, thereby seemingly violating the thesis. A viable reformulation requires that the thesis only applies to observers who have access to the holographic boundary of space. The properties of the horizon play a crucial a role in protecting the thesis. The arguments are closely related to, and were partially motivated by a recent paper by Bouland, Fefferman, and Vazirani, and by a question raised by Aaronson.

Human review

How Pith checks papers → · Full audit of this paper →

References

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Holographic Pseudo Entropy
hep-th 2020-05 conditional novelty 8.0 of 10

Pseudo entropy, defined from a reduced transition matrix between two states, is proposed to be dual to a minimal-area surface in a time-dependent Euclidean asymptotically AdS geometry, with supporting checks in qubit,...
On Quantum Simulation Of Cosmic Inflation
quant-ph 2020-09 conditional novelty 6.0 of 10

A polynomial-time quantum simulation algorithm for scalar inflationary cosmology is proposed, with lattice regularization, HKLL-type encoding, adiabatic vacuum preparation, and Trotter time evolution.
The ghost in the radiation: Robust encodings of the black hole interior
hep-th 2020-03 conditional novelty 6.0 of 10

If Hawking radiation is computationally indistinguishable from thermal noise, the black hole interior is encoded in that radiation as a quantum error-correcting code whose logical operators commute with any polynomial...
Quantum simulation of quantum field theories as quantum chemistry
hep-th 2020-04 conditional novelty 4.0 of 10

Conformal truncation of strongly-coupled quantum field theories maps onto quantum chemistry-style quantum simulation, demonstrated on a three-qubit truncation of two-dimensional QCD.

How the literature uses it

16 arXiv papers cite this in 23 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 15 sentences without a confident label

Compares with it 1 paper

This conclusion, though based on different arguments, meshes with the proposal by Bouland et al. [ref] , that the dictionary relating the black hole interior to its exterior in the context of AdS/CFT duality must be computationally complex.

The ghost in the radiation: Robust encodings of the black hole interior · Conclusion · 0.92

Cites it as support 2 papers

The complexity of doing this can be at least exponential in the complexity of the operator [ref] [ref] .

Petz map and Python's lunch · Comparison with exterior operator reconstruction · 0.98
The first is that the dictionary is extremely complex [ref] [ref] ; in fact it is exponentially complex, even for states of modest polynomial complexity[If that sounds contradictory it's not.

Black Holes at Exp-time · Three Descriptions: Which is Right? · 0.96

Cites it as background 5 papers

Recently a certain conceptual puzzle in the AdS/CFT correspondence has been identified by Bouland-Fefferman-Vazirani (BFV) [ref] and Susskind [ref] .

Remarks on Black Hole Complexity Puzzle · Introduction · 0.97
Work by Kim and Preskill [ref] brought forward concerns that the post-selection present in the dynamical holographic map proposed by [ref] might lead to superpolynomial computational complexity, violating the quantum extended Church-Turing thesis [ref] .

Bulk reconstruction and non-isometry in the backwards-forwards holographic black hole map · Action on the dynamically generated subspace · 0.80
Furthermore, recently there are some important progress about the quantum Church-Turing Thesis in curved spacetime and black holes [ref] .

Quantum simulation of quantum field theories as quantum chemistry · Quantum Church-Turing Thesis · 0.85

What it cites · 8 sentences without a confident label

Cites as support 4 papers

This of course is also the point made in [ref] : the bulk-boundary dictionary is highly complex.

Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality · Conclusion · 0.98
The work of Zhao [ref] suggests that the connection between the rate of volume growth and the existence of measurable effects behind the horizon is robust.

Complexity and Boost Symmetry · Violation of the qECT Thesis? · 1.00
An example is the attempt to mess up the interior of a two-sided black hole by repeatedly throwing in many shock waves either in or out of time order [ref] [ref] .

Black holes and the butterfly effect · Violation of the qECT Thesis? · 0.99

Cites as background 1 paper

First, item $1$: Is it possible that what I am calling complexity is not complexity but rather some much more feelable[The term “feelable" was coined by Bouland, Fefferman, and Vazirani [ref] as a shorthand for efficiently measurable or computable.

Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality · Violation of the qECT Thesis? · 0.84

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.