Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing

arXiv:2610.21003 · quant-ph, cs.ET · Submitted 2026-10-14 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing".

Mira: The gist:

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So we're looking at this paper today, "Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing." The main idea here is taking a really big optimization problem for drone deliveries and breaking it down. Mira Right, like they are not trying to solve the whole delivery puzzle at once with one massive quantum model. Kai Exactly. They're generating candidate drone missions first using classical methods and checking if those missions can actually happen, meaning they discard the impossible ones before making a single QUBO.

Lev: And that separation is key for me because when you run anything on real hardware, the overhead has to be manageable, so reducing the input size upfront makes a huge difference in terms of what's even possible to test. Kai Exactly. It’s like cleaning up the mess before you try to build the whole machine.

Mira: So, they are tackling that combinatorial explosion by using classical checks for physical constraints like payload and energy early on, which then feeds into a smaller quadratic unconstrained binary optimization problem later on. Lev I mean, it's a clever way to manage the complexity of those route decisions without having to encode everything directly into the QUBO structure immediately.

Kai: It sounds like they are focusing on how this preprocessing stage actually impacts the final QUBO formulation, which is what we need for the actual quantum part. Mira That's right. They want to see if this classical filtering actually reduces both the number of variables and how connected those variables are in the final model.

Lev: If you cut down on the interaction count in that quadratic problem, it makes running any solver, whether it's classical or quantum, much more feasible on current systems.

The paper's summary: Kai: Okay, so what they actually did in the "Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing" paper is that they introduced this hybrid quantum-classical approach where you generate candidate drone missions classically first, then evaluate them for feasibility against payload and energy limits. Mira They are treating the mission selection part as a separate step from the strict physical constraints, which is what they call separating deterministic feasibility checks from the combinatorial selection problem. Kai Right. They test three different ways of doing this preprocessing: no filtering, just payload filtering, or combining both payload and energy filters together to keep only feasible missions.

Lev: I'm interested in the way they frame it because usually, you have to solve all those constraints simultaneously in the optimization model, but here they are systematically removing the infeasible routes before the main binary problem even starts. Mira The motivation is that this decomposition has a potential to reduce both the dimensionality and the connectivity of that resulting optimization problem while still keeping all the relevant feasible solutions available.

Kai: So, they aren't trying to solve the entire global routing problem classically, but rather just removing individual missions that are physically impossible to execute on a drone before feeding them into a QUBO solver. Lev That’s exactly right. It’s about making sure the set of candidate missions you feed into the quantum step is as small and useful as possible for the QUBO formulation.

Mira: They also set up three research questions to guide their experiments: RQ1 looks at how well a QUBO solver can actually handle energy-constrained problems compared to classical optimization, RQ2 checks how much classical preprocessing affects the size and solution quality of the resulting QUBO, and RQ3 looks at how the computational behavior changes as both the delivery instance and that resulting QUBO grow. Kai It sounds like they are systematically checking if this approach actually delivers on its promise across different scales of problem size.

The paper's improvements: Kai: Looking at the improvements suggested by this paper, they are really focusing on how this classical preprocessing stage specifically impacts the resulting QUBO formulation itself. Mira They point out that classical preprocessing can reduce both nQUBO, which is the number of binary variables—equal to the number of retained candidate missions—and also the interaction count in the quadratic matrix Q by removing those infeasible missions before it's even assembled. Lev That reduction in interaction count is a big deal because if you have fewer connections between your binary variables, it makes solving that matrix much faster, regardless of whether you use a classical or quantum method.

Kai: So, the core improvement is that by removing bad routes early, they are essentially pruning the search space before the complex combinatorial selection problem gets too big for any solver. Mira They argue this decomposition has the potential to make that reduced candidate set much more manageable for the QUBO solver than if you tried to encode everything from scratch.

