A Quantum Heuristic Algorithm for the Traveling Salesman Problem

Abstract

We propose a quantum heuristic algorithm to solve a traveling salesman problem by generalizing Grover search. Sufficient conditions are derived to greatly enhance the probability of finding thetours with the cheapest costs reaching almost to unity. These conditions are characterized by statistical properties of tour costs and shown to be automatically satisfied in the large number limitof cities. In particular for a continuous distribution of the tours along the cost we show that the quantum heuristic algorithm exhibits the quadratic speedup over its classical heuristic algorithm.