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

FCS

The Church-Turing-Deutsch Principle in Quantum Computation.

P. Prashant

Published Jan 1, 2006• 0 citations
OpenAlex

Related papers

Quantum Computers: the Church-Turing Hypothesis Versus the Turing Principle

Christopher G. Timpson

Springer eBooks•Jan 1, 2004•12 citations

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

Deutsch's Quantum Computer

WORLD SCIENTIFIC eBooks•May 1, 2000•0 citations

The Mechanism of Quantum Computation

Giuseppe Castagnoli

International Journal of Theoretical Physics•Mar 7, 2008•5 citations

Efficient classical simulation of the Deutsch-Jozsa algorithm

Niklas Johansson, Larsson, Jan-Åke

In 1985, David Deutsch challenged the Church-Turing thesis by stating that his quantum model of computation "could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine". While this is thought to be true in general, there is usually no way of knowing that the corresponding classical algorithms are the best possible solutions. Here we provide an efficient classical simulation of the Deutsch-Jozsa algorithm, which was one of the first examples of quantum computational speed-up. Our conclusion is that the Deutsch-Jozsa quantum algorithm owes its speed-up to resources that are not necessarily quantum-mechanical, and when compared with the classical simulation offers no speed-up at all.

arXiv:1506.04627•Jun 15, 2015•2 citations
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.
In 1985, David Deutsch challenged the Church-Turing thesis by stating that his quantum model of computation "could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine". While this is thought to be true in general, there is usually no way of knowing that the corresponding classical algorithms are the best possible solutions. Here we provide an efficient classical simulation of the Deutsch-Jozsa algorithm, which was one of the first examples of quantum computational speed-up. Our conclusion is that the Deutsch-Jozsa quantum algorithm owes its speed-up to resources that are not necessarily quantum-mechanical, and when compared with the classical simulation offers no speed-up at all.