Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing

Omer Gurevich; Maor Matityahu; Tal Mor; Aryeh Lev Zabokritskiy

Source-linked AI summary

Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing

Omer Gurevich, Maor Matityahu, Tal Mor, Aryeh Lev Zabokritskiy

arXiv:2608.26894v1Aug 27, 2026quant-phcs.DSmath.OC

TL;DR

The paper addresses the gap that degree-only arc Hamiltonians can admit depot-disconnected subtours in fixed-fleet VRP. It repairs the formulation with capped single-commodity flow and proves connectivity and cost-optimality under explicit penalties. The paper also compares encoding resources and reports that 78.05% of selected degree-only shots were invalid, while the reduced flow circuit produced no fully feasible sample.

Problem
Degree-only arc constraints define cycle covers that may contain depot-disconnected customer cycles, which are infeasible VRP plans.
Method
The paper adds capped per-arc single-commodity flow, bitwise flow-to-arc coupling, and explicit penalty terms to repair the audited QUBO.
Results
78.05% of selected p = 1 degree-only shots realized the invalid disconnected ground state, while the reduced 14-qubit flow-augmented circuit produced no fully feasible sample.
Takeaways & Limitations
Connectivity-correct Hamiltonians prevent the formulation’s disconnected-ground-state failure, but correctness alone does not guarantee useful feasible sampling on present hardware.
Takeaways & Limitations
The logical gate bound excludes rotation synthesis, coefficient precision, hardware connectivity, and error correction, while the device experiment uses termwise Ising compilation rather than the reversible realization.

Abstract

from arXiv · show

We revisit a degree-only arc Hamiltonian for fixed-fleet, homogeneous, uncapacitated vehicle routing. Because its local penalties define only a cycle cover, 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 that every ground-state routing is connected and cost-optimal 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 compute--phase--uncompute realization evaluates the flow penalties in $O(N^2\log N+N\log^2N)$ logical gates on a complete graph with $O(\log N)$ reusable workspace and no product register. On complete loopless graphs, a depot-delimited single-sequence position encoding uses fewer problem qubits and fewer written terms when the flow-word length grows. Conversely, the flow model achieves a smaller structured logical-gate upper bound under a common reversible accounting model. Exact audits of the Hamiltonian and circuit implementation, combined with a $1{,}200$-matrix classical benchmark, verify the formulation and quantify the connectivity gap. Finally, a 32,000-shot Amazon Braket task on IQM Emerald characterizes depth-one termwise Ising circuits on a diagnostic $N = 4,\, K = 1$ counterexample instance. In the degree-only circuit, $78.05\%$ of selected $p=1$ shots realize the invalid disconnected ground state; the reduced 14-qubit flow-augmented circuit yields no fully feasible sample. These device results characterize mapped Hamiltonians and compilation rather than an asymptotic routing solution advantage.

1 Introduction

The paper studies fixed-fleet, homogeneous, uncapacitated single-depot VRP encodings and identifies a connectivity gap in degree-only arc Hamiltonians. It reconstructs the failure, proposes a flow-based QUBO repair, and compares alternative formulation and compilation resources.

The paper audits the published arc Hamiltonian and related downstream formulations by comparing displayed constraints with the Hamiltonians they actually minimize.
Degree constraints alone permit customer cycles disconnected from the depot, making some ground states infeasible transportation plans.
The proposed repair uses capped single-commodity flow with L = ⌈log2(N − K + 1)⌉ bits per arc and enforces flow support without auxiliary slack variables.
Under explicit penalty bounds, the repair provides ground-state correctness while separating logical qubits, written interactions, and reversible-oracle resources.
The position encoding uses NT variables and Θ(NT^2 + TN^2) quadratic terms, while its variable count is not formulation-independent for vehicle-indexed position models.

2 Preliminaries and Previous Work

The preliminaries define the fixed-fleet VRP and review position-indexed Hamiltonian encodings for Hamiltonian cycles. They also specify penalty scaling, symmetry reductions, and the scope of the routing model.

Position variables encode which vertex occupies each cyclic position, with one-hot vertex, one-hot position, and graph-transition constraints defining Hamiltonian cycles.
A sufficiently large penalty A makes every constraint-violating assignment more expensive than every feasible Hamiltonian cycle.
Fixing the start vertex removes cyclic-shift redundancy; identifying it with the depot enables forced-variable reductions in the VRP encoding.
A feasible solution consists of exactly K nonempty depot-to-depot routes whose customer sets are disjoint and cover all customers.
The model is fixed-fleet, homogeneous, uncapacitated, and single-depot; capacities, heterogeneous vehicles, arrival times, and time windows are outside scope.

