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

arXiv:2407.08767

A Quantum Computing Approach for Multi-robot Coverage Path Planning

Poojith U Rao, Florian Speelman, Balwinder Sodhi, Sachin Kinge

Published Jul 11, 2024• 4 citations
arXivHTMLPDF

Abstract

This paper tackles the multi-vehicle Coverage Path Planning (CPP) problem, crucial for applications like search and rescue or environmental monitoring. Due to its NP-hard nature, finding optimal solutions becomes infeasible with larger problem sizes. This motivates the development of heuristic approaches that enhance efficiency even marginally. We propose a novel approach for exploring paths in a 2D grid, specifically designed for easy integration with the Quantum Alternating Operator Ansatz (QAOA), a powerful quantum heuristic. Our contribution includes: 1) An objective function tailored to solve the multi-vehicle CPP using QAOA. 2) Theoretical proofs guaranteeing the validity of the proposed approach. 3) Efficient construction of QAOA operators for practical implementation. 4) Resource estimation to assess the feasibility of QAOA execution. 5) Performance comparison against established algorithms like the Depth First Search. This work paves the way for leveraging quantum computing in optimizing multi-vehicle path planning, potentially leading to real-world advancements in various applications.

DOI
10.48550/arxiv.2407.08767

Related papers

Collision-free Path Planning in Multi-vehicle Deployments – A Quantum Approach

Poojith U Rao, Balwinder Sodhi

A crucial factor that can severely limit the success and performance of Multi-Robot Systems (MRS) is the possibility of collisions among the robots in a deployment. The MRS deployment in real-world applications has increased almost exponentially in recent years. Thus, finding efficient and fast methods to identify collision-free paths for MRS environments becomes very important.A common objective in such applications is to generate a collision-free path for all the vehicles between two points and minimize the total distance covered while reaching the destination. Since these problems are known to be NP-hard (i.e., no classical algorithm can solve the problem in polynomial time), a heuristics-based approach is usually applied to obtain an acceptable solution.We derive a novel Quantum Alternating Operator Ansatz (QAOA) construction for collision-free path planning in MRS deployment. A heuristic approach such as the QAOA is well suited for combinatorial optimization problems that need to satisfy multiple hard constraints. We also derive the approximate resource estimates in terms of universal quantum gates for our QAOA constructions.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•1 citation

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

Optimal Path-Finding using Quantum Alternating Operator Ansatz with Grover’s Search for Multi-hop Wireless Sensor Networks

Taha Yussuf Raja, Raj Bhattacherjee, Sainath Bitragunta

With the development of wireless sensor networks to combat the problem of reaching places otherwise unreachable for humans, there is a need to keep these remote renewable devices charged. Optimizing the network to utilize the minimum amount of energy becomes paramount. With the advent of powerful Quantum Variational Algorithms suited for the current Noisy Intermediate Scale Quantum (NISQ) era of quantum computers, we can exploit the power of these quantum processors to solve classically hard problems. In this paper, we use the Quantum Alternating Operator Ansatz (QAOA) followed by Grover Searching, which amplifies the possible paths to find the optimal path in a multi-hop network. We perform experiments using quantum simulators to obtain useful insights into the algorithm’s performance with respect to various parameters of interest. Our approach involving QAOA and Grover Searching is a useful benchmark for more general and complex optimization problems in remote renewable wireless networks.

IEEE International Conference on Electronics, Computing and Communication Technologies (CONECCT)•Jul 12, 2024•2 citations

Quantum Algorithm in Path Optimization for Autonomous Underwater Vehicle: Hardware-in-the-Loop experiment

Viet-Dung Do, Xuan-Kien Dang, Žarko Koboević +2 more

Autonomous Underwater Vehicles (AUVs) are often used in survey, exploration, and monitoring missions of the maritime environment. Due to operating in complex environments, planning an optimal path to avoid obstacles is crucial and directly affects operational efficiency and safety. This study proposes a Quantum Algorithm (QA) for planning an AUV optimal path. The QA is based on determining the optimal path by computing the quantum nodes in a Three-Dimensional (3D) space with obstacles. The proposed algorithm computes optimal waypoints, which are assessed by safety requirements established at the stage. The results have a fast-processing time and are effective under complex operating conditions. The feasible results, compared with other pathfinding algorithms, have demonstrated the effectiveness of the proposed solution. In addition, this study develops experiments using a Hardware-in-the-Loop (HIL) model to evaluate the efficiency of the proposed solution under operating conditions that closely resemble actual conditions.

