Evaluating quantum-classical heuristics for traveling salesman problem

Cover Page

Cite item

Full Text

Abstract

In this paper, we develop and evaluate a hybrid quantum-classical heuristic approach to solving the Traveling Salesman Problem. This approach uses exhaustive enumeration of the starting paths and optimizes the remainder of the route using quantum computing. For quantum co-processing, we use either the Variational Quantum Eigensolver or the Quantum Annealing. Results of evaluation of the approach on several datasets including TSPLIB and touristic data for Petrozavodsk and Karelia Republic, both in simulation and in hardware, are presented. Issues of practical applicability are also discussed.

About the authors

Mariia A. Makarova

Petrozavodsk State University; Institute of Applied Mathematical Research of the KarRC RAS

Email: masha.mariam.maltseva@mail.ru
ORCID iD: 0000-0002-7982-0209
Scopus Author ID: 57204436887
ResearcherId: AAZ-7810-2021

junior researcher, PhD student, SMITS Lab, Institute of Applied Mathematical Research of the Karelian Research Center of Russian Academy of Sciences; lecturer, Petrozavodsk State University

33 Lenina Pr, Petrozavodsk, 185910, Russian Federation; 11 Pushkinskaya St, Petrozavodsk, 185910, Russian Federation

Sergey V. Fedorov

Petrozavodsk State University

Email: sergey-fedorov-04@mail.ru
Bachelor’s degree student 33 Lenina Pr, Petrozavodsk, 185910, Russian Federation

Anna V. Titova

Petrozavodsk State University

Email: masha.mariam.maltseva@mail.ru
Bachelor’s degree student 33 Lenina Pr, Petrozavodsk, 185910, Russian Federation

Alexander A. Khomich

Petrozavodsk State University

Email: masha.mariam.maltseva@mail.ru
Bachelor’s degree student 33 Lenina Pr, Petrozavodsk, 185910, Russian Federation

Alexander S. Rumyantsev

Petrozavodsk State University; Institute of Applied Mathematical Research of the KarRC RAS

Author for correspondence.
Email: ar0@krc.karelia.ru
ORCID iD: 0000-0003-2364-5939
Scopus Author ID: 36968331100
ResearcherId: L-1354-2013

Doctor of Physical and Mathematical Sciences, Leading researcher, SMITS Lab, Institute of Applied Mathematical Research of the Karelian Research Center of Russian Academy of Sciences; professor, Petrozavodsk State University

33 Lenina Pr, Petrozavodsk, 185910, Russian Federation; 11 Pushkinskaya St, Petrozavodsk, 185910, Russian Federation

