arXiv:2609.19575
Vehicle-Routing Clustering by Sparse Quantum Relaxation
Farzan Moosavi, Bilal Farooq
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.
AI Summary
The paper asks whether sample-based subspace diagonalization (SQD) can support quantum-assisted clustering for capacitated pickup-and-delivery routing with time windows. For a diagonal cost Hamiltonian, SQD on sampled computational-basis states is exactly best-of-shots. It therefore uses quantum random access optimization (QRAO) to construct a non-diagonal relaxation of a cluster-assignment surrogate, leaving route sequencing classical. The pipeline sparsifies request-conflict graphs, encodes only the clustering objective, and enforces assignment, capacity, and cluster-time budgets through classical repair after rounding. Graph analysis shows why this matters: dense interactions prevent independent-set packing for QRAO, while quadratic constraint penalties restore cliques. Across tested instances, binary/HOBO compression changes from $1\times$ on dense graphs to $3\times$ after sparsification; full penalties maintain interaction density near $0.371$. Experiments use fixed shallow Krylov-state sampling, ideal simulation, calibrated noise simulation, and IBM Heron hardware. At eight requests, increasing the Krylov dimension from one to five lowers SQD energy from $-3.20\pm0.55$ to $-5.51\pm1.19$. A 108-record evaluation includes 36 hardware runs spanning four to twelve requests; hardware has mean reported gap $0.0016$ and mean device-versus-ideal total variation distance $0.279$, versus a finite-shot null floor of $0.114$. The principal limitation is that strong classical repair also brings classical baselines near optimality, masking any quantum contribution. Feasibility-only ablations show decoder-budget-dependent gains, but a matched randomized-rounding surrogate is deferred. The instances are small, routing constraints are partly represented by clustering proxies, and no quantum advantage is claimed.
Central claim may not hold: The abstract overgeneralizes the density-induced loss of QRAO compression: the reported objective-only one-hot encoding retains 3× compression, whereas the demonstrated collapse concerns binary/HOBO encodings. The advertised regime map includes heavy-hex two-qubit depth, but the paper supplies no numerical depth results or comparison across sparsification levels. Although the paper identifies true CPDPTW route cost as its final objective, it does not define the reported gap or its hardware reference optimum, leaving the claimed near-optimal routing quality unverified.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Journal reference
- In the proceeding of IEEE Quantum Artificial Intelligence 2026