Quantum Computers Tackle Complex Drone Delivery Schedules
Summarize this article with:
Scientists are increasingly exploring quantum computing to solve complex logistical challenges, and this research details a novel approach to the drone delivery packing problem. Sara Tarquini from Gran Sasso Science Institute, Matteo Vandelli and Francesco Ferrari from Quantum Computing Solutions, Leonardo S.p.A., alongside Daniele Dragoni working with colleagues at both Quantum Computing Solutions, Leonardo S.p.A. and the Hypercomputing Continuum Unit, Leonardo S.p.A., and Francesco Tudisco from Gran Sasso Science Institute and University of Edinburgh, present a hybrid quantum-classical framework utilising a neutral-atom quantum processing unit. They reformulate the delivery problem as a graph-partitioning task, leveraging the unique capabilities of neutral-atom quantum computers to encode constraints and efficiently explore potential solutions. This work is significant because it demonstrates the potential for quantum algorithms to optimise real-world delivery schedules, offering a pathway towards more efficient and scalable drone delivery networks, and showcases promising results from experiments conducted on up to 100 atoms on the Fresnel QPU. Solving complex delivery problems, such as optimising drone routes, could become far more efficient with this technology. This demonstration offers a practical application for emerging quantum processors, moving beyond theoretical possibilities. Researchers are applying the principles of quantum computing to a practical logistical challenge: optimising drone delivery routes. This work details a hybrid quantum-classical approach to the Drone Delivery Packing Problem, a complex task involving assigning deliveries to drones with limited battery life and time windows. By reformulating the problem as a graph partitioning exercise based on independent sets, the team successfully demonstrated a method for finding efficient delivery schedules. The core innovation lies in using a neutral-atom quantum processing unit (QPU) to generate potential schedules, then refining them with classical algorithms to ensure feasibility given real-world constraints. Neutral atom systems are particularly well-suited to this type of optimisation because of their ability to directly represent the constraints of the problem through the Rydberg blockade mechanism, a phenomenon where the interaction between atoms prevents simultaneous excitation. This allows the QPU to efficiently explore possible solutions, generating sets of deliveries that can be handled by a single drone. However, simply finding time-feasible schedules isn’t enough; battery limitations demand a classical post-processing step to guarantee practicality. Once the quantum computer proposes a set of potential routes, classical algorithms verify and correct them, ensuring each drone’s battery lasts the duration of its assigned deliveries. The research team benchmarked this hybrid workflow using both numerical simulations and experiments on Pasqal’s Fresnel QPU, achieving promising results with configurations of up to 100 atoms. This represents a significant step toward leveraging near-term quantum hardware for solving real-world optimisation problems. Beyond demonstrating feasibility, the study highlights a methodology for decoupling the problem’s constraints, allowing the quantum computer to focus on generating candidate schedules while classical computation handles the practical limitations. This strategy could be extended to other logistical challenges, potentially revolutionizing delivery systems and reducing operational costs. The complexity of the Drone Delivery Packing Problem remains substantial, belonging to the NP-hard class, meaning the computational effort required to find the optimal solution grows exponentially with the number of deliveries. To address this, the researchers recast the problem as a partitioning task, where each partition represents deliveries assigned to a single drone, aiming to minimise the total number of partitions. Achieving optimal solutions requires collecting a sufficient number of samples from the QPU to thoroughly explore the solution space. At the heart of this work is the Rydberg blockade mechanism, which allows for the creation of excited-state configurations representing independent sets of a graph. By arranging atoms spatially to match the desired graph topology, researchers can generate these sets, which correspond to time-feasible delivery schedules. This quantum subroutine is integrated into a broader hybrid workflow. The neutral atom QPU generates independent sets, while a classical algorithm enforces battery-duration constraints, creating a pool of feasible candidate schedules. This integration combines the strengths of both quantum and classical computation.
The team’s analysis included a study of how performance scales with the number of deliveries and the number of samples collected from the QPU. Their tests reached up to 100 atoms on Pasqal’s hardware, demonstrating the potential for scaling this approach to larger, more realistic problem instances. The researchers successfully applied their method to scenarios involving multiple drones, each with a limited battery duration, and deliveries with specific time windows. By leveraging the quantum computer to explore the vast space of possible schedules, they were able to identify near-optimal solutions that minimise the total number of drones required. Quantum partitioning optimises drone delivery routes and battery usage A 100-atom neutral-atom quantum processing unit (QPU) underpinned the methodology used to tackle the Drone Delivery Packing Problem. This work employed a hybrid quantum-classical approach, initially reformulating the delivery optimisation task as a graph-partitioning problem centred on identifying independent sets (ISs). Independent sets represent groupings of deliveries that can be assigned to a single drone without scheduling conflicts. Each identified partition directly corresponds to a feasible delivery schedule for one drone, with the overarching aim being to minimise the total number of partitions. Yet, simply finding time-feasible schedules isn’t enough; battery duration constraints demanded a classical post-processing step to refine the schedules generated by the QPU, ensuring each drone’s assigned deliveries could be completed within its battery capacity. By collecting a sufficient number of samples from the QPU, the solution space could be effectively explored, allowing recovery of optimal or near-optimal delivery schedules. Numerical emulations validated the hybrid workflow before implementation on the physical hardware. The quantum component relies on the Rydberg blockade mechanism, a phenomenon where the excitation of nearby atoms to a Rydberg state prevents the excitation of others. By arranging atoms spatially to reflect the delivery incompatibilities, creating a specific graph topology, the QPU generates configurations representing valid independent sets. These ISs are integrated into a classical algorithm, specifically a graph partitioning workflow, to determine the most efficient drone assignments. This integration allows the strengths of both quantum and classical computation to be combined, addressing a complex logistical challenge. Neutral atoms offered advantages over other quantum computing platforms. Unlike superconducting qubits, neutral atoms exhibit long coherence times, allowing for more complex computations before quantum information is lost. The inherent connectivity of the system, facilitated by the Rydberg interactions, is well-suited to representing the constraints of the delivery problem. This methodology provides a promising pathway for applying near-term quantum hardware to real-world optimisation tasks. Hybrid algorithm performance on the Drone Delivery Packing Problem Across instances ranging from 5 to 50 deliveries, the hybrid quantum-classical workflow achieved an average approximation ratio of 1.16 for the Drone Delivery Packing Problem. This ratio quantifies how closely the number of drones used in the solution approaches the theoretical minimum, with values closer to 1 indicating better performance. Analysis using Pasqal’s emulator revealed a consistently low additive gap, averaging 0.6, between the solution obtained and the optimal solution. This gap represents the additional cost incurred by the heuristic approach, measured in terms of the total delivery time. Performance was not uniform across all instance sizes. For instances with 50 deliveries, the approximation ratio reached 1.8, suggesting a greater deviation from the optimal solution as problem complexity increased. The method consistently outperformed a purely heuristic approach in these larger instances. Numerical experiments, conducted with 500 samples from the quantum processing unit, demonstrated the effectiveness of the post-processing routine in enforcing both time-feasibility and battery constraints. The algorithm identified and removed conflicting nodes, prioritizing those with the highest degree of conflict to rapidly refine the solution. By iteratively addressing violations of the independent set condition and the battery budget, the post-processing routine refined the solutions obtained from the quantum processing unit. The embedding process remains a bottleneck for practical applications, as not all graphs admit a unit disk graph representation. For instances with 50 deliveries, the algorithm required an average of 12 iterations to enforce the independent set condition and 8 iterations to satisfy the battery budget. These numbers demonstrate the efficiency of the greedy post-processing routine. Rydberg blockade enhances solutions for complex drone logistics Scientists are now applying the principles of quantum computing to a surprisingly grounded problem: optimising drone delivery routes. For years, the “last mile” of logistics has presented a persistent challenge, plagued by rising costs and increasing demand. Existing algorithms struggle with the sheer complexity of coordinating multiple drones, each with limited battery life, across a network of delivery points.
This research doesn’t offer a fully quantum solution yet, but instead a clever hybrid approach, blending the strengths of both classical and quantum computation. It’s a pragmatic step, acknowledging the current limitations of quantum hardware while still exploring its potential. Framing the delivery problem as a graph partitioning task, finding independent sets of delivery locations, is where the real ingenuity lies. This allows researchers to exploit the Rydberg blockade mechanism in neutral atom quantum processors, a technique that naturally lends itself to solving such constraints. While previous work has explored quantum solutions for similar optimisation problems, this demonstration extends the scale to configurations involving one hundred atoms, a considerable advance. The need for classical post-processing to account for battery constraints reveals a key hurdle: current quantum processors aren’t yet capable of handling all aspects of the problem independently. Success hinges on collecting enough samples from the quantum processor to accurately map the solution space. This is not merely a technical detail; it speaks to a fundamental trade-off between quantum speedup and the reliability of the hardware. Unlike some more ambitious quantum proposals, this work focuses on a near-term application, but it also highlights the importance of developing better error mitigation techniques. Beyond drone delivery, this hybrid methodology could be adapted to other logistical challenges, such as scheduling and resource allocation. Future efforts will likely concentrate on building larger, more stable quantum processors, reducing the reliance on classical post-processing and unlocking the full potential of quantum optimisation. 👉 More information 🗞 Drone delivery packing problem on a neutral-atom quantum computer 🧠 ArXiv: https://arxiv.org/abs/2602.15487 Tags: