<p>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 <strong>BQP</strong>. </p>

<p>Travelling salesman problem is in complexity class called <strong>NP</strong>. Furthermore, it is <strong>NP</strong>-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 <strong>NP</strong>.</p>

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

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

<p>Most results about <strong>BQP</strong> are summarized at the <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp" rel="noreferrer"><strong>BQP</strong> article in the Complexity Zoo</a>.</p>

CC BY-SA 3.0
2015-04-13T10:23:34.290Z
please stop making insignificant edits to old posts.
Kaveh
CC BY-SA 3.0
2015-04-13T11:07:05.497Z
Sure. I didn't realise that I am digging out and making those questions active.
TCS-user-23
CC BY-SA 3.0
2015-04-10T09:58:59.170Z
2015-04-10T17:14:13.447Z
2015-04-10T17:14:13.447Z
TCS-user-23
<p>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.</p>

<p>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 ?</p>

<p>Also can a quantum traverse any loop in no time ??</p>

CC BY-SA 3.0
2015-04-10T12:18:42.830Z
"I know that a quantum computer with n qubits can make 2^n in a single step." No!
Sasho Nikolov
CC BY-SA 3.0
2015-04-10T15:15:14.290Z
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
CC BY-SA 3.0
2016-07-29T21:12:46.117Z
I think what quantum computers do is a lot like that.
Jamie Vicary
<quantum-computing><time-complexity><quantum-information><np-complete><analysis-of-algorithms>
Travelling sales man with Quantum Computers
alkabary
# Travelling sales man with Quantum Computers

(Asked by: username_0 on 2015-04-10)

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 ??

**Tags:** quantum-computing, time-complexity, quantum-information, np-complete, analysis-of-algorithms

> **Comments:**
> **username_1**: "I know that a quantum computer with n qubits can make 2^n in a single step." No!  
> **username_2**: 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.  
> **username_3**: I think what quantum computers do is a lot like that.  

---

## 1 answers

### Answer by username_4 on 2015-04-10. Score: 5

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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp).

> **Comments:**
> **username_5**: please stop making insignificant edits to old posts.  
> **username_4**: Sure. I didn't realise that I am digging out and making those questions active.  

---

