My understanding is that there seems to be some confidence that quantum annealing will provide a speedup for problems like the traveling salesman, due to the efficiency provided by, ex, quantum tunneling. Do we know, however, around how much of a speedup is provided?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
First, let me note that quantum annealing, or more precisely the adiabatic quantum computation model is polynomially equivalent to the conventional gate-based quantum computation model. Second, the general traveling salesman problem is NP complete. Third, it is generally believed that the with gate-based quantum computation one cannot solve in polinomial time NP complete problems. All this means that it is regarded highly unlikely that with quantum annealing one could solve in polynomial time the general traveling salesman problem.
Despite that it is believed that the general problem can be only solved in exponential time also with quantum annealing, there could still be some speed up, for instance, a polynomial speed-up. Not too much is known about this for the general case. However, there is a very nice recent work that shows that there are bounded-error quantum algorithms which provide a quadratic quantum speedup when the degree of each vertex (in the travailing salesman problem) is at most 3.
