CS Paper Radar

Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing

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

cs.ET quant-ph ·submitted 2026-10-14 22:53 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Quantum Approximate Multi-Objective Optimization in Routing Problems

cs.ET quant-ph ·2026-09-15 ·Eduardo Willwock Lussi, Alisson dos Passos Fumaco, Marcos Vinicius Reballo, José Carlos Libois Neto, Fernando Augusto Caletti de Barros +1 more
similarity 0.73
Abstract

Multi-objective optimization (MOO) problems are common in logistics, where routing decisions must balance conflicting objectives such as travel distance, delivery time, and operational risk. A recently proposed Quantum Approximate Optimization Algorithm (QAOA) parameter-transfer strategy solves multi-objective MAX-CUT problems by reusing parameters trained on smaller instances, avoiding costly reoptimization for each scalarized problem. However, its effectiveness has only been demonstrated on proof-of-concept instances tailored to quantum hardware connectivity. In this work, we evaluate the applicability of this strategy to realistic routing problems. We formulate the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) as Quadratic Unconstrained Binary Optimization (QUBO) models, reduce them to MAX-CUT, and assess the parameter-transfer framework under conditions matching the original study. Validation is performed through classical simulations and experiments on IBM quantum hardware. The resulting Pareto fronts are compared with those obtained using an adapted classical ε-constraint method, using hypervolume as the primary quality metric. Results indicate that parameter transfer remains effective, frequently achieving higher hypervolume and often finding competitive solutions earlier. However, performance depends on problem structure. The approach is consistently effective for TSP instances but less stable for the more constrained VRP, suggesting that QAOA parameter transferability decreases as the optimization landscape becomes more complex. These results provide the first comprehensive evaluation of QAOA parameter transfer on realistic multi-objective routing problems and demonstrate its potential beyond proof-of-concept MAX-CUT benchmarks.

0.23

Quantum Annealing for Resource Allocation in Next-Generation Wireless Communication Networks: A QUBO Modeling Guide

cs.IT ·2026-10-09 ·Nguyen Xuan Tung, Le Tung Giang, Mai Dinh Cong, Pham Dang Anh Duc, Nguyen Hoang Viet +2 more
published similarity 0.70
Abstract · 16 pages, 5 figures, and 7 tables. Accepted by OJ-COMS

Quantum annealing (QA) offers a physics-inspired approach for such subproblems by mapping them onto an Ising Hamiltonian, which is algebraically equivalent to a Quadratic Unconstrained Binary Optimization (QUBO) model executable on quantum annealers or hybrid solvers. However, their practical employment in wireless systems critically depends on the specific problem formulation, on the particular variable encoding, constraint handling, solver selection, hardware embedding, and fair benchmarking. This paper develops wireless-oriented QUBO modeling guidelines for QA-assisted resource allocation. We first present a beginner-friendly toy example in which a terrestrial-aerial resource-allocation problem with a fractional signal-to-interference-plus-noise ratio (SINR) maximization objective is reformulated into a two-bit QUBO via Boolean interpolation, converted into an Ising representation, and decoded back into a wireless scheduling decision. The same scheduling is applicable to UAV, aircraft, satellite, and terrestrial links in SAGIN systems. We then review the QA foundations and solver ecosystems, including binary quadratic, discrete quadratic, constrained quadratic, and hybrid models from the perspective of NG wireless optimization. Furthermore, we discuss both binary and discrete encoding, penalty-based constraint conversion, embedding overhead, solution decoding, and feasibility verification. A QUBO Compatibility Index is introduced as a lightweight diagnostic metric for assessing the associated QUBO formulation readiness, rather than a predictor of runtime or solution quality. Finally, a case study on max-min uplink power control in cell-free massive MIMO illustrates how a fairness-oriented wireless problem can be discretized, constrained, converted into the concept of a QUBO, and evaluated against classical baselines. A host of key challenges and future directions are also discussed.

0.23

Hybrid Classical-Quantum Optimization for CVRPTW: A Systems Framework with Provable Feasibility and Empirical Hardware Limits

cs.ET quant-ph ·2026-11-11 ·Syamasundar Gopasana, Swatantra Singh, Rohan Joydhar, Shubhashis Sengupta
similarity 0.67
Abstract · 11 pages, 3 figures, Poster version of this paper has been accepted to be presented at HiPC 2026 Bengaluru Conference

