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
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 ...
Sanchayan Dutta's user avatar
4 votes
2 answers
246 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