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

Обложка

Цитировать

Полный текст

Аннотация

В статье разрабатывается и оценивается гибридный квантово-классический эвристический подход к решению задачи коммивояжера. Этот подход использует исчерпывающий перебор начальных путей и оптимизирует оставшуюся часть маршрута с помощью квантовых вычислений. Для обработки на квантовой машине используется либо вариационный квантовый собственный решатель, либо квантовый отжиг. Представлены результаты оценки предложенного подхода на нескольких наборах данных, включая 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, Российская Федерация

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

  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
Скачать

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».