Исследование квантово-классической эвристики для задачи коммивояжера

Обложка

Цитировать

Полный текст

Аннотация

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

Полный текст

1. Introduction Traveling Salesman Problem (TSP) is a challenging combinatorial problem which is NP-hard [1], that is, the exact optimal solution in general cannot be obtained in polynomial time (w.r.t. the size of input data). The problem implies a search for the shortest possible (cyclic) route that visits (exactly once) a set of cities and returns to the starting city. Since the number of feasible routes increases exponentially with the number of cities [2], it is computationally hard to solve for large TSP instances using traditional algorithms such as brute force and the Held-Karp algorithm [3] (which, however, works well on a small scale). Despite its difficulty, the TSP has many practical applications in various fields such as logistics [4], transportation, and network design. Finding efficient solutions to TSP can help industries optimize delivery routes, reduce costs, and improve overall efficiency. Due to this practical importance, various heuristic and approximation algorithms were introduced to find suboptimal solutions in a reasonable time, such as the nearest-neighbor search [5] or
×

Об авторах

М. А. Макарова

Петрозаводский государственный университет; Институт прикладных математических исследований КарНЦ РАН

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, Петрозаводск, 185910, Российская Федерация; ул. Пушкинская, 11, Петрозаводск, 185910, Российская Федерация

С. В. Федоров

Петрозаводский государственный университет

Email: sergey-fedorov-04@mail.ru
пр. Ленина, д. 33, Петрозаводск, 185910, Российская Федерация

А. В. Титова

Петрозаводский государственный университет

Email: masha.mariam.maltseva@mail.ru
пр. Ленина, д. 33, Петрозаводск, 185910, Российская Федерация

А. А. Хомич

Петрозаводский государственный университет

Email: masha.mariam.maltseva@mail.ru
пр. Ленина, д. 33, Петрозаводск, 185910, Российская Федерация

А. С. Румянцев

Петрозаводский государственный университет; Институт прикладных математических исследований КарНЦ РАН

Автор, ответственный за переписку.
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, Петрозаводск, 185910, Российская Федерация; ул. Пушкинская, 11, Петрозаводск, 185910, Российская Федерация

Список литературы

  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.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Макарова М.А., Федоров С.В., Титова А.В., Хомич А.А., Румянцев А.С., 2025

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution-NonCommercial 4.0 International License.