Isaac Scientific Publishing

Journal of Advances in Applied Mathematics

Small Traveling Salesman Problems

Download PDF (330.7 KB) PP. 101 - 107 Pub. Date: March 23, 2017

DOI: 10.22606/jaam.2017.22003

Author(s)

  • Richard H. Warren*
    Retired: Lockheed Martin Corporation, King of Prussia, PA 19406, USA

Abstract

This paper illustrates fundamental principles about small traveling salesman problems (TSPs) which are a current application for quantum annealing computers. The 2048 qubit, quantum annealing computer manufactured by D-Wave Systems is estimated to be able to solve all TSPs on 8 cities, which advances a recent 4-city result on a quantum simulator. Additionally, the D-Wave quantum computer is expected to find all optimal tours for each TSP. To prepare for this, we show the expected quantum output for 5,000 randomly generated TSPs on 6, 8 and 10 cities. The examples in the TSPLIB have 14 or more cities. These are too large for the current quantum annealing processors. We have included an annotated bibliography about solving the TSP on a quantum computer.

Keywords

Traveling salesman, optimal tour, combinatorial analysis, discrete optimization, quantum annealing

References

[1] J. Bang, J. Ryu, C. Lee, S. Yoo, J. Lim, J. Lee, A quantum heuristic algorithm for the traveling salesman problem, J. Korean Phys. Soc. 61 (2012) 1944-1949. http://link.springer.com/article/10.3938/jkps.61.1944

[2] G. Barach, H. Fort, Y. Mehlman, F. Zypman, Information in the traveling salesman problem, Applied Mathematics 3 (2012) 926-930. http://dx.doi.org/10.4236/am.2012.38138

[3] Z. Bian, F. Chudak, R. Israel, B. Lackey, W. G. Macready, A. Roy, Discrete optimization using quantum annealing on sparse Ising models. Front. Phys. 2 Article 56 (2014) 10 pages. DOI:10.3389/fphy.2014.00056

[4] H. Chen, X. Kong, B. Chong, G. Qin, X. Zhou, X. Peng, J. Du, Experimental demonstration of a quantum annealing algorithm for the traveling salesman problem in a nuclear-magnetic-resonance quantum simulator, Phys. Review A 83 (2011) 5 pages. DOI:10.1103/PhysRevA.83.032314

[5] W. J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, Princeton, NJ. 2012.

[6] E. Dahl, Travelling Salesman Problem, D-Wave Systems Tutorial (Sep. 2013). Viewed Jan. 20, 2017 from http://web.archive.org/web/20130910030209/http://www.dwavesys.com/en/dev-tutorial-tsp.htm

[7] G. Gutin, A. P. Punnen (editors), The Traveling Salesman Problem and Its Variations, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002.

[8] J. Inoue, Infinite-range transverse field Ising models and quantum computation, Eur. Phys. J. Special Topics 224 (2015) 149-161. DOI:10.1140/epjst/e2015-02348-x

[9] S. R. Kumar, T. S. Lamba, The travelling salesman cipher, Journal IETE 40 (1994) 151-154.

[10] G. Laporte, A concise guide to the traveling salesman problem, J. Operational Res. Soc. 61 (2010) 35-40. DOI:10.1057/jors.2009.76

[11] A. Lucas, Ising formulations of many NP problems. Front. Phys. 2 Article 5 (2014) 15 pages. DOI:10.3389/fphy.2014.00005

[12] R. Martoňák, G. E. Santoro, E. Tosatti, Quantum annealing of the traveling salesman problem, Phys. Rev. E 70 (2004) 5 pages. DOI:10.1103/PhysRevE.70.057701

[13] C. C. McGeoch, C. Wang, Experimental evaluation of an adiabatic quantum system for combinatorial optimization, in Proceedings of the ACM International Conference on Computing Frontiers (2013 Proceedings), Article No. 23, ACM Press, New York, 2013. DOI:10.1145/2482767.2482797

[14] H. R. Moser, The quantum mechanical solution of the traveling salesman problem, Phys. E 16 (2003) 280-285. DOI:10.1016/S1386-9477(02)00928-1

[15] G. E. Santoro, E. Tosatti, Optimization using quantum mechanics: quantum annealing through adiabatic evolution, J. Phys. A 39 (2006) R393-R431. DOI:10.1088/0305-4470/39/36/R01

[16] S. Suzuki, J. Inoue, B. K. Chakrabarti, Quantum Ising Phases and Transitions in Transverse Ising Models, 2nd edition, Lecture Notes in Physics 862, Springer, Berlin, 2013. DOI:10.1007/978-3-642-33039-1

[17] TSPLIB is a library of sample instances for the TSP available at http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf

[18] E. Tsukerman, Ping-pong and the traveling salesman problem, Experimental Mathematics, 25 (2016) 1-7. DOI: 10.1080/10586458.2014.1002140

[19] R. H. Warren, Adapting the traveling salesman problem to an adiabatic quantum computer, Quantum Inf. Process. 12 (2013) 1781-1785. DOI:10.1007/s11128-012-0490-8

[20] R. H. Warren, Special Cases of the Traveling Salesman Problem. Applied Mathematics and Computation 60 (1994) 171-177. DOI: 10.1016/0096-3003(94)90103-1

[21] R. H. Warren, Optimal Arcs for the Traveling Salesman Problem, Applied Mathematics Letters 5 (1992) 13-14. DOI: 10.1016/0893-9659(92)90028-8