QUANTUM ALGORITHM FOR SOLVING THE TRAVELING SALESMAN PROBLEM

Abstract

We propose a new quantum algorithm for the Traveling Sales­man Problem (TSP). The algorithm is an extension of our recently intro­duced pattern search algorithm, which based on Hough transformation and Grover algorithm. Based on Lehmer code we directly build the circuit of acted elements of the symmetric group , and have a chance to add some heuristic informations. The result is a way of re-indexing elements of , so that a permutation that is a solution could be found at small in­dexes. The pattern search algorithm is then applied on a searching space that its size was reduced significantly.