⚛️ quantum physics

QUAV: Quantum-Assisted Path Planning and Optimization for UAV Navigation with Obstacle Avoidance

This paper introduces QUAV, a novel quantum-assisted framework utilizing the Quantum Approximate Optimization Algorithm (QAOA) to enable scalable, real-time UAV path planning with obstacle avoidance, validated through both simulations and real hardware on IBM's ibm_kyiv backend.

Original authors: Nouhaila Innan, Muhammad Kashif, Alberto Marchisio, Yung-Sze Gan, Frederic Barbaresco, Muhammad Shafique

Published 2026-10-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nouhaila Innan, Muhammad Kashif, Alberto Marchisio, Yung-Sze Gan, Frederic Barbaresco, Muhammad Shafique

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a drone trying to fly through a crowded city, weaving between skyscrapers, power lines, and no-fly zones to deliver a package. The computer guiding the drone must constantly calculate the safest, shortest route in real time. As the number of obstacles grows, the math required to find that perfect path becomes overwhelming for traditional computers, which have to check one possibility after another. This is where a new branch of computing enters the picture: quantum computing. Unlike standard computers that process information in a linear sequence of zeros and ones, quantum machines use the strange rules of physics to explore many possibilities at once. While these machines are still in their early stages, researchers are eager to see if they can solve complex navigation problems that stump conventional systems.

In a recent study, a team of researchers from New York University Abu Dhabi and Thales Group introduced a new method called QUAV to tackle this challenge. They built a system that uses a quantum algorithm, specifically one known as the Quantum Approximate Optimization Algorithm, to plan flight paths for drones. The goal was not to replace existing navigation tools immediately, but to test whether a quantum approach could successfully generate safe, efficient routes in environments filled with obstacles. The researchers treated the drone's journey as a puzzle where every possible segment of the flight path was a piece that needed to be fitted together without hitting any barriers.

To make this work, the team first had to translate the real world into a language the quantum computer could understand. They started with standard GPS coordinates for the drone's starting point, destination, and the locations of obstacles like buildings or restricted areas. Because GPS coordinates are curved to match the Earth's surface, the researchers converted them into a flat, grid-like system called Universal Transverse Mercator, which allows for precise distance calculations. They then drew a digital safety buffer around every obstacle, creating a larger "no-go" zone to ensure the drone would never get too close. The space between the start and end points was divided into a grid of potential waypoints, and the researchers mapped out every possible connection between these points to create a vast network of potential routes.

The core of the QUAV system involves breaking the journey into small segments and assigning each segment to a single quantum bit, or qubit. The researchers then used a quantum circuit to explore all possible combinations of these segments simultaneously. Instead of checking routes one by one, the quantum system evaluates the entire landscape of possibilities at once, looking for the combination that minimizes the total distance while strictly avoiding the safety buffers around obstacles. The system assigns a heavy penalty to any route that comes too close to an obstacle, effectively teaching the computer to prioritize safety. Through a process of iterative refinement, the algorithm adjusts its internal settings to find the path with the lowest overall cost, balancing the need for speed with the absolute requirement of not crashing.

The researchers tested this approach in six different scenarios, ranging from open spaces to areas with dense clusters of obstacles. They compared the results against two well-known classical navigation methods: one that guarantees the shortest path but can be very slow to compute, and another that is fast but often produces winding, inefficient routes. In simulations, the quantum-assisted system consistently found paths that were significantly shorter and more direct than the fast classical method. While it did not always match the absolute shortest distance found by the slower, more exhaustive classical method, it came much closer than the fast alternative. In some complex scenarios, the quantum system produced paths that zigzagged slightly more than the ideal straight line, a result of the probabilistic nature of quantum computing, which explores multiple valid options rather than following a single deterministic path.

To prove the system worked beyond computer simulations, the team ran the algorithm on a real quantum processor, specifically the IBM ibm_kyiv machine. This hardware is part of the current generation of quantum computers, which are still prone to errors and noise from their environment. The results showed that even with these imperfections, the system could still converge on a viable solution. The cost of the path fluctuated more than in the simulation due to hardware noise, but the algorithm successfully reduced the cost and found a safe route in every test case. The researchers observed that the system could handle the physical constraints of the machine, such as the limited connections between qubits, by carefully mapping the problem to the available hardware.

The study concludes that this quantum-assisted approach is a viable first step toward using quantum computers for real-world drone navigation. The system demonstrated that it could generate feasible, collision-free trajectories and scale its complexity linearly with the number of path segments, a promising trait for future applications. While the current hardware is not yet powerful enough to outperform the best classical computers in every situation, the research confirms that the fundamental logic works. The findings suggest that as quantum hardware improves and becomes less noisy, these systems could eventually handle the massive, dynamic calculations required for autonomous fleets of drones to navigate the complex skies of tomorrow.

Technical Summary: QUAV – Quantum-Assisted Path Planning and Optimization for UAV Navigation

