I would like to ask if anyone has any ideas about what a universal quantum turing machine (UQTM) can do as supposed to a classical universal turing machine (UTM) (i.e. quantum computer vs classical computer).

I wonder if a UQTM can solve NP problems as supposed to a UTM. I know that one of the biggest ideas in computability is that giving enough time the slow computer will calculate the samething as the fast computer just with more time. Since a UQTM can solve higher complexity problems (such as solving a molecular system) at faster speeds then a UTM, this doesn't mean for the UTM this is unsolvable.

Therefor, are there problems a UQTM can solve that a UTM cannot and vice-versa?

What about NP problems or non-computable problems?

  • 5
    $\begingroup$ Short answers: (i) any QTM can be simulated by a TM so every language decidable by a QTM is decidable by a TM [wikipedia]. (ii) It is not known whether any NP-hard problem can be solved in poly time by a QTM, but some problems (e.g. factoring) that are not known to have poly-time algorithms do have poly-time QTM algorithms [wikipedia]. Try to find an intro to quantum computing for more details. This is not a research-level question so will probably be closed. $\endgroup$
    – Neal Young
    Jan 30, 2023 at 18:04
  • $\begingroup$ Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. $\endgroup$
    – Community Bot
    Feb 8, 2023 at 11:43


Your Answer

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