Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing
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
- Reducing quantum and classical resources for quantum-centric supercomputing workloads on near-term hardware
- Reducing the complexity of sum-of-products potential energy surfaces for efficient MCTDH calculations
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- Probing the classical complexity of quantum dynamics experiments
- Optimal Lower Bound on the Sample Complexity of Coherent Classical Shadows for Mixed States
BibTeX
@misc{illesova2026reducing,
title = {{Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing}},
author = {Silvie Illésová and Vojtěch Novák and Martin Beseda},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21003},
eprint = {2610.21003},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21003},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing
AU - Silvie Illésová
AU - Vojtěch Novák
AU - Martin Beseda
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.21003
UR - https://arxiv.org/abs/2610.21003
AB - 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.
ER -