We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [quantum-turing-machine]

For questions about the quantum analogue of the universal Turing machine; i.e., for questions about the theoretical construct that is the universal quantum computer. This tag is not for questions about the normal Turing machine; those would fit better on Computer Science SE.

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 ...
2
votes
3answers
209 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 ...