A Quantum Algorithm for Solving the Traveling Salesman Problem

Tóm tắt

We propose a new quantum algorithm for the Traveling Salesman Problem (TSP). The algorithm is an extension of our recently introduced 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 S_n, and have a chance to add some heuristic informations. The result is a way of re-indexing elements of S_n, so that a permutation that is a solution could be found at small indexes. The pattern search algorithm is then applied on a searching space that its size was reduced significantly.