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

AI summary

Overview

Research area: Quantum optimization / combinatorial optimization — specifically QUBO and Ising formulations of vehicle routing problems, their mathematical correctness, and their circuit-level resource costs.

Technical level: Advanced. The paper assumes familiarity with QUBO/Ising Hamiltonians, penalty methods, single-commodity flow formulations, reversible arithmetic, and gate-count accounting.

Scope (one sentence): The paper identifies a missing-connectivity defect in a published degree-only arc-based QUBO for fixed-fleet vehicle routing, constructs a polynomial-size single-commodity-flow repair with a ground-state correctness theorem, and compares its qubit, interaction, and gate costs against a position-indexed encoding, including a small hardware characterization.

What This Paper Is About

Arc-based QUBO formulations of vehicle routing typically enforce only local degree constraints: every customer gets one incoming and one outgoing selected arc, and the depot gets exactly K of each. The authors show that these local equations define only a cycle cover, so a ground state can contain customer-only cycles that are disconnected from the depot — an infeasible delivery plan, not just an alternative optimum. The paper's goal is to repair that specific published model with a compact, provably correct flow-based penalty layer that fits a single static QUBO, and to quantify the resource trade-offs of doing so.

Key Contributions

1. An equation-level audit of the connectivity gap. The authors reconstruct the failure in the degree-only arc Hamiltonian of Azad et al. from the displayed constraints themselves, give a fully specified counterexample, and classify follow-on works (Mohanty et al., Alsaiyari and Felemban, Niu et al., Jaroszczuk) by whether their stated Hamiltonians actually contain a connectivity term.

2. A polynomial-size QUBO repair using capped single-commodity flow. Each arc flow is encoded in L = ⌈log₂(N−K+1)⌉ bits based on the tight fixed-fleet cap U = N−K, with capacity enforced by a purely quadratic bitwise support penalty instead of slack variables. The unreduced encoding uses exactly |E|(1 + ⌈log₂(N−K+1)⌉) logical problem qubits.

3. A ground-state correctness theorem (Theorem 1). Under an explicit penalty bound, P = min{A, A_f, A_c} > B(N−1+K)c_max, every minimizing assignment of the flow-augmented Hamiltonian encodes an optimal feasible collection of K nonempty depot-to-depot routes, and every optimal feasible routing has at least one minimizing binary flow encoding.

4. A reversible phase-oracle construction and a position-encoding comparison. Rather than materializing the static quadratic expansion of Θ(N³L²) Pauli interactions, the authors adapt program-based reversible arithmetic to evaluate flow penalties in O(N² log N + N log² N) logical gates on a complete graph with O(log N) reusable workspace and no product register. They also analyze a position encoding with NT variables (T = N+K−1) and Θ(NT² + TN²) quadratic terms.

Main Findings

• The gap is real and already visible in published output. In Experiment 2 of Azad et al., the adjacency matrix A₂ in their Eq. (34) contains the customer-only cycle 2 → 3 → 2 disconnected from depot 0, alongside the routes 0 → 1 → 0 and 0 → 4 → 0. It is reported at cost 128.545, below the 138.511 cost of the connected matrix A₃ in their Eq. (35).

• An explicit minimal counterexample. For N = 6 and K = 1 on the complete loopless directed graph, assigning cost 1 to the six arcs in F = {(1,2),(2,3),(3,1),(4,5),(5,6),(6,4)} and cost 10 to all others yields an optimal degree-feasible assignment of cost 6 that splits into the disconnected cycles 1 → 2 → 3 → 1 and 4 → 5 → 6 → 4, whereas any Hamiltonian cycle costs at least 2·10 + 4·1 = 24.

• Reuse is not inheritance. Mohanty et al. list MTZ-style inequalities in Eq. (17) and Eq. (23) but their Hamiltonians in Eq. (18) and Eq. (24) contain no corresponding term. Alsaiyari and Felemban display the same arc objective and four degree/depot equations in Eqs. (1)–(5) with no connectivity condition and benchmark VQE and QAOA on instances (3,2), (4,2), and (5,2). Niu et al. reproduce the five-term Hamiltonian without a connectivity term in a review.

• The flow repair is correct, not just heuristic. Lemma 1 proves that flow support plus unit customer consumption implies depot reachability of every customer; Theorem 1 then upgrades this to exact ground-state correctness for the full QUBO. Summing the customer balance residuals automatically gives the depot balance, so no separate squared depot term is needed — a written-interaction saving with the same zero-penalty set.

• Encoding trade-offs depend on what you count. On complete loopless graphs, the position encoding uses fewer problem qubits and fewer written terms once the number of bits per flow register grows, and under the same reversible accounting model the flow formulation admits a smaller upper bound on logical gates. The authors stress that variable count, expanded interaction count, and reversible implementation cost need not rank the encodings in the same order.

• Benchmarking. Exact audits of the Hamiltonian and circuit implementation were combined with a classical benchmark of 1,200 cost matrices, which verifies the formulation and quantifies the connectivity gap.

• Hardware characterization. A 32,000-shot Amazon Braket task on IQM Emerald probed 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. The authors are explicit that these results characterize mapped Hamiltonians and compilation, not an asymptotic advantage in solving routing problems.