3 Degree-Only Arc Model and Connectivity Gap

The degree-only arc model enforces local visitation and depot-degree conditions but not global connectivity, allowing disconnected subtours. The paper demonstrates this mathematically and traces the same omission through reported and downstream formulations.

The degree-only Hamiltonian selects one incoming and outgoing arc per customer and K depot arcs in each direction, but does not guarantee K depot-rooted routes.
For N = 6 and K = 1, six cost-1 arcs form an optimal degree-feasible assignment of cost 6 yet split into two disconnected cycles, whereas any Hamiltonian cycle costs at least 24.
The resulting subtours are invalid VRP solutions that can nevertheless appear as low-energy states because they satisfy all local degree constraints.
A reported source-model matrix contains a depot-disconnected customer cycle with cost 128.545, below the connected matrix cost of 138.511.
The audited downstream TQE and QSVM Hamiltonians list MTZ-style conditions but omit corresponding connectivity penalties, while other reuse establishes formulation propagation without proving disconnected outputs.
A static Hamiltonian audit differs from a lazy-constraint algorithm, which requires its own separation, update, termination, and resource specifications.

4 Flow-Augmented QUBO Repair

The repair augments degree-based arc routing with capped single-commodity flow and quadratic support coupling, proving connected, cost-optimal ground-state routings under explicit penalty assumptions. It also quantifies qubit, interaction, gate, and workspace trade-offs against a position encoding.

Connectivity repair: Single-commodity flow enforces that every customer is connected to the depot through selected arcs.The proof uses customer-balance equations and support coupling to rule out unreachable customer sets and disconnected subtours.
Connectivity repair: Bitwise implication penalties enforce that flow can be nonzero only on selected routing arcs while preserving a quadratic QUBO encoding.The bounded flow word uses L = ⌈log2(N −K + 1)⌉ bits and requires no auxiliary slack variables.
Correctness: Under feasibility, nonnegative costs, and sufficiently strong penalties, every minimizing assignment encodes K nonempty depot-to-depot routes with minimum travel cost.Conversely, every optimal feasible routing has an admissible binary flow encoding in the ground eigenspace.
Resource accounting: The unreduced flow encoding uses exactly |E|(1 + L) logical problem qubits, with O(|E| log N) scaling except in the near-saturated fleet regime.Here L = ⌈log2(N −K + 1)⌉, and the formal Θ(|E|) boundary occurs only when K = N −O(1).
Resource accounting: A compute–phase–uncompute implementation uses O(N^2 log N + N log^2 N) logical gates on complete graphs with O(log N) reusable workspace and no product register.The gate count is a logical-operation upper bound, while omitted factors include depth, T-count, rotation synthesis, connectivity, precision, and error correction.

5 Position-Indexed Alternative

The position-indexed alternative concatenates depot-separated route blocks into a cyclic sequence, enforcing connectivity through ordering. Its dense-graph resource trade-offs include practical reductions, Θ(N^3) explicit QUBO size, and transition costs driven partly by forbidden arcs.

TSP specialization: For K = 1, feasible VRP routes and objective values coincide with fixed-depot TSP tours, although their unreduced QUBO polynomials differ on infeasible assignments.Forced-variable substitutions reduce the TSP register from N^2 to (N −1)^2 variables.
Position-indexed construction: The single-sequence model concatenates K route blocks cyclically, using depot occurrences as separators and route-block permutations to represent the same unordered routes.It places the depot at position 1 and assigns one binary variable xv,t to each node-position pair.
Position-indexed construction: Constraints visit each customer once, occupy every position once, fix the initial depot, enforce K depot occurrences, forbid disallowed transitions, and prevent consecutive depots.The no-consecutive-depot condition enforces nonempty routes across the cyclic boundary.
Resource counts and reductions: The unreduced position register has NT variables and therefore Θ(N^2) logical problem qubits, while fixing forced variables saves variables without changing feasible routes or objective values.The first reduction gives N(T −1) variables; the practical saving is not asymptotic over 1 ⩽ K ⩽ N −1.
Resource counts and reductions: Θ(N^3) quadratic-monomial occurrences arise from one-hot penalties and transition terms, whose worst-case order is Θ(TN^2) because forbidden arcs also contribute.Allowed-graph sparsity alone does not imply Θ(T|E|) transition complexity.
Resource counts and reductions: The position formulation’s gate bounds depend on the accounting model: direct termwise phase separation has the same asymptotic order as written terms, while reusable arithmetic computes and uncomputes residuals.The reusable-workspace construction uses signed O(log N)-qubit accumulators and reuses workspace across counting penalties.

