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:2610.21003

Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing

Silvie Illésová, Vojtěch Novák, Martin Beseda

quant-phcs.ETSubmitted Oct 14, 2026• Announced Oct 16, 2026
arXivHTMLPDF

Abstract

Drone-delivery planning combines routing decisions with operational constraints such as payload capacity and limited onboard energy, resulting in combinatorial optimization problems that can become costly to encode directly in binary form. This work investigates a hybrid quantum--classical approach in which candidate drone missions are generated and evaluated classically before constructing a quadratic unconstrained binary optimization (QUBO) model for mission selection. Payload- and energy-infeasible missions are removed during preprocessing, while the reduced QUBO is solved using exact enumeration, simulated annealing (SA), and the Quantum Approximate Optimization Algorithm (QAOA), with mixed-integer linear programming (MILP) used as a classical reference. Experiments on controlled synthetic delivery instances evaluate solution quality, the effect of preprocessing, and computational scaling. Exact QUBO optimization reproduces the MILP optimum on the evaluated small instances, while SA achieves $100\%$ feasibility with a median optimality gap of $0\%$. Combined payload-and-energy preprocessing reduces the mean number of QUBO variables by $29.60\%$ and quadratic interactions by $49.20\%$, while reducing mean SA runtime by $31.26\%$. In contrast, the evaluated shallow statevector-based QAOA configuration achieves lower feasibility and is restricted to small QUBO instances. These results indicate that, in the considered setting, the main practical benefit of the hybrid architecture comes from classical feasibility preprocessing that reduces the binary search space before QUBO-based optimization.

Related papers

Quantum algorithms for drone mission planning

Ethan G. Davies, Pranav V. Kalidindi

Mission planning often involves optimising the use of ISR (Intelligence, Surveillance and Reconnaissance) assets in order to achieve a set of mission objectives within allowed parameters subject to constraints. The missions of interest here, involve routing multiple UAVs visiting multiple targets, utilising sensors to capture data relating to each target. Finding such solutions is often an NP-Hard problem and cannot be solved efficiently on classical computers. Furthermore, during the mission new constraints and objectives may arise, requiring a new solution to be computed within a short time period. To achieve this we investigate near term quantum algorithms that have the potential to offer speed-ups against current classical methods. We demonstrate how a large family of these problems can be formulated as a Mixed Integer Linear Program (MILP) and then converted to a Quadratic Unconstrained Binary Optimisation (QUBO). The formulation provided is versatile and can be adapted for many different constraints with clear qubit scaling provided. We discuss the results of solving the QUBO formulation using commercial quantum annealers and compare the solutions to current edge classical solvers. We also analyse the results from solving the QUBO using Quantum Approximate Optimisation Algorithms (QAOA) and discuss their results. Finally, we also provide efficient methods to encode to the problem into the Variational Quantum Eigensolver (VQE) formalism, where we have tailored the ansatz to the problem making efficient use of the qubits available.

arXiv:2409.18631•SPIE Quantum Technologies for Defence and Security•Nov 15, 2024•3 citations

Solving Real-World Optimization Problems using Near-Term Quantum Computing with Applications in Vehicle Routing and Drone Delivery

Holliday, James Bradley

