<p>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).</p>
<p>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.</p>
<p>Therefor, are there problems a UQTM can solve that a UTM cannot and vice-versa?</p>
<p>What about NP problems or non-computable problems?</p>

CC BY-SA 4.0
2023-01-30T18:04:10.247Z
Short answers: (i) any QTM can be simulated by a TM so every language decidable by a QTM is decidable by a TM [[wikipedia](https://en.wikipedia.org/wiki/Quantum_computing#Computability)].  (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](https://en.wikipedia.org/wiki/Quantum_computing#Complexity)].  Try to find an intro to quantum computing for more details.  This is not a research-level question so will probably be closed.
Neal Young
CC BY-SA 4.0
2023-02-08T11:43:57.317Z
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.
Community
<quantum-computing><computability><turing-machines><universal-turing-machines>
Computability for universal quantum turing machines
Shane Gervais
# Computability for universal quantum turing machines

(Asked by: username_0 on 2023-01-30)

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?

**Tags:** quantum-computing, computability, turing-machines, universal-turing-machines
> **Comments:**
> **username_1**: Short answers: (i) any QTM can be simulated by a TM so every language decidable by a QTM is decidable by a TM [[wikipedia](https://en.wikipedia.org/wiki/Quantum_computing#Computability)].  (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](https://en.wikipedia.org/wiki/Quantum_computing#Complexity)].  Try to find an intro to quantum computing for more details.  This is not a research-level question so will probably be closed.  
> **username_2**: Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.  

---

## 0 answers

