Discrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational Science2658-46702658-7149Peoples' Friendship University of Russia named after Patrice Lumumba (RUDN University)4525710.22363/2658-4670-2025-33-2-199-213BOMUBBModeling and SimulationМатематическое моделированиеResearch ArticleEvaluating quantum-classical heuristics for traveling salesman problemИсследование квантово-классической эвристики для задачи коммивояжераhttps://orcid.org/0000-0002-7982-020957204436887AAZ-7810-2021MakarovaMariia A.МакароваМ. А.

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

masha.mariam.maltseva@mail.ruFedorovSergey V.ФедоровС. В.Bachelor’s degree studentsergey-fedorov-04@mail.ruTitovaAnna V.ТитоваА. В.Bachelor’s degree studentmasha.mariam.maltseva@mail.ruKhomichAlexander A.ХомичА. А.Bachelor’s degree studentmasha.mariam.maltseva@mail.ruhttps://orcid.org/0000-0003-2364-593936968331100L-1354-2013RumyantsevAlexander S.РумянцевА. С.

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

ar0@krc.karelia.ruPetrozavodsk State UniversityПетрозаводский государственный университетInstitute of Applied Mathematical Research of the KarRC RASИнститут прикладных математических исследований КарНЦ РАН15072025332VOL 33, NO2 (2025)ТОМ 33, №2 (2025)19921325072025Copyright ©; 2025, Makarova M.A., Fedorov S.V., Titova A.V., Khomich A.A., Rumyantsev A.S.Copyright ©; 2025, Макарова М.А., Федоров С.В., Титова А.В., Хомич А.А., Румянцев А.С.2025Makarova M.A., Fedorov S.V., Titova A.V., Khomich A.A., Rumyantsev A.S.Макарова М.А., Федоров С.В., Титова А.В., Хомич А.А., Румянцев А.С.https://creativecommons.org/licenses/by-nc/4.0https://journals.rudn.ru/miph/article/view/45257

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.

В статье разрабатывается и оценивается гибридный квантово-классический эвристический подход к решению задачи коммивояжера. Этот подход использует исчерпывающий перебор начальных путей и оптимизирует оставшуюся часть маршрута с помощью квантовых вычислений. Для обработки на квантовой машине используется либо вариационный квантовый собственный решатель, либо квантовый отжиг. Представлены результаты оценки предложенного подхода на нескольких наборах данных, включая TSPLIB и туристические данные для Петрозаводска и Республики Карелия, как в режиме имитации, так и на соответствующей квантовой машине. Обсуждаются вопросы практической применимости.

hybrid quantum-classical heuristicstraveling salesman problemvariational quantum eigensolverquantum annealingгибридная квантово-классическая эвристиказадача коммивояжеравариационный квантовый собственный решательквантовый отжигThe research described in this publication was made possible in part by R&D Support Program for undergraduate and graduate students and postdoctoral researchers of PetrSU, funded by the Government of the Republic of Karelia. Experiments were conducted with the help of high-performance computing cluster of the Center for Collective Use “High-Performance Data Center” of the Karelian Research Center of RAS.The research described in this publication was made possible in part by R&D Support Program for undergraduate and graduate students and postdoctoral researchers of PetrSU, funded by the Government of the Republic of Karelia. Experiments were conducted with the help of high-performance computing cluster of the Center for Collective Use “High-Performance Data Center” of the Karelian Research Center of RAS.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.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).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).Filip, E. & Otakar, M. The travelling salesman problem and its application in logistic practice. 8, 163-173 (Oct. 2011).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.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).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).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.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).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.Cheng, B. et al. Noisy intermediate-scale quantum computers. Frontiers of Physics 18, 21308. doi:10.1007/s11467-022-1249-z (Mar. 2023).Cerezo, M. et al. Variational quantum algorithms. Nature Reviews Physics 3, 625-644. doi:10.1038/ s42254-021-00348-9 (Sept. 2021).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).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).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.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).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).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.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.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).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.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).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.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.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).Nielsen, M. A. & Chuang, I. L. Quantum computation and quantum information 10th anniversary ed. en (Cambridge University Press, Cambridge ; New York, 2010).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.Biamonte, J. Universal variational quantum computation. en. Physical Review A 103, L030401. doi:10.1103/PhysRevA.103.L030401 (Mar. 2021).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).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).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).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).Vesely, M. Finding the Optimal Currency Composition of Foreign Exchange Reserves with a Quantum Computer 2023. arXiv: 2303.01909 [econ.GN].Zhu, L., Liang, S., Yang, C. & Li, X. Optimizing Shot Assignment in Variational Quantum Eigensolver Measurement 2024. arXiv: 2307.06504 [quant-ph].Gantmacher, F. The Theory of Matrices (Chelsea Publishing Company, 1980).De Falco, D., Apolloni, B. & Cesa-Bianchi, N. A numerical implementation of quantum annealing in (July 1988).Su, J. Towards Quantum Computing: Solving Satisfiability Problem by Quantum Annealing (2018).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).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).Estimating Quantum Volume for Advantage https://support.dwavesys.com/hc/en-us/community/posts/360051945133-Estimating-Quantum-Volume-for-Advantage.