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

• The paper audits the published arc Hamiltonian and related downstream formulations by comparing displayed constraints with the Hamiltonians they actually minimize.Source: §1 · p. 2
• Degree constraints alone permit customer cycles disconnected from the depot, making some ground states infeasible transportation plans.Source: §1 · pp. 1–2
• 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.Source: §1 · p. 2
• Under explicit penalty bounds, the repair provides ground-state correctness while separating logical qubits, written interactions, and reversible-oracle resources.Source: §1 · p. 2
• 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.Source: §1 · pp. 2–3

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

• 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.Source: §3.1 · pp. 5–6
• 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.Source: §3.1 · p. 6, Figure 1 · p. 6
• The resulting subtours are invalid VRP solutions that can nevertheless appear as low-energy states because they satisfy all local degree constraints.Source: §3.1 · p. 6
• A reported source-model matrix contains a depot-disconnected customer cycle with cost 128.545, below the connected matrix cost of 138.511.Source: §3.2 · p. 6
• 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.Source: §3.2 · pp. 6–7
• A static Hamiltonian audit differs from a lazy-constraint algorithm, which requires its own separation, update, termination, and resource specifications.Source: §3.2 · p. 7

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.Source: §4.1 · pp. 7–8, §4.2 · p. 10
• 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.Source: §4.1 · p. 8, §4.2 · p. 9

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.Source: §4.2 · pp. 9–10

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).Source: §4.2 · pp. 10–11
• 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.Source: §4.2 · p. 12

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.Source: §5 · pp. 13, 15, §5.1 · p. 17

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.Source: §5 · pp. 13–14
• 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.Source: §5 · p. 14

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.Source: §5 · p. 15, §5.1 · p. 16
• Θ(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.Source: §5 · pp. 15–16
• 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.Source: Table 1 · p. 13, §5 · p. 16

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.Source: §6 · p. 18

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.Source: §6.1 · p. 18

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.Source: §6.2 · p. 19

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.Source: §6.3 · p. 19
• 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.Source: §6.3 · pp. 19–20

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.Source: §6.4 · pp. 22–23

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.Source: §7 · p. 24
• 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.Source: §7 · p. 24
• 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.Source: §7 · pp. 24–25
• 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.Source: §7 · p. 25
• 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.Source: §7 · p. 25
• 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.Source: §7 · p. 25
• 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.Source: §7 · p. 25