References

  1. Jünger, M., Reinelt, G. & Rinaldi, G. Chapter 4 The traveling salesman problem in Network Models (Elsevier, 1995). doi: 10.1016/s0927-0507(05)80121-5.
  2. Abbas, A. et al. Challenges and opportunities in quantum optimization. Nature Reviews Physics 6, 718-735. doi: 10.1038/s42254-024-00770-9 (Dec. 2024).
  3. Held, M. & Karp, R. M. A Dynamic Programming Approach to Sequencing Problems. Journal of the Society for Industrial and Applied Mathematics 10, 196-210. doi: 10.1137/0110015 (Mar. 1962).
  4. Filip, E. & Otakar, M. The travelling salesman problem and its application in logistic practice. 8, 163-173 (Oct. 2011).
  5. Kizilateş, G. & Nuriyeva, F. On the Nearest Neighbor Algorithms for the Traveling Salesman Problem in Advances in Computational Science, Engineering and Information Technology (Springer International Publishing, 2013). doi: 10.1007/978-3-319-00951-3_11.
  6. Helsgaun, K. General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation 1, 119-163. doi: 10.1007/s12532-009-0004-6 (Oct. 2009).
  7. Lin, S. & Kernighan, B. W. An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research 21, 498-516. doi: 10.1287/opre.21.2.498 (Apr. 1973).
  8. Shor, P. Algorithms for quantum computation: discrete logarithms and factoring in Proceedings 35th Annual Symposium on Foundations of Computer Science (1994), 124-134. doi: 10.1109/SFCS.1994. 365700.
  9. Deutsch, D. & Jozsa, R. Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439. Publisher: Royal Society, 553-558. doi: 10.1098/rspa.1992.0167 (Jan. 1997).
  10. Markidis, S. What is Quantum Parallelism, Anyhow? en. in ISC High Performance 2024 Research Paper Proceedings (39th International Conference) (IEEE, Hamburg, Germany, May 2024), 1-12. doi: 10.23919/ISC.2024.10528926.
  11. Cheng, B. et al. Noisy intermediate-scale quantum computers. Frontiers of Physics 18, 21308. doi: 10.1007/s11467-022-1249-z (Mar. 2023).
  12. Cerezo, M. et al. Variational quantum algorithms. Nature Reviews Physics 3, 625-644. doi:10.1038/ s42254-021-00348-9 (Sept. 2021).
  13. Grange, C., Poss, M. & Bourreau, E. An introduction to variational quantum algorithms for combinatorial optimization problems. en. Annals of Operations Research 343, 847-884. doi:10. 1007/s10479-024-06253-5 (Dec. 2024).
  14. Mohseni, N., McMahon, P. L. & Byrnes, T. Ising machines as hardware solvers of combinatorial optimization problems. Nature Reviews Physics 4, 363-379. doi: 10.1038/s42254-022-00440-8 (June 2022).
  15. Phillipson, F. Quantum Computing in Logistics and Supply Chain Management an Overview en. arXiv:2402.17520 [quant-ph]. Feb. 2024. doi: 10.48550/arXiv.2402.17520.
  16. Qian, W., Basili, R. A. M., Eshaghian-Wilner, M. M., Khokhar, A., Luecke, G. & Vary, J. P. Comparative Study of Variations in Quantum Approximate Optimization Algorithms for the Traveling Salesman Problem. en. Entropy 25, 1238. doi: 10.3390/e25081238 (Aug. 2023).
  17. Ruan, Y., Marsh, S., Xue, X., Liu, Z. & Wang, J. The Quantum Approximate Algorithm for Solving Traveling Salesman Problem. en. Computers, Materials & Continua 63, 1237-1247. doi:10.32604/ cmc.2020.010001 (2020).
  18. Schnaus, M., Palackal, L., Poggel, B., Runge, X., Ehm, H., Lorenz, J. M. & Mendl, C. B. Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms in 2024 IEEE International Conference on Quantum Software (QSW) (IEEE, Shenzhen, China, July 2024), 81-87. doi: 10.1109/QSW62656.2024.00022.
  19. Zhu, J., Gao, Y., Wang, H., Li, T. & Wu, H. A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem en. arXiv:2212.02735 [quant-ph]. Dec. 2022. doi: 10.48550/arXiv.2212.02735.
  20. Matsuo, A., Suzuki, Y., Hamamura, I. & Yamashita, S. Enhancing VQE Convergence for Optimization Problems with Problem-specific Parameterized Quantum Circuits. en. IEICE Transactions on Information and Systems E106.D. arXiv:2006.05643 [quant-ph], 1772-1782. doi: 10.1587/transinf.2023EDP7071 (Nov. 2023).
  21. Warren, R. H. Solving combinatorial problems by two D_Wave hybrid solvers: a case study of traveling salesman problems in the TSP Library Version Number: 1. 2021. doi: 10.48550/ARXIV.2106.05948.
  22. Jain, S. Solving the Traveling Salesman Problem on the D-Wave Quantum Computer. en. Frontiers in Physics 9, 760783. doi: 10.3389/fphy.2021.760783 (Nov. 2021).
  23. Goswami, K., Veereshi, G. A., Schmelcher, P. & Mukherjee, R. Solving The Travelling Salesman Problem Using A Single Qubit en. arXiv:2407.17207 [quant-ph]. Dec. 2024. doi: 10.48550/arXiv.2407. 17207.
  24. Mario, S. S., Pothamsetti, P., Antony, L., Vishwanath, T., Ha, D. S., Ahmed, A., Sinno, S., Thuravakkath, S. & M, D. S. Quantum Annealing Based Hybrid Strategies for Real Time Route Optimization en. 2024. doi: 10.2139/ssrn.4970901.
  25. Khumalo, M. T., Chieza, H. A., Prag, K. & Woolway, M. An investigation of IBM quantum computing device performance on combinatorial optimisation problems. en. Neural Computing and Applications 37, 611-626. doi: 10.1007/s00521-022-07438-4 (Jan. 2025).
  26. Nielsen, M. A. & Chuang, I. L. Quantum computation and quantum information 10th anniversary ed. en (Cambridge University Press, Cambridge ; New York, 2010).
  27. Jünger, M., Reinelt, G. & Rinaldi, G. en. Chapter 4 The traveling salesman problem in Handbooks in Operations Research and Management Science 225-330 (Elsevier, 1995). doi: 10.1016/0927-0507(05)80121-5.
  28. Biamonte, J. Universal variational quantum computation. en. Physical Review A 103, L030401. doi: 10.1103/PhysRevA.103.L030401 (Mar. 2021).
  29. Tilly, J. et al. The Variational Quantum Eigensolver: A review of methods and best practices. Physics Reports 986, 1-128. doi: 10.1016/j.physrep.2022.08.003 (Nov. 2022).
  30. Deglmann, P., Schäfer, A. & Lennartz, C. Application of quantum calculations in the chemical industry-An overview. International Journal of Quantum Chemistry 115, 107-136. doi: 10.1002/qua.24811 (Nov. 2014).
  31. Lordi, V. & Nichol, J. M. Advances and opportunities in materials science for scalable quantum computing. MRS Bulletin 46, 589-595. doi: 10.1557/s43577-021-00133-0 (July 2021).
  32. Cao, Y. et al. Quantum Chemistry in the Age of Quantum Computing. Chemical Reviews 119, 10856-10915. doi: 10.1021/acs.chemrev.8b00803 (Aug. 2019).
  33. Vesely, M. Finding the Optimal Currency Composition of Foreign Exchange Reserves with a Quantum Computer 2023. arXiv: 2303.01909 [econ.GN].
  34. Zhu, L., Liang, S., Yang, C. & Li, X. Optimizing Shot Assignment in Variational Quantum Eigensolver Measurement 2024. arXiv: 2307.06504 [quant-ph].
  35. Gantmacher, F. The Theory of Matrices (Chelsea Publishing Company, 1980).
  36. De Falco, D., Apolloni, B. & Cesa-Bianchi, N. A numerical implementation of quantum annealing in (July 1988).
  37. Su, J. Towards Quantum Computing: Solving Satisfiability Problem by Quantum Annealing (2018).
  38. Karp, R. M. Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane. en. Mathematics of Operations Research 2, 209-224 (1977).
  39. Karagul, K., Aydemir, E. & Tokat, S. Using 2-Opt based evolution strategy for travelling salesman problem. An International Journal of Optimization and Control: Theories & Applications (IJOCTA) 6, 103-113. doi: 10.11121/ijocta.01.2016.00268 (Mar. 2016).
  40. Estimating Quantum Volume for Advantage https://support.dwavesys.com/hc/en-us/community/posts/360051945133-Estimating-Quantum-Volume-for-Advantage.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download