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

• URL: http://arxiv.org/abs/2608.26894v1
• Date: Thu, 27 Aug 2026 09:48:35 GMT
• Title: Correcting Connectivity in Arc-Based QUBO Models for Fixed-Fleet Vehicle Routing
• Abstract summary: We revisit a degree-only arc Hamiltonian for fixed-fleet, homogeneous, uncapacitated vehicle routing.<n>Because its local penalties define only a quadratic cycle cover, ground states may contain customer cycles disconnected from the depot.<n>We prove that every ground-state routing is connected and cost-optimal under explicit penalty assumptions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians [4.914113120082008]
  We study the cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford$+T$ model.<n>Our main technical tool is an ancilla-compression theorem: any block encoding of an $n$-qubit operator with $a$ clean ancillas and at most $s$ $T$ gates can be compressed to use at most $mina,n+2s$ ancillas.
  arXiv  Detail & Related papers  (2026-09-10T07:01:08Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Restrictions on non-Clifford fault tolerance and ruling out beyond-SQL quantum metrology [0.0]
  A potential route around known no-go results is to encode sensors in a quantum code where the physical signal acts inducely as a logical gate.<n>We show that single-qubit rotations by a small angle $$ can only be fault-tolerantly reconstructed from low-weight normalizer measurements.<n>We also prove a broader metrological no-go that avoids the assumptions of the quantum Cramér-Rao bound: constant-strength signal-aligned noise rules out any advantage over computation in AC or DC sensing.
  arXiv  Detail & Related papers  (2026-07-29T18:01:14Z)
• Compander-Aligned Query Geometry for Quantized Zeroth-Order Optimization [12.92201130466754]
  CAQ-ZO forms one-grid-step Rademacher stencils $z pm r$ in $z = (x)$, maps endpoints back through $-1$, and updates in $z$.<n>Our theory proves the grid-spanarity, decomposes endpoint-rounding estimator residuals, and gives station bounds in which generic off-grid queries retain a $2/2$ residual channel while CAQ-ZO makes the query-time residual exactly zero.
  arXiv  Detail & Related papers  (2026-05-11T14:55:20Z)
• Coherent Rollout Oracles for Finite-Horizon Sequential Decision Problems [0.0]
  Coherent quantum rollout for sequential decision problems requires a unitary simulator.<n>With branch-dependent valid actions, this mapping is totalized coherent rank-select over an entangled $N-bit mask.<n>We give the first reversible-circuit complexity analysis of this primitive.
  arXiv  Detail & Related papers  (2026-04-28T00:46:37Z)
• INC: An Indirect Neural Corrector for Auto-Regressive Hybrid PDE Solvers [61.84396402100827]
  We propose the Indirect Neural Corrector ($mathrmINC$), which integrates learned corrections into the governing equations.<n>$mathrmINC$ reduces the error amplification on the order of $t-1 + L$, where $t$ is the timestep and $L$ the Lipschitz constant.<n>We test $mathrmINC$ in extensive benchmarks, covering numerous differentiable solvers, neural backbones, and test cases ranging from a 1D chaotic system to 3D turbulence.
  arXiv  Detail & Related papers  (2025-11-16T20:14:28Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Fast quantum circuit cutting with randomized measurements [0.0]
  We propose a new method to extend the size of a quantum computation beyond the number of physical qubits available on a single device. This is accomplished by randomly inserting measure-and-prepare channels to express the output state of a large circuit as a separable state across distinct devices.
  arXiv  Detail & Related papers  (2022-07-29T15:13:04Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
  We show that mixability can be a powerful tool to obtain algorithms with optimal regret. The resulting methods often suffer from high computational complexity which has reduced their practical applicability.
  arXiv  Detail & Related papers  (2021-10-08T08:22:05Z)
• Exponential Error Suppression for Near-Term Quantum Devices [0.0]
  In NISQ era, complexity and scale required to adopt even the smallest QEC is prohibitive. We show that for the crucial case of estimating expectation values of observables one can indeed achieve an effective exponential suppression.
  arXiv  Detail & Related papers  (2020-11-11T18:00:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.