Fetching the paper…

Reading the bibliography…

Horizons Protect Church-Turing · Around

2020

Horizons Protect Church-Turing

Susskind, Leonard

Original
PDF
Post on X

Understand

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.

Built on

A. Bouland, B. Fefferman and U. Vazirani, “Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality,” arXiv:1910.14646 [quant-ph]
Original
1910
Earlier work this paper cites.
S. H. Shenker and D. Stanford, “Multiple Shocks,” JHEP 1412
Original
2003
Earlier work this paper cites.
D. Stanford and L. Susskind, “Complexity and Shock Wave Geometries,” Phys. Rev. D 90
Original
2014
Earlier work this paper cites.

Similar

S. H. Shenker and D. Stanford, “Black holes and the butterfly effect,” JHEP 1403
Original
2014
Cited alongside, same era.
L. Susskind, “The Typical-State Paradox: Diagnosing Horizons with Complexity,” Fortsch. Phys. 64
Original
2016
Cited alongside, same era.
A. R. Brown, D. A. Roberts, L. Susskind, B. Swingle and Y. Zhao, “Holographic Complexity Equals Bulk Action?,” Phys. Rev. Lett. 116
Original
2016
Cited alongside, same era.

Then

Y. Zhao, “Complexity and Boost Symmetry,” Phys. Rev. D 98
Original
2018
Later among the works it cites.
Y. Sekino and L. Susskind, “Fast Scramblers,” JHEP 0810
Original
2096
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…