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

IEEE International Conference on Electronics, Computing and Communication Technologies (CONECCT)

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

Published Jul 12, 2024• 2 citations
Publisher

Abstract

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.

DOI
10.1109/conecct62155.2024.10677246

Related papers

A Statistical Approach to Analyzing the Quantum Alternating Operator Ansatz with Grover Mixer

Guilherme Adamatti Bridi, Franklin de Lima Marquezino

The Quantum Alternating Operator Ansatz (QAOA) is a promising quantum heuristic to combinatorial optimization, designed for the Noisy Intermediate-Scale Quantum (NISQ) era. A key quantum operator of the algorithm is the mixing, which introduces quantum interference. This work investigates analytically the performance of QAOA with the Grover mixer, a mixing operator inspired by Grover’s algorithm. A critical feature of QAOA with Grover mixer is that it depends only on the probability distribution of the solutions, ignoring the structure of the problem. Due to this, it was conjectured that QAOA with this mixer is bounded to the quadratic speed-up of Grover’s algorithm over the classical brute force on the unstructured search problem. On the other hand, this feature allows the development of a statistical approach, which we explore in this work. For a variant of QAOA called Grover mixing QAOA (GM-QAOA), the analysis leads to an expression for the expectation value whose number of terms depends exponentially on the number of layers of the QAOA. In contrast, for Grover mixer Threshold QAOA (GM-Th-QAOA), a simpler variant that has an intimate relationship with Grover’s algorithm, we obtain a constant-time expression, which allows us to get bounds for different performance metrics, such as the statistical quantities of standard score and quantile. Subsequently, we generalized QAOA with the Grover mixer in a framework we called Grover-based QAOA. By using a contradiction argument with the optimality of Grover’s algorithm, we extend all the bounds of GM-Th-QAOA to the general context of Grover-based QAOA. As a result, we get the main contribution of this work: the proof of the aforementioned conjecture on the performance of QAOA with Grover mixer. We apply our bounds to the class of complete bipartite graphs on the Max-Cut problem, demonstrating that we cannot obtain a polynomial-time algorithm with Grover-based QAOA for these instances, showing that the performance limitation of the Grover mixer can be very severe. Our results suggest that achieving competitive performance with QAOA requires a mixing operator capable of leveraging the structure of combinatorial optimization problems.

•Jul 20, 2025•0 citations

A Quantum Computing Approach for Multi-robot Coverage Path Planning

Poojith U Rao, Florian Speelman, Balwinder Sodhi +1 more

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.

arXiv:2407.08767•Jul 11, 2024•4 citations

Solving the Shortest Path Problem with QAOA

Zhiqiang Fan, Jinchen Xu, Guoqiang Shu +3 more

Graph computation is a core technique for solving realistic problems of graph representations. In solving the shortest path problem (SPP), the current classical methods are encountering a huge performance bottleneck. Attempting to solve this dilemma, we try to solve the SPP with a Quantum Approximate Optimal Algorithm (QAOA)-based quantum method. In this paper, we propose a QAOA-based shortest path algorithm (SPA) by constructing a suitable Hamiltonian quantity and using the idea of variational quantum computing, and verify the algorithm using a quantum simulator and an International Business Machines cloud quantum computer. The proposed algorithm is able to achieve a near-optimal solution with a correct rate that significantly exceeds the invalid solutions, reaching a good preliminary result. Furthermore, the proposed algorithm is expected to achieve a huge advantage over the classical algorithm and the SPA based on Grover’s algorithm with a suitable selection of parameters and number of steps. In addition, the proposed algorithm requires fewer quantum bits than other quantum algorithms, thus promising quantum computing superiority on current noisy intermediate-scale quantum (NISQ) quantum computing devices.

SPIN•Dec 9, 2022•6 citations

Exploring Quantum Computing Algorithms for Optimization Problems

Ananya Krishnan, Edward Tanaka

Optimization problems are pervasive across various domains, including logistics, finance, machine learning, and operations research. Quantum computing has emerged as a promising frontier to address these challenges, offering potential speedups for certain classes of optimization tasks. This paper explores the development and application of quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), Variational Quantum Eigensolver (VQE), and Grover’s search algorithm, tailored for optimization. Recent advancements in hardware, hybrid quantum-classical approaches, and variational techniques have enabled practical implementations on Noisy Intermediate-Scale Quantum (NISQ) devices. Challenges such as noise, scalability, and performance limitations are also discussed. Through theoretical analysis and case studies, this work demonstrates how quantum computing can complement classical methods, paving the way for breakthroughs in solving complex optimization problems.

International Journal on Advanced Computer Theory and Engineering•Apr 15, 2025•1 citation

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

Energy Distribution Optimization Using Variational Quantum Algorithms

Guillermo Rubiños Rodríguez, Mateo Alonso, Xela García‐Santiago +1 more