Solving large-scale Capacitated Vehicle Routing Problems with Time Windows (CVRPTW) remains challenging because strict operational constraints and scale limit both exact and heuristic methods. We present a hybrid classical-quantum architecture combining Mixed Integer Linear Programming (MILP) with vehicle-level Quadratic Unconstrained Binary Optimization (QUBO), solved using Toshiba SQBM+ and QAOA on Rigetti Ankaa-3 and IQM Emerald quantum processors. The decomposition avoids the variable growth and constraint-enforcement difficulties of monolithic CVRPTW QUBO formulations. We evaluate the framework on five realistic benchmarks derived from London traffic and location data, spanning 10--70 customers, using a validation pipeline enforcing feasibility and monotone improvement over classical baselines. SQBM+ achieves verified fleet-distance reductions of 2.80% (7,927 m) for the 25-customer instance and 0.22% (1,186 m) for the 55-customer instance. QAOA experiments establish a current hardware boundary for reliable constraint satisfaction at subproblems of up to 4 customers (16 qubits). Diagnostic results identify assignment-level time-window tightness, rather than local route optimization, as the dominant scalability bottleneck. The results demonstrate a practical near-term role for hybrid classical-quantum optimization while establishing empirical limits for current quantum hardware.

0.22

QC-CCG: Quantum-Classical Algorithm for Two-stage Adaptive Robust Optimization

cs.ET eess.SY ·2026-08-28 ·Duong The Do, Jiaming Cheng, Duong Tung Nguyen
similarity 0.66
Abstract · 12 pages

Quantum optimization provides a promising approach for solving large-scale combinatorial problems through quadratic unconstrained binary optimization (QUBO) formulations. However, integrating QUBO-based solvers into structured optimization frameworks while preserving solution guarantees remains a fundamental challenge. This paper develops a hybrid quantum-classical column-and-constraint generation (QCCG) framework for solving two-stage adaptive robust optimization problems with binary first-stage decisions and linear recourse under polyhedral uncertainty. The proposed approach reformulates the restricted master problem as a QUBO and solves it approximately using a quantum optimizer, while retaining a classical adversarial subproblem to compute worst-case recourse and certify solution quality. We construct a constraint-preserving QUBO encoding for inequality-constrained master problems using slack variables and penalty terms, enabling general mixed-integer structures to be mapped to quantum-compatible representations. To address inexactness arising from discretization, penalty modeling, and quantum optimization, we introduce a bound-adjustment mechanism that yields valid lower and upper bounds and provides a certified stopping criterion. We show that the proposed framework generalizes classical column-and-constraint generation and retains its convergence properties when the master problem is solved exactly. Numerical experiments on two-stage robust location-transportation problems demonstrate that the proposed hybrid approach achieves solution quality comparable to classical methods while reducing the computational burden associated with solving mixed-integer master problems, highlighting the potential of hybrid quantum-classical optimization for scalable decision-making under uncertainty.

0.26

Net-Zero Power UAVs: Facilitating Quantum HRLLC in Multi-Hop UAV Repeaters

eess.SY ·2026-10-16 ·Ali Ranjha, Georges Kaddoum, Halim Yanikomeroglu
publishedbenchmarkhot direction similarity 0.66
Abstract · 5 pages. Published in IEEE Wireless Communications Letters. This work was supported by the Postdoctoral Research Fellowship from the Fonds d…

In this paper, we propose a novel joint optimization framework for autonomous, quantum-enabled UAV repeater networks designed to support hyper-reliable low-latency communications (HRLLC) in challenging environments such as post-explosion chemical plant operations. The proposed system uses a symmetric dual-UAV architecture with three sequential quantum channels operating under strict energy harvesting (EH) constraints. We formulate a highly challenging non-convex mixed-integer non-linear programming (MINLP) problem. This model jointly determines qubit allocation, 2-D uncrewed aerial vehicle (UAV) spatial positioning (distance and altitude), and transmit powers to minimize the total decoding error. Crucially, our framework explicitly models real-world quantum physics, including decoherence, gate imperfections, and entanglement degradation. Since the objective function is demonstrably non-convex, to efficiently solve the MINLP, we propose a quantum-resource-optimized GA (QRO-GA). The results of our numerical simulations show that the QRO-GA yields better results than benchmark methods and it is highly efficient, with the convergence speed significantly increasing with the total qubit allocation. Convergence is achieved in as few as 5 iterations for higher qubit allocation. Moreover, the results reveal a critical U-shaped tradeoff, proving that an optimal latency distribution within a strict $80\ μ$s transmission window is strictly required to maintain HRLLC reliability. In addition, we find that the QRO-GA successfully optimizes the 2-D UAV positioning to minimize total decoding error. Finally, it balances consumed and harvested power to achieve net-zero power UAVs system.

