Questions tagged [church-turing-thesis]
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.
7
questions
2
votes
1
answer
57
views
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 ...
- 133
3
votes
1
answer
77
views
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 ...
- 10.2k
5
votes
0
answers
96
views
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 ...
- 2,302
5
votes
2
answers
426
views
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 ...
- 51
3
votes
1
answer
79
views
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 ...
- 2,439
4
votes
2
answers
232
views
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 ...
- 17.1k
9
votes
3
answers
4k
views
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 ...
- 17.1k