Исследование квантово-классической эвристики для задачи коммивояжера
- Авторы: Макарова М.А.1,2, Федоров С.В.1, Титова А.В.1, Хомич А.А.1, Румянцев А.С.1,2
-
Учреждения:
- Петрозаводский государственный университет
- Институт прикладных математических исследований КарНЦ РАН
- Выпуск: Том 33, № 2 (2025)
- Страницы: 199-213
- Раздел: Математическое моделирование
- URL: https://journal-vniispk.ru/2658-4670/article/view/316800
- DOI: https://doi.org/10.22363/2658-4670-2025-33-2-199-213
- EDN: https://elibrary.ru/BOMUBB
- ID: 316800
Цитировать
Полный текст
Аннотация
В статье разрабатывается и оценивается гибридный квантово-классический эвристический подход к решению задачи коммивояжера. Этот подход использует исчерпывающий перебор начальных путей и оптимизирует оставшуюся часть маршрута с помощью квантовых вычислений. Для обработки на квантовой машине используется либо вариационный квантовый собственный решатель, либо квантовый отжиг. Представлены результаты оценки предложенного подхода на нескольких наборах данных, включая TSPLIB и туристические данные для Петрозаводска и Республики Карелия, как в режиме имитации, так и на соответствующей квантовой машине. Обсуждаются вопросы практической применимости.
Об авторах
М. А. Макарова
Петрозаводский государственный университет; Институт прикладных математических исследований КарНЦ РАН
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
Bachelor’s degree student пр. Ленина, д. 33, Петрозаводск, 185910, Российская Федерация
А. В. Титова
Петрозаводский государственный университет
Email: masha.mariam.maltseva@mail.ru
Bachelor’s degree student пр. Ленина, д. 33, Петрозаводск, 185910, Российская Федерация
А. А. Хомич
Петрозаводский государственный университет
Email: masha.mariam.maltseva@mail.ru
Bachelor’s degree student пр. Ленина, д. 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, Российская ФедерацияСписок литературы
- 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.
Дополнительные файлы
