{"id":"arxiv/2608.26894","url":"https://arxiv.org/abs/2608.26894","tags":["quant-ph","cs.DS","math.OC"],"score":0,"title":"Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing","domain":"quant-ph","source":"arxiv","authors":["Omer Gurevich","Maor Matityahu","Tal Mor","Aryeh Lev Zabokritskiy"],"reviews":0,"subject":"quant-ph","summary":"We revisit a degree-only arc Hamiltonian for fixed-fleet, homogeneous, uncapacitated vehicle routing. Its local penalties define only a cycle cover, so ground states may contain customer cycles disconnected from the depot. We construct a polynomial-size quadratic unconstrained binary optimization (QUBO) repair using capped single-commodity flow and prove connected, cost-optimal ground-state routings under explicit penalty assumptions. For $N-1$ customers and $K$ nonempty routes, the unreduced encoding uses exactly $|E|(1+\\lceil\\log_2(N-K+1)\\rceil)$ logical problem qubits. A reversible…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-27","reactions":{}}