QUANTUM ALGORITHM FOR SOLVING THE TRAVELING SALESMAN PROBLEM

Huynh Van Duc, Bui Doan Khanh, Do Ngoc Diep
Author affiliations

Authors

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

DOI:

https://doi.org/10.15625/0866-708X/49/5/1887

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.

Downloads

Download data is not yet available.

Published

08-08-2012

How to Cite

[1]
H. V. Duc, B. D. Khanh, and D. N. Diep, “QUANTUM ALGORITHM FOR SOLVING THE TRAVELING SALESMAN PROBLEM”, Vietnam J. Sci. Technol., vol. 49, no. 5, Aug. 2012.

Issue

Section

Articles