Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Computing, Communication and Automation

Quantum vs Classical Pathfinding: Optimizing Time and Distance with QAOA, Grover’s, and Modified Dijkstra

Shaurya Pandey, Aditya Raj Thakur

Published Nov 28, 2025• 0 citations
Publisher
DOI
10.1109/iccca66364.2025.11325258

Related papers

Quantum vs. Classical Routing: A Hardware-Aware Study of QAOA and Dijkstra with Constrained Shortest Path and Constraint-Preserving Mixers

Quang Bui

•Jan 1, 2026•0 citations

The Shortest Pathfinding by a Quantum Walk

Leo Matsuoka, Kenta Yuki, Hynek Lavička +1 more

The Japan Society of Applied Physics•Jul 6, 2021•0 citations

HYBRID QUANTUM ALGORITHMS FOR AUTONOMOUS VEHICLE NAVIGATION: DIRECTED PATH PLANNING WITH GROVER-QAOA

IDRIS KAGAN DEMIR, Seda Nur Gungor, Mehmet Karaköse

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.

Quantum Journal of Engineering Science and Technology•Mar 31, 2026•1 citation

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

Паскаль Мишелевич Хури, Алина Дмитриевна Клишева, Petr Demchenko +3 more

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.

Scientific and technical journal of information technologies mechanics and optics•Jul 9, 2026•0 citations

Quantum Maze Solver: A Hybrid Quantum-Classical Approach for Pathfinding

Prashant Verma, Dinesh Kumar Vishwakarma

Lecture notes in networks and systems•Jan 1, 2026•0 citations

Parameter Optimization and Noise Resilience Analysis for QAOA on NISQ Devices: A Comprehensive Study from 3 to 40 Qubits

Matthias Christian Wurm

Abstract Quantum algorithms on Noisy Intermediate-Scale Quantum (NISQ) devices require optimization strategies matched to circuit structure. We present two complementary approaches: VERMICULAR, achieving 93.0% success rates for Grover’s algorithm through strategic dynamical decoupling (DD) placement (vs. 18.3% baseline), and systematic QAOA parameter optimization achieving 94.5% approximation ratios for MaxCut (vs. 39.6% with theoretical parameters). Through >15,000 circuit executions across IQM Garnet, Rigetti Ankaa-3, and IonQ Forte-1 (total cost: €70), we demonstrate that circuit structure determines which strategy succeeds: DD helps algorithms with substantial idle time (Grover: 34% idle → 5× improvement) but degrades continuously-active circuits (QAOA: 2.4% idle → 50% degradation with DD). We systematically characterize algorithm noise resilience via critical noise thresholds (σc), finding Bell states achieve 4× higher σc than product states (0.200 vs 0.050, p < 0.001) and that σc predicts hardware performance (r = 0.94, p = 0.006). QAOA scaling studies (3-40 qubits) reveal exponential decay with 56% plateau beyond 20 qubits. Simulator-optimized parameters transfer effectively to hardware (85-98% efficiency), but hardware-to-hardware transfer requires architecture-specific tuning. We provide SigmaCSuite, an open-source validation framework, and complete experimental protocols. These findings establish that optimization strategy must match circuit structure: idle-time protection for search algorithms, parameter tuning for variational algorithms—achieving 2.5-5× improvements through targeted approaches.

•Dec 3, 2025•1 citation
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.
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.
Abstract Quantum algorithms on Noisy Intermediate-Scale Quantum (NISQ) devices require optimization strategies matched to circuit structure. We present two complementary approaches: VERMICULAR, achieving 93.0% success rates for Grover’s algorithm through strategic dynamical decoupling (DD) placement (vs. 18.3% baseline), and systematic QAOA parameter optimization achieving 94.5% approximation ratios for MaxCut (vs. 39.6% with theoretical parameters). Through >15,000 circuit executions across IQM Garnet, Rigetti Ankaa-3, and IonQ Forte-1 (total cost: €70), we demonstrate that circuit structure determines which strategy succeeds: DD helps algorithms with substantial idle time (Grover: 34% idle → 5× improvement) but degrades continuously-active circuits (QAOA: 2.4% idle → 50% degradation with DD). We systematically characterize algorithm noise resilience via critical noise thresholds (σc), finding Bell states achieve 4× higher σc than product states (0.200 vs 0.050, p < 0.001) and that σc predicts hardware performance (r = 0.94, p = 0.006). QAOA scaling studies (3-40 qubits) reveal exponential decay with 56% plateau beyond 20 qubits. Simulator-optimized parameters transfer effectively to hardware (85-98% efficiency), but hardware-to-hardware transfer requires architecture-specific tuning. We provide SigmaCSuite, an open-source validation framework, and complete experimental protocols. These findings establish that optimization strategy must match circuit structure: idle-time protection for search algorithms, parameter tuning for variational algorithms—achieving 2.5-5× improvements through targeted approaches.