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
62
votes
3answers
2k 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 ...
29
votes
2answers
996 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 ...
2
votes
0answers
43 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
0answers
103 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 ...
1
vote
0answers
14 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\...