Questions tagged [computability-theory]

For questions on Church-Turing thesis, computable functions, etc. as relevant to quantum computing. It is a major branch of the theory of computation. Computability theory, also known as recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. (Wikipedia)

Filter by
Sorted by
Tagged with
3
votes
2answers
128 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 ...
2
votes
0answers
23 views

Explicit Construction of Classical Rules in Quantum Turing Machine

I knew that we usually use circuit instead of Turing machine in Quantum computation. In a deterministic Turing machine one has transition rules, $$ \delta: Q\times\Gamma\rightarrow Q\times\Gamma\...
2
votes
0answers
48 views

Quantum algorithms for Prolog or automated theorem proving?

Are there quantum algorithms for Prolog (SLD resolution - unification and depth-first-search) or for automated theorem proving in general (negation, resolution, and SAT)? Usually automated theorem ...
2
votes
3answers
225 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 ...
30
votes
2answers
1k views

Can a quantum computer simulate a normal computer?

Similar to the question Could a Turing Machine simulate a quantum computer?: given a 'classical' algorithm, is it always possible to formulate an equivalent algorithm which can be performed on a ...
62
votes
3answers
3k views

Can a Turing machine simulate a quantum computer?

I know that a Turing machine1 can theoretically simulate "anything", but I don't know whether it could simulate something as fundamentally different as a quantum-based computer. Are there any ...