Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2003.01807

Horizons Protect Church-Turing

Leonard Susskind

Published Mar 3, 2020• 21 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.2003.01807

Related papers

Exclusively Quantum: Computations Only Possible on a Quantum Computer

Selim G. Akl

The property of quantum exclusivity is introduced which refers to computations that are possible to carry out only on a quantum computer, but are impossible, in principle , on a Turing machine. Exclusively quantum computations invalidate the famous conjecture known as the Church–Turing thesis, according to which any computation that can be performed on any computing device can be simulated on a Turing machine. By direct consequence, because they cannot be carried out at all , whether efficiently or inefficiently, on a Turing machine, these computations invalidate the extended Church–Turing thesis as well. These computations also demonstrate the falsity of the Principle of Universality — the assertion that there exists a Universal Computer capable of simulating any computation by any other computational device. By reviewing these results, dating mostly from the first two decades of this century, this chapter aims to establish correct historical precedence, especially in light of recent related claims of priority with respect to the violation of the Extended Church–Turing thesis by a quantum computer.

WORLD SCIENTIFIC eBooks•Aug 22, 2021•0 citations

Computable Functions, the Church-Turing Thesis and the Quantum Measurement Problem

R. Srikanth

It is possible in principle to construct quantum mechanical observables and unitary operators which, if implemented in physical systems as measurements and dynamical evolution, would contradict the Church-Turing thesis, which lies at the foundation of computer science. Elsewhere we have argued that the quantum measurement problem implies a finite, computational model of the measurement and evolution of quantum states. If correct, this approach helps to identify the key feature that can reconcile quantum mechanics with the Church-Turing thesis: finitude of the degree of fine-graining of Hilbert space. This suggests that the Church-Turing thesis constrains the physical universe and thereby highlights a surprising connection between purely logical and algorithmic considerations on the one hand and physical reality on the other.

arXiv:quant-ph/0402128•Feb 18, 2004•5 citations

Will boson-sampling ever disprove the Extended Church-Turing thesis?

Peter P. Rohde, Keith R. Motes, Paul Knott +1 more

Boson-sampling is a highly simplified, but non-universal, approach to implementing optical quantum computation. It was shown by Aaronson and Arkhipov that this protocol cannot be efficiently classically simulated unless the polynomial hierarchy collapses, which would be a shocking result in computational complexity theory. Based on this, numerous authors have made the claim that experimental boson-sampling would provide evidence against, or disprove, the Extended Church-Turing thesis -- that any physically realisable system can be efficiently simulated on a Turing machine. We argue against this claim on the basis that, under a general, physically realistic independent error model, boson-sampling does not implement a provably hard computational problem in the asymptotic limit of large systems.

arXiv:1401.2199•Jan 9, 2014•18 citations

Limits of Computation and Physical Reality

Apostolos Syropoulos

The physical laws of the universe dictate what can and what cannot be computed. The Church-Turing Thesis (CTT) is based on the assumption that the Turing machine is the ultimate computing device and according to the CTT something is computable only if it can be computed by a Turing machine. However, the CTT has not been proved and it can be definitely proved in a universe with specific properties. Whether our universe is such a universe is an open problem as it is an open problem whether the universe behaves like a machine. A broader approach that rejects the CTT and shows that the mechanistic universe and the CTT are incompatible is proposed and discussed thoroughly.

WORLD SCIENTIFIC eBooks•Feb 1, 2020•0 citations

Remarks on black hole complexity puzzle

Beni Yoshida

Abstract Recently a certain conceptual puzzle in the AdS/CFT correspondence, concerning the growth of quantum circuit complexity and the wormhole volume, has been identified by Bouland-Fefferman-Vazirani and Susskind. In this note, we propose a resolution of the puzzle and save the quantum Extended Church-Turing thesis by arguing that there is no computational shortcut in measuring the volume due to gravitational backreaction from bulk observers. A certain strengthening of the firewall puzzle from the computational complexity perspective, as well as its potential resolution, is also presented.

arXiv:2005.12491•Journal of High Energy Physics•Oct 1, 2020•7 citations

The History and the Contemporary Status of the No Cloning Theorem and the Extended Church-Turing Thesis

Spalding, Dalton

This project aims to trace the history and the evolution of two fundamental concepts that have cut across physics, mathematics and computer science over the past 100 years. First: Evolution of the so-called No-Cloning Theorem. In classical computing (Pre-Quantum), information can be copied without limitations. The discovery of the No-Cloning Theorem by Wootters and Zurek (1982) and Dieks (1982) revised this concept dramatically; they independently proved that unknown quantum states cannot be perfectly copied. I look at mathematical proofs of this theorem, construct physics-based nonmathematical plausibility arguments for it, and explore the role it plays in Quantum Key Distribution (QKD) protocols, such as BB84 (Bennett and Brassard, 1984) and the Ekert Protocol (Artur Ekert 1991). Second: Evolution of the concept of computability in quantum computing. I began by trying to understand the classical Church-Turing thesis (1936) which states that any computation performed by a physically realizable system can be simulated by a Turing machine. Then I try to explore the Extended Church-Turing Thesis (ECTT, 1980s) which conjectures that all efficiently computable functions in the physical world can be efficiently simulated by a probabilistic Turing machine. The recent discovery of quantum algorithms (for example, Shor’s algorithm, 1994) suggests that quantum computers could violate this thesis by solving problems exponentially faster than classical computers. The very modern debate (2020’s) surrounding this topic asks whether quantum computing truly invalidates ECTT or whether deeper physical constraints (such as decoherence) might limit quantum computers in a fashion that would be consistent with ECTT. This debate is far from settled. I have grappled with these hard questions and will summarize what I understand to be the status of this debate.

