Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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.

Filter by
Sorted by
Tagged with
10 votes
3 answers
5k 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 ...
Sanchayan Dutta's user avatar
7 votes
2 answers
573 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 ...
treks2448's user avatar
5 votes
0 answers
104 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 ...
R.W's user avatar
  • 2,337
4 votes
2 answers
249 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 ...
Sanchayan Dutta's user avatar
3 votes
1 answer
126 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 ...
truebaran's user avatar
  • 153
3 votes
1 answer
120 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 ...
Mark Spinelli's user avatar
3 votes
1 answer
88 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 ...
user1936752's user avatar
  • 2,997