Quantum computing is emerging as a key tool for enhancing energy management, particularly in areas like resource allocation and renewable energy distribution. Although fault-tolerant quantum computers are still in development, current Noisy Intermediate-Scale Quantum (NISQ) technology shows promise for solving optimization problems using variational quantum algorithms. In this paper, the energy distribution problem for a community with one battery is solved using the Quantum Approximate Optimization Algorithm (QAOA) and the Variational Quantum Eigensolver (VQE) in quantum circuit simulators. This proof of concept provides insights into their potential and limitations for real-world energy applications.

XoveTIC Conference (XoveTIC)•Nov 1, 2024•0 citations
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.
The Quantum Alternating Operator Ansatz (QAOA) is a promising quantum heuristic to combinatorial optimization, designed for the Noisy Intermediate-Scale Quantum (NISQ) era. A key quantum operator of the algorithm is the mixing, which introduces quantum interference. This work investigates analytically the performance of QAOA with the Grover mixer, a mixing operator inspired by Grover’s algorithm. A critical feature of QAOA with Grover mixer is that it depends only on the probability distribution of the solutions, ignoring the structure of the problem. Due to this, it was conjectured that QAOA with this mixer is bounded to the quadratic speed-up of Grover’s algorithm over the classical brute force on the unstructured search problem. On the other hand, this feature allows the development of a statistical approach, which we explore in this work. For a variant of QAOA called Grover mixing QAOA (GM-QAOA), the analysis leads to an expression for the expectation value whose number of terms depends exponentially on the number of layers of the QAOA. In contrast, for Grover mixer Threshold QAOA (GM-Th-QAOA), a simpler variant that has an intimate relationship with Grover’s algorithm, we obtain a constant-time expression, which allows us to get bounds for different performance metrics, such as the statistical quantities of standard score and quantile. Subsequently, we generalized QAOA with the Grover mixer in a framework we called Grover-based QAOA. By using a contradiction argument with the optimality of Grover’s algorithm, we extend all the bounds of GM-Th-QAOA to the general context of Grover-based QAOA. As a result, we get the main contribution of this work: the proof of the aforementioned conjecture on the performance of QAOA with Grover mixer. We apply our bounds to the class of complete bipartite graphs on the Max-Cut problem, demonstrating that we cannot obtain a polynomial-time algorithm with Grover-based QAOA for these instances, showing that the performance limitation of the Grover mixer can be very severe. Our results suggest that achieving competitive performance with QAOA requires a mixing operator capable of leveraging the structure of combinatorial optimization problems.
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.
Graph computation is a core technique for solving realistic problems of graph representations. In solving the shortest path problem (SPP), the current classical methods are encountering a huge performance bottleneck. Attempting to solve this dilemma, we try to solve the SPP with a Quantum Approximate Optimal Algorithm (QAOA)-based quantum method. In this paper, we propose a QAOA-based shortest path algorithm (SPA) by constructing a suitable Hamiltonian quantity and using the idea of variational quantum computing, and verify the algorithm using a quantum simulator and an International Business Machines cloud quantum computer. The proposed algorithm is able to achieve a near-optimal solution with a correct rate that significantly exceeds the invalid solutions, reaching a good preliminary result. Furthermore, the proposed algorithm is expected to achieve a huge advantage over the classical algorithm and the SPA based on Grover’s algorithm with a suitable selection of parameters and number of steps. In addition, the proposed algorithm requires fewer quantum bits than other quantum algorithms, thus promising quantum computing superiority on current noisy intermediate-scale quantum (NISQ) quantum computing devices.
Optimization problems are pervasive across various domains, including logistics, finance, machine learning, and operations research. Quantum computing has emerged as a promising frontier to address these challenges, offering potential speedups for certain classes of optimization tasks. This paper explores the development and application of quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), Variational Quantum Eigensolver (VQE), and Grover’s search algorithm, tailored for optimization. Recent advancements in hardware, hybrid quantum-classical approaches, and variational techniques have enabled practical implementations on Noisy Intermediate-Scale Quantum (NISQ) devices. Challenges such as noise, scalability, and performance limitations are also discussed. Through theoretical analysis and case studies, this work demonstrates how quantum computing can complement classical methods, paving the way for breakthroughs in solving complex optimization problems.
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.
Quantum computing is emerging as a key tool for enhancing energy management, particularly in areas like resource allocation and renewable energy distribution. Although fault-tolerant quantum computers are still in development, current Noisy Intermediate-Scale Quantum (NISQ) technology shows promise for solving optimization problems using variational quantum algorithms. In this paper, the energy distribution problem for a community with one battery is solved using the Quantum Approximate Optimization Algorithm (QAOA) and the Variational Quantum Eigensolver (VQE) in quantum circuit simulators. This proof of concept provides insights into their potential and limitations for real-world energy applications.