Vehicle-Routing Clustering by Sparse Quantum Relaxation

AI summary

Overview

Research area: Quantum optimization for logistics — specifically quantum relaxation (QRAO) applied to the clustering layer of a vehicle-routing decomposition, with benchmarking on simulated and real IBM hardware.

Technical level: Intermediate. Readers need some familiarity with QUBO/Ising formulations, Pauli observables, and circuit resource metrics, but the paper's central argument is structural rather than mathematically heavy.

Scope (one sentence): The paper characterizes when a non-diagonal quantum relaxation of a capacitated pickup-and-delivery clustering problem remains non-redundant, and maps how graph sparsification trades off against QRAO compression, circuit cost, sampling drift, and final routing quality — without claiming quantum advantage.

What This Paper Is About

Directly encoding a vehicle-routing problem as a quantum optimization Hamiltonian scales badly, so the authors study only the cluster-assignment layer of a cluster-first-route-second decomposition for the capacitated pickup-and-delivery problem with time windows (CPDPTW), leaving route ordering to classical solvers. They show that the natural quantum candidate — sample-based subspace diagonalization (SQD) — is provably useless on a diagonal optimization Hamiltonian, because it collapses exactly to picking the best sampled bitstring; a genuine quantum contribution requires a non-diagonal relaxation, which quantum random access optimization (QRAO) supplies. The goal is then to determine where, on the sparsity-versus-compression trade-off, CPDPTW instances can actually sit.

Key Contributions

1. A best-of-shots lemma for diagonal SQD, paired with a Krylov-dimension sweep. The authors prove that projecting any diagonal QUBO/Ising/Max-K-Cut Hamiltonian onto a sampled subspace yields a diagonal operator whose ground state is simply the lowest-cost sampled bitstring, so subspace diagonalization adds nothing; they then sweep the Krylov dimension on the relaxed Hamiltonian to separate this diagonal redundancy from the genuine non-diagonal signal.

2. Quantification of a routing-specific density obstruction. Building on the QRAO independent-set requirement, they show binary-label compression falls from threefold on sparse graphs to no compression on dense CPDPTW instances, and that penalty encodings pin interaction density at roughly 0.371 regardless of sparsification.

3. Repair-after-rounding as part of the encoding architecture. Because full two-phase repair drives all methods to near-zero gap, they isolate decoder-level gains in a feasibility-only ablation, where SQD-weight reranking helps by an amount that scales with the rerank budget.

4. A reproducible characterization protocol and a 108-row ideal-calibrated-hardware grid. The grid spans ideal Qiskit Aer, calibrated FakeTorino, and IBM Heron ibm_quebec, reporting achieved QRAO compression, LCU 1-norm, heavy-hex two-qubit depth, a TVD null floor, an ALNS-prior Spearman check, and final routing gap.

Main Findings

• Diagonal subspace diagonalization is exactly best-of-shots. For any diagonal Hamiltonian and any superposition over sampled bitstrings, the energy expectation is a convex combination of sampled costs, so it can never beat the minimum sampled cost. The paper's method comparison confirms this: diagonal best-of-shots tracks random-labels plus repair.

• The non-diagonal signal is real at the energy level. At N = 8, the SQD ground energy drops from −3.20 ± 0.55 at Krylov dimension r = 1 to −5.51 ± 1.19 at r = 5 over 10 seeds. Gains for r > 1 come from the time-evolved samples, since at r = 1 the only prepared state is the all-zero state.

• Compression collapses on dense graphs. Achieved compression ρ_comp is defined as binary variables divided by relaxed qubits. One-hot QRAO compression stays at the nominal 3× regardless of sparsification, while binary/HOBO compression goes from 3× at quantile q = 0.9 down to 1× at q = 0.

• Penalties are the culprit. At N = 12, objective-only interaction density falls from 0.31 to 0.04 across q ∈ [0, 0.9], and compression tracks it from 1.00× to 3.00×. Adding one-hot penalties raises interaction density by +0.06 to +0.09 at every q, and full one-hot plus capacity/time penalties lock it at 0.371 independent of q.

• Sparsification also shrinks circuit resources. On instances of size N ∈ {6, 8, 10, 12}, the LCU 1-norm λ drops from about 26 at q = 0 to about 8 at q = 0.9 for N = 8. At N = 12, sparsification reduces the Pauli-term count L from 186 to 87 and TVD from 0.568 to 0.279 as q moves from 0.25 to 0.75.

• Under full repair, everything converges — so the decoder is where the difference lives. Under full two-phase repair all four methods converge to gap ≤ 0.02. In the feasibility-only ablation with a fixed top-32 eigenvector rerank, gains over random labels are 48%, 37%, 9%, and 3% for N = 6, 8, 10, 12.