Lev: If we think about running this on actual hardware, having a smaller QUBO instance means lower circuit depth or fewer required qubits, which directly translates to better fidelity and less error accumulation when we run the algorithm. Kai That makes sense. It’s not just theoretical reduction in size; it has direct physical implications for how robust the computation ends up being.

Mira: The experiments they set up to answer their research questions are designed specifically to show how much better this is compared to just starting with a full, unfiltered QUBO model and what the trade-offs are with those classical preprocessing configurations.

Conclusion: Kai: So, wrapping up the "Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing" paper, the main point is that hybrid quantum-classical decomposition is a viable way to tackle complex drone delivery planning problems by using classical checks to filter out physically impossible missions before feeding them into a QUBO solver. Mira They are showing that this approach has the potential to reduce both the dimensionality and the connectivity of those resulting optimization problems while still keeping all the relevant feasible solutions available in that reduced set. Lev From my side, it’s clear that by removing those infeasible routes early, you’re making running any solver on real hardware much more feasible because you get a smaller QUBO instance to work with.

Kai: It really shows how separating the deterministic feasibility checks from the combinatorial selection problem can lead to a formulation that is more tractable for optimization techniques like QAOA or even classical solvers. Mira They’ve demonstrated how this hybrid approach works across different filtering configurations, showing that it’s a systematic way to reduce complexity as the problem grows.

Lev: The limitation they mention is that while this preprocessing helps, the overall method still relies on being able to generate those candidate missions classically in a reasonable time before you even get to the QUBO part. Kai So, it’s not a total solution where everything is purely quantum or purely classical; it still has that initial classical hurdle of generating and checking all those potential routes.

Mira: And they noted that the effectiveness of this reduction depends heavily on how you configure that classical preprocessing stage, so you have to choose the right filter—whether it’s just payload, or combining payload and energy constraints. Kai That means for a practitioner, the choice of pre-filtering strategy is as important as the quantum solver itself when trying to get a good result.

Lev: So, in summary, they found that classical feasibility preprocessing can significantly reduce the size of the QUBO formulation by pruning infeasible routes before optimization begins.

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

Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VSB – Technical University of Ostrava · IT4Innovations National Supercomputing Center, VSB – Technical University of Ostrava · Department of Informatics and Statistics, Marine Research Institute, Klaipeda University · Gran Sasso Science Institute

quant-ph, cs.ET

Submitted: 2026-10-14

Updated: 2026-10-14

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 84/100

The gist: The gist: This work investigates a hybrid quantum–classical approach in which candidate drone missions are generated and evaluated classically before constructing a quadratic unconstrained binary

Key concepts

Hybrid Quantum–Classical Approach: This method combines classical computation with quantum optimization techniques. Classical methods handle initial mission generation and feasibility checks, while quantum methods (like QUBO solvers) are then applied to the reduced set of feasible missions to find the best delivery plan.
Classical Feasibility Preprocessing for Mission Generation: Before building a complex optimization model, classical algorithms check every potential drone route. They discard any mission that exceeds the drone's payload capacity or energy limits. This step removes physically impossible routes from consideration early on.
Quadratic Unconstrained Binary Optimization (QUBO): QUBO is a mathematical formulation used to solve optimization problems by minimizing a quadratic objective function subject to binary constraints. In this context, it is used to select the best set of feasible drone missions from the preprocessed candidate list.
Problem Dimensionality Reduction: The classical preprocessing stage reduces the number of candidate missions ($n_{QUBO}$) and their interactions by eliminating infeasible routes. This reduction in variables and connections makes the subsequent QUBO model smaller, leading to a lower computational cost for the final quantum solver.

Terminology

Combinatorial Optimization — 1× in this paper · explained in 2 episodes
Hybrid Architecture — 1× in this paper · explained in 2 episodes
Quantum Approximate Optimization Algorithm — 1× in this paper

Summary

The gist: 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.

