# Travelling sales man with Quantum Computers [closed]

I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for example, A quantum computer with 500 qubits) .I know that a quantum computer with n qubits can make 2^n in a single step and so a quantum computer with 500 qubits can make 2^500 calculations in a single step.

In classical computers, TSM has a time complexity of O(2^n). What is the time complexity if we deal with quantum computers for TSM ?

Also can a quantum traverse any loop in no time ??

• "I know that a quantum computer with n qubits can make 2^n in a single step." No! – Sasho Nikolov Apr 10 '15 at 12:18
• Specifically, quantum computers do not do anything like trying all possibilities in parallel, and selecting the possibility that works. Quantum indeterminism is much more like randomness than it is like that. – Niel de Beaudrap Apr 10 '15 at 15:15
• I think what quantum computers do is a lot like that. – Jamie Vicary Jul 29 '16 at 21:12

However, it is not yet known whether NP $\subseteq$ BQP, and the informal consensus is that this containment is in fact very unlikely. There is circumstantial evidence, in the sense that NP is not contained in BQP with probability 1 relative to a random oracle, and NP $\cap$ coNP is not contained in BQP with probability 1 relative to a random permutation oracle.