-7
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 9
    $\begingroup$ "I know that a quantum computer with n qubits can make 2^n in a single step." No! $\endgroup$
    – Sasho Nikolov
    Apr 10, 2015 at 12:18
  • 3
    $\begingroup$ 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. $\endgroup$
    – Niel de Beaudrap
    Apr 10, 2015 at 15:15
  • $\begingroup$ I think what quantum computers do is a lot like that. $\endgroup$
    – Jamie Vicary
    Jul 29, 2016 at 21:12

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ please stop making insignificant edits to old posts. $\endgroup$
    – Kaveh
    Apr 13, 2015 at 10:23
  • $\begingroup$ Sure. I didn't realise that I am digging out and making those questions active. $\endgroup$
    – TCS-user-23
    Apr 13, 2015 at 11:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.