A Quantum Algorithm for Solving the Traveling Salesman Problem

  • Duc Huynh Van Duc Huynh Van
  • Khanh Bui Doan Khanh Bui Doan
  • Diep Do Ngoc Diep Do Ngoc

Abstract

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 Sn, and have a chance to add some heuristic informations. The result is a way of re-indexing elements of Sn, 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.

điểm /   đánh giá
Published
2014-11-12
Section
Articles