A hypothesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.
Questions tagged [church-turing-thesis]
8 questions
11
votes
3 answers
What precisely is the quantum extended Church-Turing thesis?
Context
Prof. Aaronson mentions that the quantum extended Church-Turing (quantum ECT) thesis has no known counterexamples cf. around 14:18 but doesn't mention its precise statement.
Questions
What precisely is the statement of the quantum extended…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
7
votes
2 answers
Does there exists an algorithm to construct a quantum circuit given an arbitrary unitary?
Suppose there exists an algorithm that takes as input an arbitrary unitary matrix and produces as output a quantum circuit representing that matrix. Then in theory that algorithm could construct any quantum circuit. This would be quite…
treks2448
- 71
- 1
6
votes
0 answers
Consequences of MIP*=RE regarding quantum universality
Provided that $\mathsf{MIP}^*=\mathsf{RE}$ there can be Bell inequalities that have violations achievable only for infinite dimensional quantum systems (vide discussions in Post1 and Post2). Does this implies that this kind of behaviour, once found,…
R.W
- 2,468
- 7
- 25
4
votes
2 answers
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?
Note: This has been cross-posted to CS Theory SE.
If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies the Extended Church Turing thesis. However, in a related…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
3
votes
1 answer
Quantum circuits, quantum Turing machine and universal quantum computer-comparing different models of quantum computations
Forgive me if this question was already asked somewhere on this site-I haven't found it but it is possible that I've overlooked it. So basically, I would like to summarize different notions of quantum models of computations, namely:
Quantum…
truebaran
- 203
- 1
- 6
3
votes
1 answer
What kind of program was Deutsch envisioning to test for the linearity of quantum mechanics?
I've recently been studying Deutsch's 1985 paper "Quantum theory, the Church-Turing principle and the universal quantum computer" (pdf here). In this he endorses the position that a naïve statement of the Church-Turing thesis is in tension with…
Mark Spinelli
- 15,378
- 3
- 26
- 83
3
votes
1 answer
How does a quantum circuit capture the "non-halting ability" of classical Turing machines?
It is claimed that a quantum Turing machine is "computationally" equivalent to the circuit model. Quantum computing also includes all classical computing. However, we know that there are classical Turing machines that do not halt on certain…
user1936752
- 3,311
- 1
- 9
- 24
0
votes
0 answers
What the key difficulty in (efficiently) simulating a 'Quantum Turing machine' with 'Non-deterministic Turing machine '?
I am reading Niel de Beaudrap's answer in quantumcomputing.SE post to understand the workings of:
Deterministic Turing Machine (DTM),
Non-deterministic Turing Machine (NDTM) and
Quantum Truing machine (QTM).
The transition tree model of these…
108_mk
- 883
- 1
- 6
- 20