Quantum computing (QC) stands at the cusp of revolutionizing computation, yet its near-term potential, constrained by Noisy Intermediate-Scale Quantum (NISQ) devices, remains underexplored. This dissertation investigates how hybrid quantum-classical algorithms can address combinatorial optimization challenges in logistics, focusing on vehicle routing and drone delivery—NP-hard problems with exponential solution spaces that defy classical exhaustive methods. Amidst NISQ limitations like limited qubits and high noise, we confront key challenges: encoding complex constraints, e.g., time windows, battery capacity, into quantum models, balancing quantum and classical components for scalability, and accessing scarce quantum resources. By integrating quantum annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA) with classical heuristics, this work demonstrates QC’s practical utility, advancing both optimization theory and real-world logistics applications. The dissertation unfolds across four core contributions. First, the Hybrid Quantum Tabu Search (HQTS) optimally solves the 50-location Capacitated Vehicle Routing Problem (CVRP), achieving a 4.72% optimality gap. Secondly, we refine HQTS to reach a 2.15% gap with enhanced QA utilization, outperforming prior hybrids on standard datasets. Third, adapting HQTS for the CVRPTWwith D-Wave’s Constrained Quadratic Model solver yields a 3.85% gap on 100-location instances, leveraging a novel heuristic to ensure time-window feasibility where quantum outputs falter. Lastly, QUADRO, a pioneering framework for drone delivery, employs QAOA-driven routing and hybrid scheduling, minimizing transit time and makespan for fleets of 2–11 drones needing fewer than 100 qubits, rivaling classical benchmarks on adapted Augerat datasets. These advances, tested via D-Wave’s Advantage system and Qiskit simulations, showcase hybrid strategies that mitigate NISQ constraints, delivering scalable, feasible solutions to logistics challenges. This work establishes near-term QC’s viability for combinatorial optimization, bridging theoretical promise with practical impact. Synthesizing quantum exploration with classical refinement achieves competitive performance, e.g., matching or surpassing Google ORTools in select CVRPTW cases, while illuminating NISQ limits, such as feasibility degradation beyond small scales. These hybrid strategies deliver scalable, feasible solutions, from a 2.15% optimality gap for CVRP to effective drone fleet management with fewer than 100 qubits, illuminating quantum computing’s potential despite its current constraints. Ultimately, this dissertation positions hybrid QC as a transformative tool for optimization challenges, offering a robust foundation for scaling quantum optimization into operational reality.

Journal of the Arkansas Academy of Science•May 1, 2025•0 citations

Quantum Optimization for Airline Itinerary and Scheduling: A QUBO and QAOA Approach

Vaibhav V. Khedekar

Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.

•Apr 22, 2025•0 citations

QUADRO: A Hybrid Quantum Optimization Framework for Drone Delivery

James B. Holliday, Darren Blount, Hoang Quan Nguyen +2 more

Quantum computing holds transformative potential for optimizing large-scale drone fleet operations, yet its nearterm limitations necessitate hybrid approaches blending classical and quantum techniques. This work introduces Quantum Unmanned Aerial Delivery Routing Optimization (QUADRO), a novel hybrid framework addressing the Energy-Constrained Capacitated Unmanned Aerial Vehicle Routing Problem and the Unmanned Aerial Vehicle Scheduling Problem. By formulating these challenges as Quadratic Unconstrained Binary Optimization problems, QUADRO leverages the Quantum Approximate Optimization Algorithm for routing and scheduling, enhanced by classical heuristics and post-processing. We minimize total transit time in routing, considering payload and battery constraints, and optimize makespan scheduling across various drone fleets. Evaluated on adapted Augerat benchmarks (16-51 nodes), QUADRO competes against classical and prior hybrid methods, achieving scalable solutions with fewer than one hundred qubits. The proposed results underscore the viability of hybrid quantumclassical strategies for real-world drone logistics, paving the way for quantum-enhanced optimization in the Noisy Intermediate Scale Quantum era.

arXiv:2503.24301•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

An Empirical Evaluation of Quantum-Inspired QUBO Methods for Heterogeneous HPC Workflow Mapping and Scheduling

Aasish Kumar Sharma, Christian Boehme, Julian Martin Kunkel

Heterogeneous HPC workflow scheduling under multiple hard constraints poses a challenging combinatorial optimization problem. Classical exact solvers provide optimal solutions but often face scalability limitations, motivating interest in quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) formulations as alternative optimization paradigms. This work presents a systematic and reproducible empirical evaluation of QUBO-based scheduling methods against established classical baselines, including MILP, CP-SAT, GA, and HEFT. We evaluate three QUBO variants, single-run simulated annealing, multi-attempt annealing, and a layered QAOA-inspired schedule, together with hybrid enhancement strategies on both ground-truth validation workflows (3–4 tasks) and synthetic scaling instances (5–20 tasks). All solvers are assessed through a unified evaluation pipeline that explicitly tracks feasibility, makespan, and resource utilization under progressive constraint activation and controlled penalty sweeps. Results show that all approaches recover the expected optimal makespan on validation instances, confirming formulation correctness. However, feasibility degradation emerges for specific QUBO variants as constraint interactions intensify, particularly when communication costs are introduced. Penalty sensitivity analysis reveals a sharp feasibility threshold for QUBO-SA, where insufficient penalties consistently fail and moderate-to-strong penalties restore feasibility. Scaling experiments delineate the regimes in which classical solvers and heuristics remain robust across all tested sizes, while QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks. Overall, the study provides a clear empirical characterization of the reliability boundaries of quantum-inspired QUBO formulations for heterogeneous HPC scheduling and identifies the regimes where classical approaches remain preferable under current formulations and solver capabilities.

