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.
2
questions
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
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