HYBRID QUANTUM ALGORITHMS FOR AUTONOMOUS VEHICLE NAVIGATION: DIRECTED PATH PLANNING WITH GROVER-QAOA
DOI:
https://doi.org/10.55197/qjoest.v7i1.278Keywords:
quantum computing, automated navigation, quantum optimization, algorithmsAbstract
Path planning in complex and obstacle-constrained environments remains a challenging combinatorial optimization problem due to the exponential growth of the solution space and the limitations of classical algorithms in dynamic decision-making scenarios. Traditional approaches such as Dijkstra or A* may experience high computational costs and susceptibility to local optima when dealing with large-scale directed graphs containing obstacles. This study proposes a hybrid quantum computing approach that integrates the Grover Search Algorithm and the Quantum Approximate Optimization Algorithm (QAOA) to address optimal path planning on obstacle-oriented directed graphs. The Grover algorithm is first employed as an oracle-based filtering mechanism to detect and eliminate obstacle-containing edges, thereby generating a valid subgraph of feasible paths. Following this preprocessing step, QAOA is applied to the filtered graph within a nonlinear optimization framework to determine the minimum-cost path between source and destination nodes. The optimization model represents the graph as G=(V,E), where binary decision variables indicate whether an edge is included in the selected route while satisfying flow conservation constraints. By narrowing the solution space through Grover-based obstacle detection and performing optimization only on valid edges, the proposed method significantly reduces computational complexity compared to conventional approaches. Experimental analysis demonstrates that the hybrid quantum model effectively identifies optimal routes and adapts to different obstacle configurations while maintaining efficient convergence behavior. The results highlight the potential of integrating quantum search and quantum optimization techniques for solving combinatorial graph problems. This work contributes to the growing body of research on quantum-assisted optimization and demonstrates the feasibility of applying hybrid quantum algorithms to directed path planning problems relevant to autonomous navigation systems.
References
[1] Arora, S., Barak, B. (2009): Computational complexity: a modern approach. – Cambridge University Press 594p.
[2] Bar, N.F., Yetíş, H., Özbey, N., Karaköse, M. (2024): Quantum computing based collaborative optimum mission allocation approach for heterogeneous multi unmanned vehicles. – IEEE Access 12: 169069-169078.
[3] Bharti, K., Cervera-Lierta, A., Kyaw, T.H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J.S., Menke, T., Mok, W.K. (2022): Noisy intermediate-scale quantum algorithms. – Reviews of Modern Physics 94(1): 91p.
[4] Boyer, M., Brassard, G., Høyer, P., Tapp, A. (1998): Tight bounds on quantum searching. – Fortschritte der Physik: Progress of Physics 46(4‐5): 493-505.
[5] Brassard, G., Hoyer, P., Mosca, M., Tapp, A. (2000): Quantum amplitude amplification and estimation. – AMS Contemporary Mathematics 305: 53-74.
[6] Campbell, E., Khurana, A., Montanaro, A. (2019): Applying quantum algorithms to constraint satisfaction problems. – Quantum 3: 30p.
[7] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C. (2022): Introduction to algorithms. – MIT Press 1312p.
[8] Das, A., Chakrabarti, B.K. (Eds.) (2005): Quantum annealing and related optimization methods. – Springer Science & Business Media 679: 384p.
[9] Farhi, E., Goldstone, J., Gutmann, S. (2014): A quantum approximate optimization algorithm. – ArXiv Preprint ArXiv:1411.4028 16p.
[10] Fitzek, D., Ghandriz, T., Laine, L., Granath, M., Kockum, A.F. (2024): Applying quantum approximate optimization to the heterogeneous vehicle routing problem. – Scientific Reports 14(1): 18p.
[11] Grover, L.K. (1996): A fast quantum mechanical algorithm for database search. – In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing 8p.
[12] Gungor, S.N., Karakose, M. (2025): A Quantum Computing Based Solution Approach for NP-Complete Problems. – In 2025 29th International Conference on Information Technology (IT), IEEE 4p.
[13] Korte, B., Vygen, J. (2008): Combinatorial optimization: theory and algorithms. – Berlin, Heidelberg: Springer Berlin Heidelberg 664p.
[14] Montanaro, A. (2016): Quantum algorithms: an overview. – NPJ Quantum Information 2(1): 1-8.
[15] Papadimitriou, C.H., Steiglitz, K. (1998): Combinatorial optimization: algorithms and complexity. – Courier Corporation 496p.
[16] Pellow-Jarman, A., McFarthing, S., Sinayskiy, I., Park, D.K., Pillay, A., Petruccione, F. (2024): The effect of classical optimizers and Ansatz depth on QAOA performance in noisy devices. – Scientific Reports 14(1): 11p.
[17] Preskill, J. (2018): Quantum computing in the NISQ era and beyond. – Quantum 2: 20p.
[18] Wang, Z., Hadfield, S., Jiang, Z., Rieffel, E.G. (2018): Quantum approximate optimization algorithm for MaxCut: A fermionic view. – Physical Review A 97(2): 12p.
[19] Yetis, H., Karakose, M. (2021): Collaborative truck-drone routing optimization using quantum-inspired genetic algorithms. – In 2021 25th International Conference on Information Technology (IT), IEEE 4p.
[20] Zhou, L., Wang, S.T., Choi, S., Pichler, H., Lukin, M.D. (2020): Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. – Physical Review X 10(2): 23p.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 IDRIS KAGAN DEMIR, SEDANUR GÜNGÖR, MEHMET KARAKOSE
This work is licensed under a Creative Commons Attribution 4.0 International License.