ISC High Performance (ISC)•Jun 1, 2026•0 citations

Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms

Gian Giacomo Guerreschi

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.

arXiv:2101.07813•Jan 19, 2021•12 citations
Drone-delivery planning combines routing decisions with operational constraints such as payload capacity and limited onboard energy, resulting in combinatorial optimization problems that can become costly to encode directly in binary form. This work investigates a hybrid quantum--classical approach in which candidate drone missions are generated and evaluated classically before constructing a quadratic unconstrained binary optimization (QUBO) model for mission selection. Payload- and energy-infeasible missions are removed during preprocessing, while the reduced QUBO is solved using exact enumeration, simulated annealing (SA), and the Quantum Approximate Optimization Algorithm (QAOA), with mixed-integer linear programming (MILP) used as a classical reference. Experiments on controlled synthetic delivery instances evaluate solution quality, the effect of preprocessing, and computational scaling. Exact QUBO optimization reproduces the MILP optimum on the evaluated small instances, while SA achieves 100%100\%100% feasibility with a median optimality gap of 0%0\%0%. Combined payload-and-energy preprocessing reduces the mean number of QUBO variables by 29.60%29.60\%29.60% and quadratic interactions by 49.20%49.20\%49.20%, while reducing mean SA runtime by 31.26%31.26\%31.26%. In contrast, the evaluated shallow statevector-based QAOA configuration achieves lower feasibility and is restricted to small QUBO instances. These results indicate that, in the considered setting, the main practical benefit of the hybrid architecture comes from classical feasibility preprocessing that reduces the binary search space before QUBO-based optimization.
Mission planning often involves optimising the use of ISR (Intelligence, Surveillance and Reconnaissance) assets in order to achieve a set of mission objectives within allowed parameters subject to constraints. The missions of interest here, involve routing multiple UAVs visiting multiple targets, utilising sensors to capture data relating to each target. Finding such solutions is often an NP-Hard problem and cannot be solved efficiently on classical computers. Furthermore, during the mission new constraints and objectives may arise, requiring a new solution to be computed within a short time period. To achieve this we investigate near term quantum algorithms that have the potential to offer speed-ups against current classical methods. We demonstrate how a large family of these problems can be formulated as a Mixed Integer Linear Program (MILP) and then converted to a Quadratic Unconstrained Binary Optimisation (QUBO). The formulation provided is versatile and can be adapted for many different constraints with clear qubit scaling provided. We discuss the results of solving the QUBO formulation using commercial quantum annealers and compare the solutions to current edge classical solvers. We also analyse the results from solving the QUBO using Quantum Approximate Optimisation Algorithms (QAOA) and discuss their results. Finally, we also provide efficient methods to encode to the problem into the Variational Quantum Eigensolver (VQE) formalism, where we have tailored the ansatz to the problem making efficient use of the qubits available.
Quantum computing (QC) stands at the cusp of revolutionizing computation, yet its near-term potential, constrained by Noisy Intermediate-Scale Quantum (NISQ) devices, remains underexplored. This dissertation investigates how hybrid quantum-classical algorithms can address combinatorial optimization challenges in logistics, focusing on vehicle routing and drone delivery—NP-hard problems with exponential solution spaces that defy classical exhaustive methods. Amidst NISQ limitations like limited qubits and high noise, we confront key challenges: encoding complex constraints, e.g., time windows, battery capacity, into quantum models, balancing quantum and classical components for scalability, and accessing scarce quantum resources. By integrating quantum annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA) with classical heuristics, this work demonstrates QC’s practical utility, advancing both optimization theory and real-world logistics applications. The dissertation unfolds across four core contributions. First, the Hybrid Quantum Tabu Search (HQTS) optimally solves the 50-location Capacitated Vehicle Routing Problem (CVRP), achieving a 4.72% optimality gap. Secondly, we refine HQTS to reach a 2.15% gap with enhanced QA utilization, outperforming prior hybrids on standard datasets. Third, adapting HQTS for the CVRPTWwith D-Wave’s Constrained Quadratic Model solver yields a 3.85% gap on 100-location instances, leveraging a novel heuristic to ensure time-window feasibility where quantum outputs falter. Lastly, QUADRO, a pioneering framework for drone delivery, employs QAOA-driven routing and hybrid scheduling, minimizing transit time and makespan for fleets of 2–11 drones needing fewer than 100 qubits, rivaling classical benchmarks on adapted Augerat datasets. These advances, tested via D-Wave’s Advantage system and Qiskit simulations, showcase hybrid strategies that mitigate NISQ constraints, delivering scalable, feasible solutions to logistics challenges. This work establishes near-term QC’s viability for combinatorial optimization, bridging theoretical promise with practical impact. Synthesizing quantum exploration with classical refinement achieves competitive performance, e.g., matching or surpassing Google ORTools in select CVRPTW cases, while illuminating NISQ limits, such as feasibility degradation beyond small scales. These hybrid strategies deliver scalable, feasible solutions, from a 2.15% optimality gap for CVRP to effective drone fleet management with fewer than 100 qubits, illuminating quantum computing’s potential despite its current constraints. Ultimately, this dissertation positions hybrid QC as a transformative tool for optimization challenges, offering a robust foundation for scaling quantum optimization into operational reality.
Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.
Quantum computing holds transformative potential for optimizing large-scale drone fleet operations, yet its nearterm limitations necessitate hybrid approaches blending classical and quantum techniques. This work introduces Quantum Unmanned Aerial Delivery Routing Optimization (QUADRO), a novel hybrid framework addressing the Energy-Constrained Capacitated Unmanned Aerial Vehicle Routing Problem and the Unmanned Aerial Vehicle Scheduling Problem. By formulating these challenges as Quadratic Unconstrained Binary Optimization problems, QUADRO leverages the Quantum Approximate Optimization Algorithm for routing and scheduling, enhanced by classical heuristics and post-processing. We minimize total transit time in routing, considering payload and battery constraints, and optimize makespan scheduling across various drone fleets. Evaluated on adapted Augerat benchmarks (16-51 nodes), QUADRO competes against classical and prior hybrid methods, achieving scalable solutions with fewer than one hundred qubits. The proposed results underscore the viability of hybrid quantumclassical strategies for real-world drone logistics, paving the way for quantum-enhanced optimization in the Noisy Intermediate Scale Quantum era.
Heterogeneous HPC workflow scheduling under multiple hard constraints poses a challenging combinatorial optimization problem. Classical exact solvers provide optimal solutions but often face scalability limitations, motivating interest in quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) formulations as alternative optimization paradigms. This work presents a systematic and reproducible empirical evaluation of QUBO-based scheduling methods against established classical baselines, including MILP, CP-SAT, GA, and HEFT. We evaluate three QUBO variants, single-run simulated annealing, multi-attempt annealing, and a layered QAOA-inspired schedule, together with hybrid enhancement strategies on both ground-truth validation workflows (3–4 tasks) and synthetic scaling instances (5–20 tasks). All solvers are assessed through a unified evaluation pipeline that explicitly tracks feasibility, makespan, and resource utilization under progressive constraint activation and controlled penalty sweeps. Results show that all approaches recover the expected optimal makespan on validation instances, confirming formulation correctness. However, feasibility degradation emerges for specific QUBO variants as constraint interactions intensify, particularly when communication costs are introduced. Penalty sensitivity analysis reveals a sharp feasibility threshold for QUBO-SA, where insufficient penalties consistently fail and moderate-to-strong penalties restore feasibility. Scaling experiments delineate the regimes in which classical solvers and heuristics remain robust across all tested sizes, while QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks. Overall, the study provides a clear empirical characterization of the reliability boundaries of quantum-inspired QUBO formulations for heterogeneous HPC scheduling and identifies the regimes where classical approaches remain preferable under current formulations and solver capabilities.
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.