A Technion Team Fixes the Disconnected-Route Flaw in Quantum Vehicle Routing and Tests the Repair on IQM Emerald
Quentir Defense Monitor
Evidence-based insights for quantum defense and security. Published by Quentir Systems LLC · August 28, 2026.
For a decade the sales pitch for quantum optimization has led with logistics, because routing trucks between depots and delivery points is the kind of combinatorial problem a defense sustainment planner solves every working day. A paper posted to arXiv on August 27, 2026 by three computer scientists at the Technion in Haifa, joined by a colleague at the MIGAL Galilee Research Institute, reports that the standard compact encoding of that problem for quantum hardware carries a structural flaw: its lowest-energy answers can be sets of closed loops that never visit the depot, which on a real map is a delivery plan no truck can drive.
The paper, Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing by Omer Gurevich, Maor Matityahu, Tal Mor and Aryeh Lev Zabokritskiy, does three things a buyer of quantum optimization should notice. It measures how often the flawed encoding produces an infeasible plan, it constructs a repair with a mathematical proof of correctness, and it runs both versions on a real 54-qubit superconducting processor to show what present-day hardware makes of them. Each step yields a number worth remembering, and the last number is the sobering one.
Degree Constraints Alone Reward Routes That Skip the Depot: the 98.5 Percent Finding
An arc-based QUBO writes the vehicle routing problem as a grid of yes-or-no decisions, one binary variable per road segment, with penalty terms that punish any customer holding more or fewer than one incoming and one outgoing arc, and any depot sending out a number of routes different from the fleet size. Encodings of this family run throughout the quantum annealing and QAOA literature because they are compact and map directly onto hardware couplings. The Technion group's observation is that these degree penalties enforce only what graph theory calls a cycle cover: every customer sits on some closed loop, yet nothing forces every loop to pass through the depot. A loop of customers circling among themselves satisfies every local constraint and pays less in travel cost than a route that makes the trip home.
The counterexample in the paper takes six customers and one vehicle. Two disconnected triangles satisfy every degree constraint at a total cost of 6, while the cheapest genuinely drivable tour costs 24, so the encoding's energy minimum is an undeliverable plan that appears four times cheaper than the true optimum.
The team then measured how often this failure bites in practice. Across 1,200 randomly generated cost matrices with five to ten customers, spanning Euclidean road-distance geometry as well as asymmetric integer costs, the disconnected optimum was strictly cheaper than the cheapest connected tour in 98.5 percent of the single-vehicle metric instances, with a mean cost gap of 20.32 percent. A solver that faithfully minimizes this objective will hand back an undriveable plan on essentially every realistic input, and the sampler is blameless, since the mathematics itself asks for the wrong thing.
A Capped Single-Commodity Flow Proves Every Optimal Route Passes Through the Depot
The repair borrows a classical device from integer programming and rebuilds it for binary quadratic hardware. Alongside each yes-or-no arc variable, the corrected model routes an imaginary commodity out of the depot: every customer must absorb exactly one unit of flow, flow may ride only on arcs the route actually uses, and the capacity bounds permit a depot-adjacent arc to carry all units assigned to its route. A closed loop that avoids the depot has no source feeding it, its customers can never absorb their unit, and the penalty terms price the loop out of the ground state. Since the flow on an arc is an integer, the construction encodes it in binary, spending roughly the base-two logarithm of the customer count in extra qubits per arc.
The accounting is stated openly. The repaired encoding multiplies the qubit budget per road segment, and on a fully connected map the number of quadratic couplings grows with the cube of the customer count. In exchange, Theorem 1 of the paper proves that once the penalty weights clear a stated threshold, every minimizing assignment of the corrected objective encodes an optimal, feasible set of depot-to-depot routes. The claim holds for any solver that truly reaches the ground state, quantum annealer, gate-model processor or classical heuristic alike.
Quantum pillar: computing (optimization and logistics). Use posture: dual-use. Technology readiness: TRL 3 of 9. The repaired model is mathematics with a correctness proof, and the accompanying run on a real 54-qubit processor is a small proof-of-concept execution, which places the work at experimental proof of concept, far from a planning tool a logistics unit could rely on.
On IQM Emerald in Stockholm, the Corrected Circuit Produced No Fully Feasible Route Across Its Hardware Runs
The hardware section of the paper is short and unusually candid. On July 23, 2026 the team ran depth-one QAOA circuits through Amazon Braket's Europe Stockholm region on IQM Emerald, a 54-qubit superconducting processor built on transmon qubits in a square lattice with tunable couplers, offered on Braket since July 2025. The test instance was deliberately tiny: four nodes and one vehicle, six qubits in the flawed degree-only version and fourteen once the flow repair was added, with circuit angles optimized classically and frozen before execution, and 32,000 shots collected in total across both versions.
The flawed circuit behaved exactly as the theory predicts. In 78.05 percent of its selected shots, IQM Emerald landed on the invalid disconnected ground state, a live demonstration that the encoding can steer a working quantum processor toward the undriveable answer. The repaired fourteen-qubit circuit removed that trap but produced no fully feasible sample across its hardware runs. This single depth-one, frozen-angle experiment does not establish why no feasible sample appeared or whether other depths, parameters or algorithms would do so. Both numbers matter to a reader weighing capability. The first shows the mathematical flaw manifesting on hardware; the second shows that the corrected problem, even at toy scale, did not yield a feasible result in this depth-one experiment.
What a Military Logistics Buyer Should Ask About Quantum Route Optimization
Routing sits squarely on the defense side of the dual-use line as well as the commercial one, and the posture reading is dual-use in the plainest sense: the beneficiary is whoever runs the depots. The same mathematics that schedules parcel vans schedules fuel convoys, aerial resupply and ship replenishment, and the capability a working quantum route optimizer would offer a force is faster re-planning of sustainment movements under pressure, when roads close and demand shifts faster than a staff section can recompute. That prospect is why optimization appears on every list of candidate military quantum computing applications, and why this paper's finding lands on program offices and parcel carriers alike.
The honest baseline is classical. Google's freely available OR-Tools routing solver handles vehicle routing with capacity limits, time windows and dropped-visit penalties at the scale of hundreds of stops on ordinary hardware, and dedicated commercial solvers go further. In this depth-one experiment, the quantum device did not return one feasible four-node route from the corrected circuit, while other depths, parameters or algorithms were not tested. DARPA's Quantum Benchmarking Initiative frames the question that matters for 2033: whether any quantum computer's computational value will exceed its cost at industrially useful scale, which is exactly the bar route optimization has to clear before a sustainment cell should care.
For a program office, the near-term value of the Technion work is procedural rather than computational, and it converts directly into acquisition questions. Formulation correctness is now a checkable line item: a vendor offering annealing or QAOA route planning should be asked whether its encoding provably excludes depot-disconnected solutions and what that proof costs in qubits. Feasibility rate is a more revealing benchmark than average solution energy, since an optimizer whose selected samples are 78 percent undriveable plans carries a defect that energy statistics conceal. Qubit budgets in vendor roadmaps deserve matching scrutiny, because a correctness repair of this kind multiplies the per-segment qubit count, and a roadmap priced on the flawed encoding understates the hardware the real problem needs.
The result worth watching next is a repaired-encoding run that reports its feasibility rate on larger instances and deeper circuits. Until one appears, military logistics planning stays with the classical solvers, and the readiness ladder for quantum routing starts at the rung this paper honestly documents.
Sources
Primary source: Omer Gurevich, Maor Matityahu and Tal Mor of the Technion, Israel Institute of Technology, with Aryeh Lev Zabokritskiy of the MIGAL Galilee Research Institute, 'Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing,' arXiv:2608.26894, August 27, 2026. Other material: AWS Quantum Technologies Blog on IQM Emerald (July 21, 2025); DARPA Quantum Benchmarking Initiative program description; Google OR-Tools routing documentation.