• The apparent fade at larger N is partly a decoder-budget effect. Widening the rerank to 512 candidates changes the N = 10 and N = 12 gaps from 0.281 and 0.265 to 0.131 ± 0.024 and 0.173 ± 0.018. Best feasible candidates appear deep in the |α_x|² ordering, with median ranks 340 at N = 10 and 785 at N = 12.

• The subspace projection is noise-stable, but the fixed shallow ansatz is the bottleneck. Under a FakeTorino noise sweep with s ∈ {0, 1, 2, 5} at N = 8, SQD ground energy varies by less than 0.03 (−5.283 to −5.307 over 8 seeds), and at s = 5 the feasibility-only gap is 0.231 versus a noiseless 0.23. However, rounded gap stays near 0.88 because Pauli-expectation rounding collapses the assignment before repair can act; classical top-1 shot share drops from 0.46 to 0.19 and Gini from 0.85 to 0.65 under noise, but these raw shot statistics do not determine the post-repair gap.

• Hardware results are feasible and low-gap, with measurable drift. The 108-row grid spans N ∈ {4, 6, 8, 10, 12}, K ∈ {2, 3, 4}, q ∈ {0, 0.25, 0.5, 0.75}, r ∈ {1, 3, 5, 7}, and both (3,1) and (2,1) QRAC encodings. Every hardware row produces a feasible repaired assignment; mean hardware gap is 0.0016 and the worst observed gap is 0.0382.

• Device-vs-ideal drift grows with problem size but stays above the null floor. Across 36 hardware rows the observed TVD is 0.279 against a null floor of 0.114 (ratio 2.44). By size: N = 4 gives 0.174 vs 0.041; N = 6 gives 0.185 vs 0.078; N = 8 gives 0.324 vs 0.133; N = 10 gives 0.391 vs 0.195; N = 12 gives 0.463 vs 0.254. Observed TVD is 1.8 to 4.3 times the floor.

• The ALNS-derived noise prior ranks but does not calibrate. It predicts mean TVD 0.614 versus an observed 0.279, yet its ranking survives with Spearman 0.854 and Pearson 0.801, so it is usable for shot allocation ordering only.

• Repair supplies most of the practical improvement. Across all hardware rows, repair reduces the mean rounded gap from 0.493 ± 0.035 to 0.0016 ± 0.0012 using 4.47 ± 0.42 moves. Rounded-label agreement with ideal sampling is 67% overall and repaired-label agreement is 78% (75% at N = 12). Shot coverage of 3000/K^N is 46%, 5%, and 0.6% at (N, K) = (8,3), (10,3), (12,3).

• No advantage is claimed. Under strong repair the classical pass alone reaches near-optimal cost at the tested sizes, so the quantum contribution is described as structural and regime-dependent rather than a performance win.

Methodology in Plain English

Each pickup–delivery request pair is contracted into a single "supernode" before any quantum encoding, which enforces the must-link constraint in advance and avoids a large penalty term. A weighted conflict graph is then built over supernodes using normalized demand pressure and a pairwise time-window incompatibility measure, so that heavily incompatible requests get large weights and should be separated into different vehicle clusters.

That graph is almost always dense, which is fatal for QRAO because QRAO can only pack variables onto one qubit when they form an independent set in the problem graph. So the authors add an explicit sparsification step — thresholding small weights or keeping k nearest neighbors — and treat the sparsification level as a free parameter rather than a preprocessing detail.

Only the sparsified Max-K-Cut objective is encoded into the quantum Hamiltonian. The one-hot, capacity, and cluster time-budget constraints are deliberately kept out of the Hamiltonian to avoid the all-pairs clique structure that a quadratic penalty creates. Instead, several classical binary variables are packed onto one qubit via non-commuting Pauli observables using a QRAC, making the Hamiltonian non-diagonal and subspace diagonalization meaningful.

Sampling uses a fixed shallow SKQD-style preparation: start from the all-zero state, apply Lie–Trotter time evolution by kΔt for k = 0 to r−1 with one-step PauliEvolutionGate, and take the union of measured bitstrings from all r circuits, expanded by Hamming-1 neighbors of the top 32 sampled configurations, as the subspace to diagonalize. The parameter r counts sampled time points, not ansatz depth.

Decoded assignments come from Pauli-expectation rounding, which guarantees neither one-hot assignment nor capacity or time-budget feasibility. A two-phase repair then restores feasibility by moving requests between clusters, and improves the cut by seeding empty clusters with high-degree admissible requests and applying reassignments that preserve all budgets. Finally, each repaired cluster is sequenced by exact dynamic programming when small enough, or by OR-Tools/ALNS otherwise, and the score reported is the true CPDPTW route cost, not the relaxed energy.