•Apr 12, 2025•0 citations
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.
The property of quantum exclusivity is introduced which refers to computations that are possible to carry out only on a quantum computer, but are impossible, in principle , on a Turing machine. Exclusively quantum computations invalidate the famous conjecture known as the Church–Turing thesis, according to which any computation that can be performed on any computing device can be simulated on a Turing machine. By direct consequence, because they cannot be carried out at all , whether efficiently or inefficiently, on a Turing machine, these computations invalidate the extended Church–Turing thesis as well. These computations also demonstrate the falsity of the Principle of Universality — the assertion that there exists a Universal Computer capable of simulating any computation by any other computational device. By reviewing these results, dating mostly from the first two decades of this century, this chapter aims to establish correct historical precedence, especially in light of recent related claims of priority with respect to the violation of the Extended Church–Turing thesis by a quantum computer.
It is possible in principle to construct quantum mechanical observables and unitary operators which, if implemented in physical systems as measurements and dynamical evolution, would contradict the Church-Turing thesis, which lies at the foundation of computer science. Elsewhere we have argued that the quantum measurement problem implies a finite, computational model of the measurement and evolution of quantum states. If correct, this approach helps to identify the key feature that can reconcile quantum mechanics with the Church-Turing thesis: finitude of the degree of fine-graining of Hilbert space. This suggests that the Church-Turing thesis constrains the physical universe and thereby highlights a surprising connection between purely logical and algorithmic considerations on the one hand and physical reality on the other.
Boson-sampling is a highly simplified, but non-universal, approach to implementing optical quantum computation. It was shown by Aaronson and Arkhipov that this protocol cannot be efficiently classically simulated unless the polynomial hierarchy collapses, which would be a shocking result in computational complexity theory. Based on this, numerous authors have made the claim that experimental boson-sampling would provide evidence against, or disprove, the Extended Church-Turing thesis -- that any physically realisable system can be efficiently simulated on a Turing machine. We argue against this claim on the basis that, under a general, physically realistic independent error model, boson-sampling does not implement a provably hard computational problem in the asymptotic limit of large systems.
The physical laws of the universe dictate what can and what cannot be computed. The Church-Turing Thesis (CTT) is based on the assumption that the Turing machine is the ultimate computing device and according to the CTT something is computable only if it can be computed by a Turing machine. However, the CTT has not been proved and it can be definitely proved in a universe with specific properties. Whether our universe is such a universe is an open problem as it is an open problem whether the universe behaves like a machine. A broader approach that rejects the CTT and shows that the mechanistic universe and the CTT are incompatible is proposed and discussed thoroughly.
Abstract Recently a certain conceptual puzzle in the AdS/CFT correspondence, concerning the growth of quantum circuit complexity and the wormhole volume, has been identified by Bouland-Fefferman-Vazirani and Susskind. In this note, we propose a resolution of the puzzle and save the quantum Extended Church-Turing thesis by arguing that there is no computational shortcut in measuring the volume due to gravitational backreaction from bulk observers. A certain strengthening of the firewall puzzle from the computational complexity perspective, as well as its potential resolution, is also presented.
This project aims to trace the history and the evolution of two fundamental concepts that have cut across physics, mathematics and computer science over the past 100 years. First: Evolution of the so-called No-Cloning Theorem. In classical computing (Pre-Quantum), information can be copied without limitations. The discovery of the No-Cloning Theorem by Wootters and Zurek (1982) and Dieks (1982) revised this concept dramatically; they independently proved that unknown quantum states cannot be perfectly copied. I look at mathematical proofs of this theorem, construct physics-based nonmathematical plausibility arguments for it, and explore the role it plays in Quantum Key Distribution (QKD) protocols, such as BB84 (Bennett and Brassard, 1984) and the Ekert Protocol (Artur Ekert 1991). Second: Evolution of the concept of computability in quantum computing. I began by trying to understand the classical Church-Turing thesis (1936) which states that any computation performed by a physically realizable system can be simulated by a Turing machine. Then I try to explore the Extended Church-Turing Thesis (ECTT, 1980s) which conjectures that all efficiently computable functions in the physical world can be efficiently simulated by a probabilistic Turing machine. The recent discovery of quantum algorithms (for example, Shor’s algorithm, 1994) suggests that quantum computers could violate this thesis by solving problems exponentially faster than classical computers. The very modern debate (2020’s) surrounding this topic asks whether quantum computing truly invalidates ECTT or whether deeper physical constraints (such as decoherence) might limit quantum computers in a fashion that would be consistent with ECTT. This debate is far from settled. I have grappled with these hard questions and will summarize what I understand to be the status of this debate.