An Efficient Quantum Algorithm for the Traveling Salesman Problem

The traveling salesman problem is the problem of finding out the shortest route in a network of cities, that a salesman needs to travel to cover all the cities, without visiting the same city more than once. This problem is known to be N P -hard with a brute-force complexity of O(N ^N) or O(N ^2N) for N number of cities. This problem is equivalent to finding out the shortest Hamiltonian cycle in a given graph, if at least one Hamiltonian cycle exists in it. Quantum algorithms for this problem typically provide with a quadratic speedup only, using Grover’s search, thereby having a complexity of O(N ^N/2) or O(N ^N). We present a bounded-error quantum polynomial-time (BQP) algorithm for solving the problem, providing with an exponential speedup. The overall complexity of our algorithm is O(N ³ log(N)κ/ϵ + 1/ϵ³), where the errors ϵ are O(1/poly(N)), and κ is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.