• Reductions that are safe and reductions that are not. Fixing the initial depot column in the position encoding saves exactly N variables. For K = 1, further eliminating depot variables gives the same feasible tours and objective values as fixed-depot TSP, but it does not make the unreduced Hamiltonians polynomials identical.

• Not reported. Physical-qubit counts, embedding and routing overheads, fitting-synthesis costs, and fault-tolerance overheads are treated as hardware dependent and are excluded from the stated accounting.

Methodology in Plain English

The authors work in three layers.

First, they read the published equations rather than citing them. They compare what each follow-on paper says about subtour elimination with what its displayed Hamiltonian actually minimizes, and they build a small routing instance where the cheap answer is provably the wrong one.

Second, they import a classical trick from operations research. Single-commodity flow sends a phantom delivery quantity out of the depot that is consumed one unit per customer. If a customer cannot be reached from the depot, the flow bookkeeping becomes impossible — the sum over the unreachable set reads zero-in minus nonnegative-out equals a positive number, a contradiction. To put this in QUBO form, they cap each arc's flow at N−K (the longest possible single route when there are K nonempty routes) and write the flow in binary bits. Coupling flow to route selection becomes a simple penalty on "flow bit is 1 but the arc is not selected," which is quadratic and needs no slack variables.

Third, they separate three resource ledgers: logical problem qubits, written Hamiltonian terms, and the reversible circuit that computes the penalty phases. For the circuit, they compute flow-balance residuals with reusable ancillas and uncompute them, rather than expanding the full Θ(N³L²) Pauli interaction list. They validate the formulation with exact audits, a classical benchmark over 1,200 cost matrices, and a small run on IQM Emerald through Amazon Braket.

Why This Matters

Impact on research. The paper shows that a widely reused arc-based VRP Hamiltonian is not connectivity-correct as published, and that citations to it do not guarantee the connectivity condition was carried into later Hamiltonians. It supplies a proof-carrying repair with explicit penalty bounds, and it argues that encoding comparisons are only meaningful when qubit count, interaction count, and circuit cost are reported separately — a methodological point for the whole quantum-optimization benchmarking literature.

Real-world applications:

• Logistics and last-mile delivery: fixed-fleet dispatch where exactly K vehicles must each run a nonempty depot-to-depot route.
• Service technician and field-maintenance scheduling: routing a known number of crews from a single depot.
• Multiple traveling-salesperson planning: the paper notes this equivalence explicitly.
• Benchmark integrity for quantum-hardware vendors and algorithm developers: the diagnostic N = 4, K = 1 instance and the reported shot statistics give a concrete infeasibility check for mapped Ising circuits.

Industry relevance. Any pipeline that maps a routing QUBO onto annealers or variational hardware inherits the feasibility properties of the Hamiltonian it starts from. A ground state that silently encodes a disconnected cycle would be deployed as a delivery plan. The paper's explicit penalty condition, its bitwise support construction, and its reporting of hardware-level infeasibility rates give practitioners concrete tools for auditing such pipelines.

Future Directions

• Hardware-aware ranking of encodings. The authors note that the number of binary variables, the expanded interaction count, and the reversible implementation cost need not order the encodings the same way, leaving open which encoding wins once rotation synthesis, device connectivity, and embedding overheads are included.

• Beyond the fixed-fleet, uncapacitated, single-depot case. Capacities, heterogeneous vehicles, physical arrival times, and time windows are explicitly outside the model; general customer demands q_i are said to be incorporable "at the cost of additional bookkeeping," which remains to be worked out and analyzed.

• Better sampling on the repaired circuit. The reduced 14-qubit flow-augmented circuit produced no fully feasible sample at depth one, so improving compilation or ansatz design for the flow-augmented Hamiltonian is an open engineering question.

• Static Hamiltonian versus iterative constraint generation. The paper distinguishes its single static QUBO from lazy-constraint loops that detect disconnected samples and add penalties iteratively, noting such procedures need their own separation rule, update and termination specification, and resource analysis.

Target Audience

Researchers and graduate students in quantum optimization and quantum algorithms who work with QUBO/Ising formulations of routing and scheduling problems; operations-research practitioners interested in how classical single-commodity-flow ideas translate into quadratic binary models; and quantum-hardware and compiler engineers who need precise, auditable resource ledgers and diagnostic instances rather than headline speedup claims. Readers seeking an introductory treatment of QAOA or quantum annealing will find the paper's level of formulation detail demanding.

Authors’ abstract

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 compute-phase-uncompute implementation evaluates the flow penalties in $O(N^2\log N+N\log^2N)$ logical gates on a complete graph, using $O(\log N)$ reusable workspace and no product register. On complete loopless graphs, a position encoding that arranges all routes in one sequence separated by depot occurrences uses fewer problem qubits and written terms when the number of bits per flow register grows. Under the same reversible accounting model, the flow formulation admits a smaller logical-gate upper bound. Exact Hamiltonian and circuit audits and a benchmark of 1,200 cost matrices verify the formulation and quantify the connectivity gap. A 32,000-shot Amazon Braket task on IQM Emerald characterizes depth-one termwise Ising circuits for a diagnostic $N=4$, $K=1$ counterexample. 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, not an asymptotic advantage in solving routing problems.