Why This Matters

Impact on research: The paper supplies a clean negative result — diagonal subspace diagonalization on an optimization Hamiltonian is just best-of-shots — that closes off a tempting but empty transfer from quantum chemistry to combinatorial optimization. It also names a failure mode specific to routing (penalty-induced graph density defeating QRAO compression) that does not appear in sparse MaxCut benchmarks, and it provides three reusable baselines: an achieved-compression curve versus sparsification on CPDPTW graphs, a calibrated Heron record with a TVD null floor, and decoder-budget scaling for subspace-argmax gains.

Real-world applications:

• Urban last-mile freight, where route quality directly drives fleet-kilometers, energy use, and greenhouse-gas emissions.
• Drone delivery fleets, which face the same pairing, precedence, capacity, and time-window structure.
• Real-time dispatch under dense, rapidly changing request patterns, where decomposition into a clustering layer plus fast classical sequencing is the practical architecture.
• Hybrid logistics pipelines that already use adaptive large neighborhood search or learning-based solvers and want to know whether a quantum sampler could plug into the clustering stage.

Industry relevance: For logistics software vendors, the practical message is that the quantum component should be scoped to a surrogate objective while classical repair and sequencing carry feasibility — a division of labor that mirrors how production solvers are already built. For quantum hardware and cloud providers, the paper offers a calibrated, reproducible regime map on IBM Heron ibm_quebec with an explicit noise floor, which is more useful for deciding whether a routing workload is worth running than a headline energy number.

Future Directions

• Better rounding rules. The authors explicitly list alternative single-qubit rounding rules as future work, motivated by the finding that Pauli-expectation rounding collapses to one cluster and leaves a rounded gap near 0.88 at N = 8.

• Learned graph pruning. Sparsification is currently a thresholding or k-nearest-neighbor choice over an engineered weight formula; learning which edges to keep could move the operating point on the sparsity-versus-approximation trade-off.

• QSVT and Fejér filtering. The paper treats linear-combination-of-unitaries and quantum singular value transformation only as analytic resource lenses, with filter degree scaling as d ∼ λ/Δ, and notes that Fejér-filter constructions offer related finite-depth, finite-shot guarantees when constraints are handled outside penalties.

• Larger-instance hardware plus matched-budget baselines. The authors call for larger-instance hardware runs and matched-budget QAOA and CVaR comparisons, which would test whether the near-zero hardware gap at N ∈ {10, 12} survives beyond the sizes tested here.

Target Audience

Quantum optimization researchers working on constrained combinatorial problems will find the best-of-shots lemma and the density-obstruction analysis directly useful, as will practitioners benchmarking NISQ devices on real workloads who need a template for reporting TVD null floors and decoder-budget scaling. Operations research and transportation scientists interested in where a quantum sampler could plausibly sit inside a decomposition-based VRP solver will benefit from the clear separation of quantum objective encoding from classical feasibility repair. The paper assumes comfort with QUBO formulations and Pauli observables, so it is best suited to readers with intermediate quantum computing background rather than complete beginners.

Authors’ abstract

This paper studies the cluster-assignment layer of a cluster-first-route-second decomposition for the capacitated pickup-and-delivery problem with time windows (CPDPTW), instead of a direct route-ordering quadratic unconstrained binary optimization (QUBO). Sample-based subspace diagonalization (SQD) degenerates to best-of-shots for any diagonal optimization Hamiltonian, so a useful transfer to routing requires non-diagonal relaxation. Quantum random access optimization (QRAO) provides this non-diagonality by encoding binary variables through non-commuting quantum random access code (QRAC) observables. CPDPTW-derived conflict graphs expose a routing-specific obstruction because dense objectives and penalty-encoded constraints destroy QRAO compression. We keep the Hamiltonian sparse by encoding only the sparsified objective and enforcing one-hot, capacity, and cluster time-budget feasibility by repair after rounding. We make no quantum-advantage claim. Under strong repair the classical pass alone reaches near-optimal cost at the tested sizes. The result is a regime map linking sparsification, achieved compression, linear-combination-of-unitaries (LCU) 1-norm, heavy-hex two-qubit depth, sampling drift, and final routing quality on Qiskit Aer, calibrated FakeTorino, and IBM Heron ibm_quebec. Across a 108-row ideal-calibrated-hardware evaluation grid spanning four to twelve pickup-delivery request pairs, the hardware slice has mean gap 0.0016 and mean device-vs-ideal total variation distance (TVD) 0.279; a decoder ablation at sizes six through twelve isolates the non-diagonal signal.