Problem Statement
The paper addresses the challenge of real-time path planning for Unmanned Aerial Vehicles (UAVs) in complex, dynamic environments characterized by dense obstacles and restricted airspaces. Traditional classical methods, such as graph-search algorithms (A*, Dijkstra) and sampling-based approaches (RRT), often face prohibitive computational loads when scaling to high-dimensional optimization problems. These methods struggle to efficiently evaluate vast numbers of potential routes while simultaneously satisfying collision avoidance constraints, dynamic no-fly zones, and geospatial accuracy requirements. The authors posit that the combinatorial nature of these problems necessitates alternative frameworks capable of exploring solution spaces more efficiently.

Methodology
The authors propose QUAV, a quantum-assisted framework that reformulates UAV path planning as a quantum optimization task using the Quantum Approximate Optimization Algorithm (QAOA). The methodology is structured into four distinct phases:

Spatial Preprocessing: Input data (GPS coordinates for start points, end points, and obstacles) is converted into Universal Transverse Mercator (UTM) coordinates to ensure metric accuracy. Obstacles are modeled as polygons with added safety buffers to guarantee a predefined margin.
Path Finding and Segmentation: The continuous environment is discretized into a structured grid. A graph $G=(V, E)$ is constructed where nodes represent waypoints and edges represent valid connections. Candidate paths are enumerated, and the total path is segmented into discrete edges based on available quantum resources (qubit count).
Cost Assignment: A cost function is assigned to each path segment (edge). This function includes:
- Euclidean distance costs.
- Obstacle penalties (exponentially increasing for segments near the safety buffer).
- A negative bias for the start segment to anchor the path.
- High penalties for segments intersecting obstacles.
Quantum-Assisted Optimization: Each path segment is mapped to a qubit. The QAOA circuit is initialized in an equal superposition state. The algorithm iteratively applies a Cost Hamiltonian ( $H_C$ ) to encode the problem constraints (penalizing collisions and inefficiency) and a Mixer Hamiltonian ( $H_B$ ) to explore the solution space. A classical optimizer (Adam) updates the variational parameters ( $\gamma$ and $\beta$ ) to minimize the expectation value of the cost Hamiltonian.

Key Contributions
The paper outlines four primary contributions:

QAOA-Based Framework: The development of QUAV, which integrates obstacle avoidance constraints directly into the quantum optimization process. The authors note this represents, to their knowledge, one of the first applications of QAOA specifically for drone trajectory optimization.
Theoretical Complexity Analysis: A demonstration that QUAV exhibits linear scaling in circuit depth relative to the number of edges ( $O(S \cdot |E|)$ ) under fixed optimization settings, offering insights into its feasibility compared to classical exponential scaling in certain worst-case scenarios.
Performance Evaluation: Extensive simulations across six scenarios evaluating the framework's ability to generate feasible, collision-free paths under varying environmental constraints.
Real-Hardware Implementation: The execution of QUAV on IBM's ibm_kyiv quantum processing unit (QPU). This validates the framework's robustness against real-world hardware constraints, including noise, decoherence, and qubit connectivity limitations.

Results
The study presents results from simulations and real-hardware execution:

Obstacle Avoidance: In all six tested scenarios, QUAV successfully generated collision-free paths. While some paths exhibited zigzag patterns due to the probabilistic nature of QAOA and the trade-off between safety buffers and path length, the algorithm consistently avoided obstacles.
Path Efficiency: When compared to classical baselines:
- A:* Consistently produced the shortest paths (optimal) but is noted to suffer from scalability issues in high-dimensional spaces.
- RRT: Generated longer, more exploratory paths with higher variance.
- QUAV: Generally outperformed RRT in path length (e.g., Scenario 5: 447.08m vs. 662.88m) but did not always match the absolute optimality of A*. In Scenario 3, QUAV produced a longer path than A* but remained significantly shorter than RRT.
Hardware Performance: Execution on the ibm_kyiv backend demonstrated that while noise causes initial fluctuations in the cost function, the optimizer successfully converges to lower-cost solutions. The results highlight the impact of hardware noise and the necessity of error mitigation strategies.

Significance and Claims
The authors position QUAV as a practical first step toward scalable quantum-assisted path planning rather than a solution that currently outperforms mature classical methods in all metrics.

Feasibility: The primary claim is the validation of the fundamental viability of using QAOA for drone navigation.
Scalability: The framework offers a promising direction for large-scale, dynamic environments as quantum hardware matures, potentially complementing classical approaches.
Future Outlook: The paper suggests that while full quantum advantage remains theoretical, combining QAOA with classical preprocessing or techniques like Grover's algorithm could enhance efficiency. The work emphasizes that as quantum hardware improves, QUAV has the potential to surpass classical approaches in specific complex optimization contexts.

Technical Summary: QUAV – Quantum-Assisted Path Planning and Optimization for UAV Navigation

More like this