# 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

## 1 Answer

The set of problems that can be solved by an universal quantum computer in "polynomial time" (with at most 1/3 probability of error) is called BQP.

Travelling salesman problem is in complexity class called NP. Furthermore, it is NP-complete: meaning that if the Travelling Salesman Problem can be solved in any model of computation which can also simulate polynomial-time deterministic computation, then that model of computation can solve any problem in NP.

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.

More generally, quantum computers do not provide any known super-polynomial advantage for solving NP-complete problems. (Techniques such as Grover's Search can provide polynomial-time speedups, though.)

Most results about BQP are summarized at the BQP article in the Complexity Zoo.

• please stop making insignificant edits to old posts. – Kaveh Apr 13 '15 at 10:23
• Sure. I didn't realise that I am digging out and making those questions active. – TCS-user-12 Apr 13 '15 at 11:07