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

$\endgroup$

closed as off-topic by Kristoffer Arnsfelt Hansen, Sasho Nikolov, R B, Marzio De Biasi, Niel de Beaudrap Apr 10 '15 at 17:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kristoffer Arnsfelt Hansen, Sasho Nikolov, R B, Marzio De Biasi, Niel de Beaudrap
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 8
    $\begingroup$ "I know that a quantum computer with n qubits can make 2^n in a single step." No! $\endgroup$ – Sasho Nikolov Apr 10 '15 at 12:18
  • 2
    $\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 '15 at 15:15
  • $\begingroup$ I think what quantum computers do is a lot like that. $\endgroup$ – Jamie Vicary Jul 29 '16 at 21:12
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.

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

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