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

WORLD SCIENTIFIC eBooks

Exclusively Quantum: Computations Only Possible on a Quantum Computer

Selim G. Akl

Published Aug 22, 2021• 0 citations
Publisher

Abstract

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.

DOI
10.1142/9789811235726_0004

Related papers

Church’s Thesis, Turing’s Limits, and Deutsch’s Principle

Rossella Lupacchini

In the search for a precise definition of the notion of effective calculability, Turing’s computability has proven to be more convincing than other definitions proposed almost simultaneously. Turing does not define a particular class of “calculable functions”, but which processes can be carried out in computing. His conceptual analysis brings about an intimate and inescapable link between computability and “measurability”, hence between mechanical procedures and physical processes. The full significance of this link is captured in Deutsch’s physical version of the Church-Turing thesis, namely, his claim that every physical system can be simulated by a universal quantum Turing machine. Quantum physics supports more efficient forms of computation, even though quantum computation remains within Turing’s limits. Why? This chapter explores how logical principles and physical processes coalesce into the notion of computation.

Cambridge University Press eBooks•May 17, 2018•2 citations

Quantum Speed-up of Computations

Itamar Pitowsky

Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system...Nophysically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time. An even more extreme formulation of (more or less) the same thesis is due to Aharonov (1998): A probabilistic Turing machine can simulate any reasonable physical device in polynomial cost. She calls this The Modern Church Thesis. Aharonov refers here to probabilistic Turing machines that use random numbers in addition to the usual deterministic table of steps. It seems that such machines are capable to perform certain tasks faster than fully deterministic machines. The most famous randomized algorithm of that kind concerns the decision whether a given natural number is prime. A probabilistic algorithm that decides primality in a number of

Philosophy of Science•Sep 1, 2002•36 citations

Quantum theory, the Church–Turing principle and the universal quantum computer

David Deutsch

Abstract It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizible physical system can be perfectly simulated by a universal model computing machine operating by finite means’. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the 'universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive functions, but they do include ‘quantum parallelism’, a method by which certain probabilistic tasks can be performed faster by a universal quantum computer than by any classical restriction of it. The intuitive explanation of these properties places an intolerable strain on all interpretations of quantum theory other than Everett’s. Some of the numerous connections between the quantum theory of computation and the rest of physics are explored. Quantum complexity theory allows a physically more reasonable definition of the ‘complexity’ or ‘knowledge’ in a physical system than does classical complexity theory.

Proceedings of the Royal Society of London A Mathematical and Physical Sciences•Jul 8, 1985•4,778 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

A computable formulation of quantum theory

Mike Stannett

According to the Church-Turing Thesis (CTT), effective formal behaviours can be simulated by Turing machines; this has naturally led to speculation that physical sys- tems can also be simulated computationally. But is this wider claim true, or do behaviours exist which are strictly hypercomputational? Several idealised computational models are known which suggest the possibility of hypercomputation, some Newtonian, some based on cosmology, some on quantum theory. While these models' physicality is debatable, they nonetheless throw into question the validity of extending CTT to include all physical systems. We consider the physicality of hypercomputational behaviour from first princi- ples, by showing that quantum theory can be reformulated in a way that explains why physical behaviours can be regarded as 'computing something' in the standard compu- tational state-machine sense. While this does not rule out the physicality of hypercomputation, it strongly limits the forms it can take. Our model also has physical consequences; in particular, the continuity of motion and arrow of time become theorems within the basic model.

•Jan 1, 2009•0 citations

Horizons Protect Church-Turing

Leonard Susskind

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.

arXiv:2003.01807•Mar 3, 2020•21 citations
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.
In the search for a precise definition of the notion of effective calculability, Turing’s computability has proven to be more convincing than other definitions proposed almost simultaneously. Turing does not define a particular class of “calculable functions”, but which processes can be carried out in computing. His conceptual analysis brings about an intimate and inescapable link between computability and “measurability”, hence between mechanical procedures and physical processes. The full significance of this link is captured in Deutsch’s physical version of the Church-Turing thesis, namely, his claim that every physical system can be simulated by a universal quantum Turing machine. Quantum physics supports more efficient forms of computation, even though quantum computation remains within Turing’s limits. Why? This chapter explores how logical principles and physical processes coalesce into the notion of computation.
Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system...Nophysically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time. An even more extreme formulation of (more or less) the same thesis is due to Aharonov (1998): A probabilistic Turing machine can simulate any reasonable physical device in polynomial cost. She calls this The Modern Church Thesis. Aharonov refers here to probabilistic Turing machines that use random numbers in addition to the usual deterministic table of steps. It seems that such machines are capable to perform certain tasks faster than fully deterministic machines. The most famous randomized algorithm of that kind concerns the decision whether a given natural number is prime. A probabilistic algorithm that decides primality in a number of
Abstract It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizible physical system can be perfectly simulated by a universal model computing machine operating by finite means’. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the 'universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive functions, but they do include ‘quantum parallelism’, a method by which certain probabilistic tasks can be performed faster by a universal quantum computer than by any classical restriction of it. The intuitive explanation of these properties places an intolerable strain on all interpretations of quantum theory other than Everett’s. Some of the numerous connections between the quantum theory of computation and the rest of physics are explored. Quantum complexity theory allows a physically more reasonable definition of the ‘complexity’ or ‘knowledge’ in a physical system than does classical complexity theory.
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.
According to the Church-Turing Thesis (CTT), effective formal behaviours can be simulated by Turing machines; this has naturally led to speculation that physical sys- tems can also be simulated computationally. But is this wider claim true, or do behaviours exist which are strictly hypercomputational? Several idealised computational models are known which suggest the possibility of hypercomputation, some Newtonian, some based on cosmology, some on quantum theory. While these models' physicality is debatable, they nonetheless throw into question the validity of extending CTT to include all physical systems. We consider the physicality of hypercomputational behaviour from first princi- ples, by showing that quantum theory can be reformulated in a way that explains why physical behaviours can be regarded as 'computing something' in the standard compu- tational state-machine sense. While this does not rule out the physicality of hypercomputation, it strongly limits the forms it can take. Our model also has physical consequences; in particular, the continuity of motion and arrow of time become theorems within the basic model.
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.