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

IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON)

Quantum computation: From Church-Turing thesis to Qubits

Shankhadip Kundu, Rajdeep Kundu, Shubhabrata Kundu, Anubhab Bhattachaijee, Sayantan Gupta, Souvik Ghosh, Indranil Basu

Published Oct 1, 2016• 8 citations
Publisher

Abstract

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.

DOI
10.1109/uemcon.2016.7777805

Related papers

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

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

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

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

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
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.
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
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].
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.
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.
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.
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.