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:1702.00923

An All-Or-Nothing Flavor to the Church-Turing Hypothesis

Stefan Wolf

Published Feb 3, 2017• 0 citations
arXivHTMLPDF

Abstract

Landauer's principle claims that "Information is Physical." It is not surprising that its conceptual antithesis, Wheeler's "It from Bit," has been more popular among computer scientists --- in the form of the Church-Turing hypothesis: All natural processes can be computed by a universal Turing machine; physical laws then become descriptions of subsets of observable, as opposed to merely possible, computations. Switching back and forth between the two traditional styles of thought, motivated by quantum-physical Bell correlations and the doubts they raise about fundamental space-time causality, we look for an intrinsic, physical randomness notion and find one around the second law of thermodynamics. Bell correlations combined with complexity as randomness tell us that beyond-Turing computations are either physically impossible, or they can be carried out by "devices" as simple as individual photons.

DOI
10.48550/arxiv.1702.00923

Related papers

Quantum Computation and the Church–Turing Hypothesis

Christopher G. Timpson

Some of the philosophical questions raised by the theory of quantum computation are discussed. First it is considered whether the possibility of exponential speed-up in quantum computation provides an argument for a more substantive notion of quantum information than so far allowed. It is concluded that this is not so. Then some questions regarding the status of the Church-Turing hypothesis in the light of quantum computation are considered. In particular, Deutsch’s claim that a physical principle, the Turing Principle, underlies the Church-Turing hypothesis is rebutted. Finally, the question of whether the Church-Turing hypothesis might serve as a constraint on the laws of physics is briefly considered.

Oxford University Press eBooks•Apr 25, 2013•0 citations

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

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

Quantum computing and quantum complexity theory

Umesh V. Vazirani

There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].

IEEE International Symposium on Circuits and Systems proceedings•Jan 1, 2000•0 citations

Quantum computation: From Church-Turing thesis to Qubits

Shankhadip Kundu, Rajdeep Kundu, Shubhabrata Kundu +4 more

In the paper we interpret the Church Turing thesis of Computation Algorithm and how it differs from the strong Church Turing thesis in the field of computation. Church Turing thesis can be classified as Strong Church Turing thesis and Normal Church Turing thesis. Church Turing hypothesis says “that a computing problem can be solved in any computer if and only if it can be solved on a very simple ‘machine’, named TURING MACHINE”. We introspect the difference in the model of computers that are developed on these two competitive algorithms. We will also be studying the physical realization of bits in a quantum computer with special mention to the commercial quantum computer systems offered at the moment. Our objective is to find out the relation of a quantum bit and the Strong Church Turing Thesis converging the gap between theoretical model and physical structure.

IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON)•Oct 1, 2016•7 citations
Landauer's principle claims that "Information is Physical." It is not surprising that its conceptual antithesis, Wheeler's "It from Bit," has been more popular among computer scientists --- in the form of the Church-Turing hypothesis: All natural processes can be computed by a universal Turing machine; physical laws then become descriptions of subsets of observable, as opposed to merely possible, computations. Switching back and forth between the two traditional styles of thought, motivated by quantum-physical Bell correlations and the doubts they raise about fundamental space-time causality, we look for an intrinsic, physical randomness notion and find one around the second law of thermodynamics. Bell correlations combined with complexity as randomness tell us that beyond-Turing computations are either physically impossible, or they can be carried out by "devices" as simple as individual photons.
Some of the philosophical questions raised by the theory of quantum computation are discussed. First it is considered whether the possibility of exponential speed-up in quantum computation provides an argument for a more substantive notion of quantum information than so far allowed. It is concluded that this is not so. Then some questions regarding the status of the Church-Turing hypothesis in the light of quantum computation are considered. In particular, Deutsch’s claim that a physical principle, the Turing Principle, underlies the Church-Turing hypothesis is rebutted. Finally, the question of whether the Church-Turing hypothesis might serve as a constraint on the laws of physics is briefly considered.
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
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.
There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].
In the paper we interpret the Church Turing thesis of Computation Algorithm and how it differs from the strong Church Turing thesis in the field of computation. Church Turing thesis can be classified as Strong Church Turing thesis and Normal Church Turing thesis. Church Turing hypothesis says “that a computing problem can be solved in any computer if and only if it can be solved on a very simple ‘machine’, named TURING MACHINE”. We introspect the difference in the model of computers that are developed on these two competitive algorithms. We will also be studying the physical realization of bits in a quantum computer with special mention to the commercial quantum computer systems offered at the moment. Our objective is to find out the relation of a quantum bit and the Strong Church Turing Thesis converging the gap between theoretical model and physical structure.