2
$\begingroup$

I studied about Quantum Turing machine and i figured out that the difference between QTM and TM is in transition function and also if a problem is unsolvable by a TM then it is unsolvable by a QTM but I need a justifiable reason to claim QTM does not contradict with Church-Turing thesis.

$\endgroup$

1 Answer 1

4
$\begingroup$

Quantum Turing machines can be simulated by classical Turing machines. See Deutsch's fundamental paper Quantum theory, the Church-Turing principle and the universal quantum computer.

$\endgroup$
2
  • $\begingroup$ Can classical Turing machine simulate the Quantum Turing machine with at most polynomial slowdown? Are there some references? $\endgroup$
    – narip
    Dec 1, 2021 at 8:59
  • $\begingroup$ Okay, I found an answer in this problem link. $\endgroup$
    – narip
    Dec 1, 2021 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.