Поиск с квантовым ускорением кратчайшего пути на графе в несортированном пространстве

Введение. Алгоритмы и структуры данных важны в информационных технологиях (в частности, в терагерцовых беспроводных коммуникациях 6G), логистике, транспорте и планировании маршрутов в медицине. Одним из основополагающих алгоритмов, который находит применение во многих практических задачах, является алгоритм поиска кратчайшего пути на графе. Он используется для нахождения оптимального маршрута между двумя вершинами, минимизируя длину или количество промежуточных узлов. Эта задача относится к 21 NP трудной проблеме, сформулированной Ричардом Карпом в 1972 году. Она по-прежнему представляет собой серьезный вызов для науки, поскольку не существует полиномиального алгоритма, способного обеспечить точное ее решение. Метод. Рассмотрены подходы к решению задачи поиска кратчайшего пути на графе, а также обсуждаются их преимущества и недостатки. Изучены алгоритмы, такие как Беллмана–Форда, Дейкстры и А*; проанализированы их эффективность и применимость в различных ситуациях. Обсуждаются вопросы оптимизации алгоритмов поиска кратчайшего пути, такие как использование эвристик, предварительная обработка графа и другие методы, которые могут улучшить производительность и точность алгоритмов. Основные результаты. Предложена оптимизация алгоритма Дейкстры с квантовым ускорением. Проведена оценка устойчивости квантового алгоритма и величины искажений в схеме с различным количеством кубитов. Показано, что с возрастанием интенсивности искажений вероятность обнаружения искомого элемента уменьшается, а время, затрачиваемое на его поиск, увеличивается. При применении алгоритма Гровера для оптимизации пути в квантовой сети эти помехи становятся причиной увеличения времени поиска оптимального пути и повышения вероятности выбора неверного маршрута. Показано, что увеличение количества кубитов и, соответственно, количества итераций делает алгоритм более устойчивым. Продемонстрировано, что устойчивость алгоритма Гровера для схем с большим количеством кубитов имеет схожий характер. Работы квантовых схем на 9, 10 и 11 кубитах различие в значениях вероятностей верного срабатывания отличается менее, чем на 10–3. Таким образом, из полученных зависимостей можно предсказать характер такого влияния на схемы с еще большим числом кубитов, устойчивость которых не может быть исследована вследствие недостаточной вычислительной мощности классических компьютеров. Обсуждение. Наиболее эффективным способом модификации алгоритма Дейкстры является замена очереди с приоритетом в классической версии алгоритма на некоторую квантовую структуру данных, находящую минимальный элемент для следующей итерации алгоритма. Несмотря на то, что квантовый поиск не дает потенциального прироста в асимптотике, можно использовать иную квантовую модификацию алгоритма Дейкстры. А именно, вместо поддержания и поиска минимума в очереди с приоритетом применить квантовый алгоритм сразу для поиска вершины, которую необходимо добавить в дерево кратчайших путей, что дополнительно даст ускорение обхода графа алгоритмом Дейкстры.

1. Zhan F.B., Noon C.E. Shortest path algorithms: an evaluation using real road networks // Transportation Science. 1998. V. 32. N 1. P. 6573. doi: 10.1287/trsc.32.1.65

2. Karp R.M. Reducibility among combinatorial problems // 50 Years of Integer Programming 1958–2008. 2010. P. 219–241. doi: 10.1007/978-3-540-68279-0_8

3. Haeupler B., Hladík R., Rozhoň V., Tarjan R.E., Tetĕk J. Universal optimality of Dijkstra via beyond-worst-case heaps // Proc. of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). 2024. P. 2099–2130. doi: 10.1109/focs61266.2024.00125

4. Wei Z. High performance computing simulation of intelligent logistics management based on shortest path algorithm // Computational Intelligence and Neuroscience. 2022. V. 2022. P. 7930553. doi: 10.1155/2022/7930553

5. Chen R. Dijkstra’s shortest path algorithm and its application on bus routing // Advances in Economics, Business and Management Research. 2022. P. 321–325. doi: 10.2991/aebmr.k.220502.058

6. Warrier A., Aljaburi L., Whitworth H., Al-Rubaye S, Tsourdos A. Future 6G communications powering vertical handover in nonterrestrial networks // IEEE Access. 2024. V. 12. P. 33016–33034. doi: 10.1109/ACCESS.2024.3371906

7. Kurniawan F., Widyanto R.A., Sukmasetya P. Dijkstra algorithm implementation to determine the shortest route to hospital: a case study in Magelang district Indonesia // E3S Web of Conferences. 2024. V. 500. P. 01004. doi: 10.1051/e3sconf/202450001004

8. Bellman R. On a routing problem // Quarterly of Applied Mathematics. 1958. V. 16. № 1. P. 87–90. doi: 10.1090/qam/102435

9. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik. 1959. V. 1. N 1. P. 269–271. doi: 10.1007/BF01386390

10. Hart P.E., Nilsson N.J., Raphael B. A formal basis for the heuristic determination of minimum cost paths // IEEE transactions on Systems Science and Cybernetics. 1968. V. 4. N 2. P. 100–107. doi: 10.1109/TSSC.1968.300136

11. Dürr C., Heiligman M., Høyer P., Mhalla M. Quantum query complexity of some graph problems // SIAM Journal on Computing. 2006. V. 35. N 6. P. 1310–1328. doi: 10.1137/050644719

12. Ray P. Quantum simulation of Dijkstra’s algorithm // International Journal of Advance Research in Computer Science and Management Studies. 2014. V. 2. N 9. P. 30–43.

13. Grover L.K. A fast quantum mechanical algorithm for database search // Proc. of the 28th Annual ACM Symposium on Theory of Computing (STOC). 1996. P. 212–221. doi: 10.1145/237814.237866

14. Nielsen M.A., Chuang I.L. Quantum Computation and Quantum Information. Cambridge University Press, 2010. 702 p. doi: 10.1017/CBO9780511976667

15. Nakahara M., Ohmi T. Quantum Computing: from Linear Algebra to Physical Realizations. CRC Press, 2008. 438 p.

16. Linington I.E., Ivanov P.A., Vitanov N.V. Quantum search in a nonclassical database of trapped ions // Physical Review A. 2009. V. 79. N 1. P. 012322. doi: 10.1103/PhysRevA.79.012322