Table of Content

Open Access iconOpen Access



The Quantum Approximate Algorithm for Solving Traveling Salesman Problem

Yue Ruan1, *, Samuel Marsh2, Xilin Xue1, Zhihao Liu3, Jingbo Wang2, *

1 School of Computer Science and Technology, Anhui University of Technology, Maanshan, China.
2 School of Physics, University of Western Australia, Perth, Australia.
3 School of Computer Science and Engineering, Southeast University, Nanjing, China.

* Corresponding Authors: Yue Ruan. Email: email;
  Jingbo Wang. Email: email.

Computers, Materials & Continua 2020, 63(3), 1237-1247.


The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems. It consists of interleaved unitary transformations induced by two operators labelled the mixing and problem Hamiltonians. To fit this framework, one needs to transform the original problem into a suitable form and embed it into these two Hamiltonians. In this paper, for the well-known NP-hard Traveling Salesman Problem (TSP), we encode its constraints into the mixing Hamiltonian rather than the conventional approach of adding penalty terms to the problem Hamiltonian. Moreover, we map edges (routes) connecting each pair of cities to qubits, which decreases the search space significantly in comparison to other approaches. As a result, our method can achieve a higher probability for the shortest round-trip route with only half the number of qubits consumed compared to IBM Q’s approach. We argue the formalization approach presented in this paper would lead to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to NP optimization problems.


Cite This Article

APA Style
Ruan, Y., Marsh, S., Xue, X., Liu, Z., Wang, J. (2020). The quantum approximate algorithm for solving traveling salesman problem. Computers, Materials & Continua, 63(3), 1237-1247.
Vancouver Style
Ruan Y, Marsh S, Xue X, Liu Z, Wang J. The quantum approximate algorithm for solving traveling salesman problem. Comput Mater Contin. 2020;63(3):1237-1247
IEEE Style
Y. Ruan, S. Marsh, X. Xue, Z. Liu, and J. Wang "The Quantum Approximate Algorithm for Solving Traveling Salesman Problem," Comput. Mater. Contin., vol. 63, no. 3, pp. 1237-1247. 2020.

cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 5248


  • 2662


  • 0


Related articles

Share Link