Hybrid Quantum-Classical Routing Saves 2.8% on Delivery Distances — Then Hits a 16-Qubit Wall

A MILP+QUBO decomposition shaves real meters off London delivery routes via simulated annealing, but gate-model quantum hardware maxes out at 4-customer subproblems.

Imagine you're assembling flat-pack furniture. The instructions say to build the whole bookshelf at once, but you don't have enough floor space. So you build each shelf separately on the kitchen table, then slot them into the frame. That's exactly what this paper does with vehicle routing: it uses classical optimization (MILP) to assign customers to trucks and sequence them, then hands each individual truck's route to a quantum or quantum-inspired solver to shave off distance. The key insight is that the monolithic QUBO formulation of CVRPTW — encoding every constraint as a penalty term in one giant binary optimization — scales catastrophically. By decomposing per-vehicle, you keep subproblems small enough for near-term hardware. The committed claim: a hybrid classical-quantum framework for CVRPTW that provably maintains feasibility through decomposition, demonstrated on realistic London benchmarks from 10 to 70 customers, with Toshiba's simulated bifurcation machine (SQBM+) delivering verified distance reductions of 2.80% on a 25-customer instance and 0.22% on a 55-customer instance. Gate-model QAOA on Rigetti Ankaa-3 and IQM Emerald hardware reliably satisfies constraints only up to 4-customer subproblems (16 qubits). This is not a quantum advantage paper. It is a systems architecture paper that honestly maps where quantum hardware currently fails. On the ladder: the classical baseline is their own MILP solver, and the improvements come from SQBM+ — which is a simulated annealing machine, not a quantum computer. The actual quantum processors (Rigetti, IQM) did not beat the classical baseline at any scale tested. The 2.80% reduction is real and verified, but it comes from a classical-physics-inspired device, not from quantum gates. This distinction matters enormously for anyone evaluating quantum readiness claims. The paper is honest about this, which is refreshing, but readers should not conflate SQBM+ results with quantum computing results. Architecturally, the paper sits in the variational/QUBO family: decompose a constrained combinatorial problem into unconstrained binary subproblems, then solve with either simulated bifurcation (classical analog) or QAOA (parameterized quantum circuits). The MILP master problem handles assignment, capacity, and time-window constraints; QUBO subproblems handle intra-route sequencing. The validation pipeline enforces monotone improvement — no solution is accepted unless it's strictly better than the classical baseline AND feasible. This is a sensible engineering choice that prevents the usual QUBO failure mode of reporting infeasible "improvements." Integrity is mixed. The benchmarks are custom-derived from London traffic data, not community-standard Solomon or Gehring-Homberger instances. This makes direct comparison with the broader VRP literature impossible. The monotone-improvement validation pipeline is a genuine contribution to honest reporting, but the absence of standard benchmarks limits external validation. No code release is mentioned. The five benchmark instances (10–70 customers) are realistic but small by operations-research standards, where state-of-the-art heuristics routinely handle 1,000+ customers. The most useful diagnostic finding is that time-window tightness at the assignment level — not route-level optimization — is the dominant scalability bottleneck. This means even if quantum hardware improves dramatically, the MILP master problem's ability to make good assignments under tight time windows will gate overall performance. It's a systems-level insight that redirects where research effort should go: better decomposition strategies, not just bigger quantum processors. For the milestone picture: QAOA currently caps at 16 qubits for reliable constraint satisfaction on this problem. Scaling to subproblems of 8–10 customers (32–40 qubits with acceptable error rates) would be the threshold where gate-model quantum hardware starts competing with SQBM+ on per-vehicle routes. That's probably 3–5 years out given current hardware trajectories, and even then, SQBM+ and classical metaheuristics will have continued improving in the meantime.