0.40

Quantum-Based k-Coverage Optimization for UAV-Aided Search and Rescue Missions

eess.SY ·2026-09-01 ·Halim Lee, Suhui Jeong, Na Young Kim, Jiwon Seo
published similarity 0.64
Abstract · Accepted for publication in the IEEE Internet of Things Journal

In large-scale disaster scenarios, rapid localization of missing persons is a critical challenge for search-and-rescue (SAR) operations. Unmanned aerial vehicles (UAVs) equipped with radio frequency (RF) receivers can support RF-based localization by collecting signals emitted from mobile devices at spatially distributed sensing locations. This paper addresses the resulting waypoint-selection problem: determining a minimum set of UAV waypoints that provides at least threefold coverage of every potential target location. We formulate this task as an extended k-coverage problem that independently defines the UAV-navigable and target regions, and derive an exact-penalty quadratic unconstrained binary optimization (QUBO) formulation with a sufficient penalty condition that preserves feasibility and minimum waypoint cardinality. The QUBO is mapped to an Ising-form cost Hamiltonian and evaluated using the quantum approximate optimization algorithm (QAOA) on both a noise-free simulator and IBM's 127-qubit Eagle processor. On the tested simulator instances, QAOA recovers the known minimum-cardinality solutions. Across the rectangular hardware test cases, the mean 3-coverage ratio exceeded 95%. In the campus-scale evaluation, ten hardware executions achieved 99.3% mean 3-coverage with a 90% feasible-run rate, while the shortest feasible flight path was up to 37.0% shorter than those of the deterministic grid-based baselines. Additional comparisons with classical optimization and learning-based baselines are provided, together with computational and quantum-resource analyses for larger generated instances. These results establish an exact QUBO representation for RF-based SAR waypoint selection and characterize its implementation on current gate-based quantum hardware.

0.32

Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes

cs.ET quant-phmath.COmath.OC ·2026-10-30 ·Emanuele Casciaro, Mario De Simone, Stefano Martina, Fabio Mascherpa, Alfonso Amendola +1 more
similarity 0.63
Abstract · 12 pages, 6 figures, 1 table

With the expansion of complex transport infrastructure, new paths for linking different destinations have emerged, allowing the definition of multiple routes. The introduction of new roads may also lead to disruptions in traffic flow. This problem can be generalized into a special case of VRP, which aims to find the optimal route for a fleet of vehicles within a network of destinations. Finding solutions to this problem requires an exponential number of operations, hindering the ability of exact solvers to deal with large instances, which must therefore be tackled using heuristics, often leading to suboptimal results. Quantum-based algorithms may allow us to find exact solutions in polynomial time with high probability, offering a potential future alternative to classical solvers and in this work, we focus on the QAOA. Our novel contributions are a parameter-initialization strategy that improves the convergence probability and the integration of the subtour constraints directly into the optimization without using additional qubits by employing an approximation of exponential equality constraints. We believe that our results pave the way for effectively solving instances of VRP using quantum-based solutions, leveraging the space-efficient problem encoding and our initialization strategy, which limits the effect of barren-plateau under random parameter initialization.

0.08

GPU-Accelerated Quantum Annealing-Inspired UAV Path Planning for Smart Agriculture

cs.ET eess.SY ·2026-08-26 ·Maho Hirahara, Aohan Li
similarity 0.62
Abstract · 6 pages, 3 figures, conference

With the rapid advancement of smart agriculture, Unmanned Aerial Vehicles (UAVs) have become indispensable for efficient coverage and path planning in grid-mapped agricultural fields. However, optimizing UAV flight paths in large-scale environments remains a complex Nondeterministic Polynomial-time (NP)-hard problem. Traditional path planning methods are often constrained by local optima, limited scalability, and slow convergence, which significantly restrict their effectiveness in solving large-scale problems. To address these limitations, this paper proposes a novel optimization framework utilizing a Graphics Processing Unit (GPU)-parallelized Ising solver. Our method mimics the operational principles of quantum annealing on GPU hardware, enabling rapid search for the minimum-energy state of Ising models. Unlike physical quantum devices, which are often constrained by the number of qubits, our approach leverages the Fixstars Amplify (FA) platform to perform parallel annealing on highly parallelized GPUs. This enables the simultaneous evaluation of thousands of potential path candidates and vast state transitions. By leveraging large-scale parallel processing, this framework's core strength lies in minimizing computation time even as the problem scale increases. Simulation results demonstrate that our proposed method consistently identifies superior flight paths while maintaining stable computational performance compared with the genetic algorithm and simulated annealing method.

0.29