Naše more•Aug 24, 2026•0 citations

Navigating The Future: A Systematic Review on the Role of Quantum Computing in Multi-Robot Systems

Vandana D, Suman .

More and more, multi-robot systems (MRS) are being used for hard tasks like industrial automation, surveillance, and autonomous navigation. Nevertheless, these systems have significant computation difficulties especially in path planning, task distribution and coordination. Quantum computing is capable of computing information based on such concepts as superposition and entanglement. This provides an alternative solution to optimization problems that are more efficient than the conventional methods. A systematic review approach based on PRISMA was used. We used pre-set search terms to look for useful papers in databases including Google Scholar, Scopus, IEEE Xplore, and Web of Science. We found peer-reviewed articles that had come out in the last 10 to 15 years based on some rules for which ones to include and which ones to leave out. A total of thirty papers, mainly focusing on algorithms, applications and constraints were included in qualitative synthesis. The review demonstrated that quantum algorithms, such as the search and QAOA algorithms created by Grover, can be helpful in optimizing the problems of MRS. These methods have the benefits of parallelism and speed. Nevertheless, they are used in simulations only due to the limitations of technology, scaling issues, and integration challenges with real-time robotic system.

International Journal of Artificial Intelligence and Machine Learning•Jan 1, 2026•0 citations

Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes

Emanuele Casciaro, Mario De Simone, Stefano Martina +3 more

With the expansion of complex transport infrastructure, new paths for linking different destinations have emerged, allowing the definition of multiple routes. The introduction of new roads may also lead to disruptions in traffic flow. This problem can be generalized into a special case of VRP, which aims to find the optimal route for a fleet of vehicles within a network of destinations. Finding solutions to this problem requires an exponential number of operations, hindering the ability of exact solvers to deal with large instances, which must therefore be tackled using heuristics, often leading to suboptimal results. Quantum-based algorithms may allow us to find exact solutions in polynomial time with high probability, offering a potential future alternative to classical solvers and in this work, we focus on the QAOA. Our novel contributions are a parameter-initialization strategy that improves the convergence probability and the integration of the subtour constraints directly into the optimization without using additional qubits by employing an approximation of exponential equality constraints. We believe that our results pave the way for effectively solving instances of VRP using quantum-based solutions, leveraging the space-efficient problem encoding and our initialization strategy, which limits the effect of barren-plateau under random parameter initialization.

