Quantum-accelerated shortest path search on a graph in unsorted space

Algorithms and data structures are important in information technology (particularly in 6G terahertz wireless communications), logistics, transportation, and route planning in medicine. One of the fundamental algorithms that find application in many practical problems is the shortest path algorithm. The shortest path algorithm is used to find the optimal route between two vertices while minimizing the length or number of intermediate nodes. This problem is one of the 21 NP-hard problems formulated by Richard Karp in 1972. It still poses a serious challenge to science, since there is no polynomial algorithm that can provide an exact solution to this problem. The article considers approaches to solving the problem of finding the shortest path on a graph, and discusses their advantages and disadvantages. Various algorithms, such as the Bellman-Ford algorithm, Dijkstra, and the A* algorithm, are considered; their efficiency and applicability in various situations are analyzed. Issues of optimization of shortest path algorithms are discussed, such as the use of heuristics, graph preprocessing, and other methods that can improve the performance and accuracy of algorithms. The article proposes an optimization of Dijkstra’s algorithm with quantum acceleration. The stability of the quantum algorithm and the magnitude of distortions in a circuit with a different number of qubits are estimated. It is shown that with an increase in the intensity of distortions, the probability of detecting the desired element decreases, and the time spent on its search increases. When using Grover’s algorithm to optimize a path in a quantum network, these interferences cause an increase in the time it takes to find the optimal path and an increase in the probability of choosing an incorrect route. It is shown that an increase in the number of qubits and, accordingly, the number of iterations makes the algorithm more stable. It is demonstrated that the stability of Grover’s algorithm for circuits with a large number of qubits has a similar nature. The work of quantum circuits on 9, 10 and 11 qubits, the difference in the probabilities of correct operation differs by less than 10–3. Thus, from the obtained dependencies, it is possible to predict the nature of such an influence on circuits with an even larger number of qubits, the stability of which cannot be studied due to the insufficient computing power of classical computers. The most efficient way to modify Dijkstra’s algorithm is to replace the priority queue in the classical version of the algorithm with some quantum data structure that finds the minimum element for the next iteration of the algorithm. Despite the fact that quantum search does not provide a potential gain in asymptotics, another quantum modification of Dijkstra’s algorithm can be used. Namely, instead of maintaining and searching for a minimum in the priority queue, use the quantum algorithm immediately to search for a vertex that needs to be added to the shortest path tree, which will additionally acceleration the graph traversal by Dijkstra’s algorithm.

1. Zhan F.B., Noon C.E. Shortest path algorithms: an evaluation using real road networks. Transportation Science, 1998, vol. 32, no. 1, pp. 65–73. doi: 10.1287/trsc.32.1.65

2. Karp R.M. Reducibility among combinatorial problems. 50 Years of Integer Programming 1958–2008, 2010, pp. 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, pp. 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 and Neuroscience, 2022, vol. 2022. pp. 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, pp. 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, vol. 12, pp. 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, vol. 500, pp. 01004. doi: 10.1051/e3sconf/202450001004

8. Bellman R. On a routing problem. Quarterly of Applied Mathematics, 1958, vol. 16, no. 1, pp. 87–90. doi: 10.1090/qam/102435

9. Dijkstra E.W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, vol. 1, no. 1, pp. 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, vol. 4, no. 2, pp. 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, vol. 35, no. 6, pp. 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, vol. 2, no. 9, pp. 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, pp. 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, vol. 79, no. 1, pp. 012322. doi: 10.1103/PhysRevA.79.012322