Problem Context

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 The paper discusses how UAVs are increasingly considered for lastmile delivery because they can provide direct point-to-point transport, reduce dependence on road infrastructure, and support rapid delivery in areas where conventional ground transportation may be less efficient Practical drone-delivery planning requires the simultaneous consideration of several operational constraints, including payload capacity, limited onboard energy, route length, fleet size, and the assignment of customer requests to feasible drone missions Together, these factors lead to combinatorial optimization problems whose complexity can increase rapidly with the number of customers and candidate routes Classical approaches to drone-delivery optimization commonly rely on mixedinteger linear programming (MILP) [12, 53, 49], vehicle-routing formulations [18, 16, 52], decomposition methods [38, 56], and metaheuristic optimization [24, 23, 1] One widely used formulation in this context is quadratic unconstrained binary optimization (QUBO) A direct encoding of a complete drone-delivery problem as a QUBO [22], however, can become large quickly For this reason, this work investigates a hybrid quantum–classical decomposition rather than encoding the complete drone-delivery problem directly into a single QUBO In the proposed approach, classical preprocessing is used to generate candidate drone missions and evaluate their operational feasibility Routes that violate payload or energy constraints are removed before the binary optimization model is constructed The motivation for this architecture is to separate deterministic feasibility checks from the combinatorial selection problem Payload and energy constraints can be evaluated efficiently in a classical preprocessing stage, while the reduced candidate set is subsequently passed to a QUBO solver This decomposition has the potential to reduce both the dimensionality and the connectivity of the resulting optimization problem while preserving the relevant feasible solution space

How it works

The proposed method follows a workflow summarized as instance generation → candidate missions → feasibility preprocessing → QUBO → solver → decoded delivery plan Candidate missions are first generated classically from subsets and permutations of the customer set Each candidate mission is evaluated in terms of route distance, carried payload, and energy consumption Depending on the preprocessing configuration used in the experiments, missions that violate payload or energy limits are discarded The remaining mission-selection problem is then transformed into a QUBO and solved using either classical or quantum optimization methods

Classical Preprocessing

The classical preprocessing stage evaluates the physical feasibility of every generated mission before the QUBO is constructed Three preprocessing configurations are considered in the experimental evaluation: no filtering, payload filtering, and combined payload-and-energy filtering With payload filtering, a mission r is retained only if Wr ≤ Wmax This eliminates missions whose combined package weight exceeds the carrying capacity of the drone With combined payload-and-energy filtering, the payload condition in Eq. (26) is applied together with Er ≤ Emax The retained mission set is therefore Rfeasible =

r ∈ R Wr ≤ Wmax ∧ Er ≤ Emax The purpose of this stage is not to solve the global routing problem classically, but to remove individual missions that cannot appear in any operationally valid solution

QUBO Formulation and Complexity Reduction

After preprocessing, one binary variable xr is introduced for every retained candidate mission r The number of QUBO variables is equal to the number of retained candidate missions, nQUBO = |R| while the number of quadratic interactions depends on how many candidate missions overlap in the customers they contain Classical preprocessing can therefore reduce both nQUBO and the interaction count by removing infeasible missions before the matrix Q is assembled<ref:2610.

Improvements for AI systems

Bold header: Classical feasibility preprocessing for mission generation

Classical checks can eliminate unsuitable route candidates before the combinatorial optimization is performed, which reduces the binary search space and directly impacts the input size to the QUBO solver.

Bold header: Hybrid quantum-classical solver strategy

The system can leverage classical methods like Exact enumeration and Simulated Annealing (SA) for high-quality solutions, as SA achieves 100% feasibility with a median optimality gap of 0%, while QAOA is reserved for smaller instances, acknowledging that the evaluated shallow statevector-based QAOA configuration achieves lower feasibility and is restricted to small QUBO instances.

Bold header: Scaling based on effective problem dimension

The AI system can prioritize the reduction of the number of QUBO variables over the nominal customer count, as the resulting QUBO dimension is therefore a more informative indicator of solver cost than the nominal number of delivery requests.

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.