quant-pharXiv:2610.41120•Nov 2, 2026•0 citations
This paper tackles the multi-vehicle Coverage Path Planning (CPP) problem, crucial for applications like search and rescue or environmental monitoring. Due to its NP-hard nature, finding optimal solutions becomes infeasible with larger problem sizes. This motivates the development of heuristic approaches that enhance efficiency even marginally. We propose a novel approach for exploring paths in a 2D grid, specifically designed for easy integration with the Quantum Alternating Operator Ansatz (QAOA), a powerful quantum heuristic. Our contribution includes: 1) An objective function tailored to solve the multi-vehicle CPP using QAOA. 2) Theoretical proofs guaranteeing the validity of the proposed approach. 3) Efficient construction of QAOA operators for practical implementation. 4) Resource estimation to assess the feasibility of QAOA execution. 5) Performance comparison against established algorithms like the Depth First Search. This work paves the way for leveraging quantum computing in optimizing multi-vehicle path planning, potentially leading to real-world advancements in various applications.
A crucial factor that can severely limit the success and performance of Multi-Robot Systems (MRS) is the possibility of collisions among the robots in a deployment. The MRS deployment in real-world applications has increased almost exponentially in recent years. Thus, finding efficient and fast methods to identify collision-free paths for MRS environments becomes very important.A common objective in such applications is to generate a collision-free path for all the vehicles between two points and minimize the total distance covered while reaching the destination. Since these problems are known to be NP-hard (i.e., no classical algorithm can solve the problem in polynomial time), a heuristics-based approach is usually applied to obtain an acceptable solution.We derive a novel Quantum Alternating Operator Ansatz (QAOA) construction for collision-free path planning in MRS deployment. A heuristic approach such as the QAOA is well suited for combinatorial optimization problems that need to satisfy multiple hard constraints. We also derive the approximate resource estimates in terms of universal quantum gates for our QAOA constructions.
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.
With the development of wireless sensor networks to combat the problem of reaching places otherwise unreachable for humans, there is a need to keep these remote renewable devices charged. Optimizing the network to utilize the minimum amount of energy becomes paramount. With the advent of powerful Quantum Variational Algorithms suited for the current Noisy Intermediate Scale Quantum (NISQ) era of quantum computers, we can exploit the power of these quantum processors to solve classically hard problems. In this paper, we use the Quantum Alternating Operator Ansatz (QAOA) followed by Grover Searching, which amplifies the possible paths to find the optimal path in a multi-hop network. We perform experiments using quantum simulators to obtain useful insights into the algorithm’s performance with respect to various parameters of interest. Our approach involving QAOA and Grover Searching is a useful benchmark for more general and complex optimization problems in remote renewable wireless networks.
Autonomous Underwater Vehicles (AUVs) are often used in survey, exploration, and monitoring missions of the maritime environment. Due to operating in complex environments, planning an optimal path to avoid obstacles is crucial and directly affects operational efficiency and safety. This study proposes a Quantum Algorithm (QA) for planning an AUV optimal path. The QA is based on determining the optimal path by computing the quantum nodes in a Three-Dimensional (3D) space with obstacles. The proposed algorithm computes optimal waypoints, which are assessed by safety requirements established at the stage. The results have a fast-processing time and are effective under complex operating conditions. The feasible results, compared with other pathfinding algorithms, have demonstrated the effectiveness of the proposed solution. In addition, this study develops experiments using a Hardware-in-the-Loop (HIL) model to evaluate the efficiency of the proposed solution under operating conditions that closely resemble actual conditions.
More and more, multi-robot systems (MRS) are being used for hard tasks like industrial automation, surveillance, and autonomous navigation. Nevertheless, these systems have significant computation difficulties especially in path planning, task distribution and coordination. Quantum computing is capable of computing information based on such concepts as superposition and entanglement. This provides an alternative solution to optimization problems that are more efficient than the conventional methods. A systematic review approach based on PRISMA was used. We used pre-set search terms to look for useful papers in databases including Google Scholar, Scopus, IEEE Xplore, and Web of Science. We found peer-reviewed articles that had come out in the last 10 to 15 years based on some rules for which ones to include and which ones to leave out. A total of thirty papers, mainly focusing on algorithms, applications and constraints were included in qualitative synthesis. The review demonstrated that quantum algorithms, such as the search and QAOA algorithms created by Grover, can be helpful in optimizing the problems of MRS. These methods have the benefits of parallelism and speed. Nevertheless, they are used in simulations only due to the limitations of technology, scaling issues, and integration challenges with real-time robotic system.
With the expansion of complex transport infrastructure, new paths for linking different destinations have emerged, allowing the definition of multiple routes. The introduction of new roads may also lead to disruptions in traffic flow. This problem can be generalized into a special case of VRP, which aims to find the optimal route for a fleet of vehicles within a network of destinations. Finding solutions to this problem requires an exponential number of operations, hindering the ability of exact solvers to deal with large instances, which must therefore be tackled using heuristics, often leading to suboptimal results. Quantum-based algorithms may allow us to find exact solutions in polynomial time with high probability, offering a potential future alternative to classical solvers and in this work, we focus on the QAOA. Our novel contributions are a parameter-initialization strategy that improves the convergence probability and the integration of the subtour constraints directly into the optimization without using additional qubits by employing an approximation of exponential equality constraints. We believe that our results pave the way for effectively solving instances of VRP using quantum-based solutions, leveraging the space-efficient problem encoding and our initialization strategy, which limits the effect of barren-plateau under random parameter initialization.