6 Exact Verification and Hardware Characterization on Small Instances

Exact enumeration and audits verify the corrected Hamiltonian and implementation, while a 1,200-matrix benchmark quantifies when degree-only optima disconnect. IQM Emerald measurements characterize termwise circuits on the diagnostic instance without demonstrating quantum advantage.

Verification strategy: Four complementary checks combine exhaustive QUBO enumeration, a reversible-circuit audit, exact connectivity benchmarking, and a shallow hardware characterization.The checks address distinct validation questions and do not provide evidence of quantum advantage.
6.1 Exhaustive classical check of the flow correction: The sparse diagnostic uses 18 problem bits, and exhaustive evaluation of all 2^18 assignments finds a unique connected minimum of energy 22.The minimizer carries flows 3, 2, 1, 0 along the connected route’s selected arcs.
6.2 Functional audit of compute–phase–uncompute: The functional audit confirms scalar QUBO–circuit energy agreement and register cleanup, but it is not a QPU experiment or empirical proof of the asymptotic gate bound.The archived unoptimized decomposition is not the optimized ripple-carry implementation assumed in the resource analysis.
6.3 Systematic exact connectivity benchmark: Among 1,200 cost matrices and 7,800 matrix–fleet evaluations, disconnected optima become possible at N−K = 3.The benchmark uses exact Held–Karp and set-partition dynamic programming across metric and asymmetric instance families.
6.3 Systematic exact connectivity benchmark: At N−K = 3, strictly disconnected optima occur in 99.83% of metric instances and 5.50% of asymmetric instances.These frequencies describe the stated deterministic samples rather than a probability theorem or hardware experiment.
6.4 Termwise hardware characterization on the four-node diagnostic instance: In 2,000 selected p = 1 shots, 78.05% produced the degree-feasible disconnected ground state, while the reduced flow-augmented circuits produced no fully feasible sample.The device task used termwise Ising circuits, not the reversible arithmetic oracle, so it characterizes mapped Hamiltonians and compilation.

7 Conclusion and Outlook

The paper repairs connectivity defects in degree-only arc VRP Hamiltonians with a flow-augmented QUBO and proves ground-state correctness under explicit penalty assumptions. Audits and hardware characterization expose the gap between low energy, connectivity correctness, and feasible sampling.

Conclusion and Outlook: Local degree penalties permit depot-disconnected customer cycles, so zero-penalty assignments can represent infeasible routing plans.The audited source model contains a cheaper disconnected degree-feasible subgraph, and the benchmark shows this is not only a constructed example.
Conclusion and Outlook: The flow repair uses capped per-arc registers, bitwise arc-flow coupling, and explicit penalty assumptions to guarantee feasibility equivalence and ground-state correctness.The construction carries the range 0,...,N-K into the flow register and separates problem-qubit, interaction, and reversible-oracle resources.
Conclusion and Outlook: On complete graphs, written quadratic occurrences scale as Θ(N^3L^2), while workspace-reusing reversible evaluation uses O(N^2 log N + N log^2 N) logical gates.The reversible construction uses O(log N) reusable workspace without a separate product register or materialized dense expansion.
Conclusion and Outlook: The single-sequence position encoding uses fewer problem qubits and written terms than the flow encoding when the flow-word length grows on complete loopless graphs.Its written-occurrence count is Θ(N^3), compared with Θ(N^3L^2) for flow; vehicle-indexed position encodings can have different resource ordering.
Conclusion and Outlook: The local audit checks exhaustive energy agreement, phase accumulation, and work-register cleanup, but does not empirically validate the optimized asymptotic gate bound.The hardware task used termwise Ising compilation rather than the reversible compute–phase–uncompute realization.
Conclusion and Outlook: In the degree-only model, 78.05% of selected-circuit shots were the invalid disconnected ground state, while the reduced flow-augmented circuits produced no fully feasible sample in 12,000 shots.These device results characterize mapped Hamiltonians and compilation, not an asymptotic routing solution advantage.
Conclusion and Outlook: The conclusions are limited to fixed-fleet, homogeneous, uncapacitated routing with nonnegative arc costs and do not provide general physical-resource or fault-tolerant estimates.The paper identifies capacity, timing, heterogeneous-fleet, hardware-connectivity, noise, memory, and rotation-precision comparisons as future work.