Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.26894

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

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

quant-phcs.DSmath.OCSubmitted Aug 27, 2026• Announced Aug 28, 2026• 0 citations• Revised Oct 4, 2026 (v2)
v1 · Aug 27, 2026v2 · Oct 4, 2026
arXivHTMLPDF

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.

Comments
29 pages, 3 figures, 5 tables. Reproducibility package: https://doi.org/10.5281/zenodo.21595142

Related papers

Cooperative Platoon Routing and Dispatching via Edge-Assisted Hybrid Quantum Optimization

Talha Azfar, Ruimin Ke

Cooperative platooning can reduce the energy use of Connected and Autonomous Vehicle (CAV) fleets, but the routing problem becomes difficult when vehicles must meet on the same road segments at compatible times while moving through unstable urban traffic. This paper develops an edge-assisted, closed-loop evaluation pipeline for platooning-aware vehicle routing. Roadside Units estimate local traffic kinematics from video, classify segment-level flow stability, and activate platooning rewards only on road segments where close-gap coordination is physically appropriate. The resulting multi-vehicle routing problem is written directly as a Quadratic Unconstrained Binary Optimization (QUBO) model, so pairwise platooning interactions are represented as native quadratic Ising terms instead of requiring auxiliary MILP linearization variables. We evaluate the framework using a 24-hour microscopic SUMO simulation of Troy, NY, together with localized IBM Quantum hardware benchmarks. The SUMO study shows an $18.5\%$ reduction in fleet tractive-energy demand relative to a non-cooperative baseline. On 25-active-qubit benchmark instances executed on $\texttt{ibm_boston}$, Linear-Chain QAOA reduces two-qubit CNOT depth by $66.7\%$ compared with dense QAOA and samples the exact classical ground state with $P_{\text{feas}} = 38.6\%$ and $P_{\text{opt}} = 14.2\%$ at $p=2$. These results suggest that edge perception and shallow quantum optimization can work together as a useful component of closed-loop CAV platoon dispatching.

quant-pharXiv:2608.00524•Aug 4, 2026

Hardware-Aware Sparse QUBO Encoding for CVRPTW on Coherent Ising Machines: An LKH-Guided Variable-Compression Framework

Zhitao Wu, Zonglin Yang, Jie Zhou +2 more

Capacitated vehicle routing with time windows (CVRPTW) is a natural target for coherent Ising machines (CIMs), but a direct multi-vehicle arc encoding scales as O(mN2) and exceeds the variable budget of current CIM-compatible systems. We argue the bottleneck is encoding density, not expressiveness, and present LSQ, a hardware-aware sparse Quadratic Unconstrained Binary Optimization (QUBO) framework that decouples CVRPTW into a compact customer-to-route assignment QUBO and a classical intra-route ordering step under a soft no-wait service convention. LKH candidate edges compress the per-route edge space from O(N2) to O(KN), and a per-route dynamic-penalty subroutine encodes time-window sensitivities as binary variables in a round-wise outer loop. On a six-vehicle, 51-node reference instance curated from long-term operational data, LSQ shrinks the maximum single-submission QUBO from 15,300 arc variables to 342 logicalQUBOvariables (∼45× compression), cuts travel time by 22.9% (74 vs. 96), and cuts route duration by 11.2% (174 vs. 196) against an OR-Tools soft-window baseline at the same fleet size. OR-Tools retains an advantage on raw time-window penalty (1600 vs. 3540) and runtime; under the scalar operational cost ∑kT(πk)+∑iℓi(τi), OR-Tools is therefore the better single-objective solver, and the comparison is a multi-objective trade-off rather than a scalar dominance claim. Ablations confirm that the LKH prior recovers Held–Karp on a 15-customer TSP at 53 vs. 120 variables and that the dynamic-penalty encoding reduces compressed time-window loss by 15.25% at constant travel. All hardware claims refer to QUBO sizing on a Kaiwu/CIM-compatible backend, not physical CIM execution.

Algorithms•Jun 29, 2026•0 citations

Feasibility-Preserving Quantum Search for Constrained Transportation Routing

Dahye Kim, Monika Filipovska

Transportation routing problems such as the Traveling Salesperson Problem (TSP) and the Vehicle Routing Problem (VRP) are characterized by strict feasibility requirements involving customer assignment and visit rules, route sequencing, and depot-return logic alongside cost minimization. Most quantum routing formulations adopt Quadratic Unconstrained Binary Optimization (QUBO) encodings, where feasibility is incorporated indirectly via penalty terms in the cost Hamiltonian. While convenient for standard implementations of the Quantum Approximate Optimization Algorithm (QAOA), QUBO encodings allow the quantum search dynamics to allocate substantial probability to infeasible route configurations. This study develops a transportation-grounded constraint-aware Quantum Alternating Operator Ansatz (QAOA+) framework that embeds feasibility-preserving logic directly into the search operator. We introduce a custom mixer that functions as a quantum analogue of feasibility-preserving routing neighborhoods, using column-wise swap moves, it restricts evolution to feasible configurations while enabling structured exploration of valid routes. We compare three constraint-handling architectures: penalty-based QUBO QAOA, penalty free QAOA+ with the feasibility-preserving mixer, and a Hybrid QAOA+ combining mixer based feasibility with and penalty guidance. Results on small TSP and VRP instances show that constraint-handling architecture strongly influences feasible-route sampling, convergence behavior, and probability concentration over low-cost feasible routes. These findings position constraint-aware quantum search as a methodological extension of transportation routing search approaches, where feasibility is enforced through admissible quantum transitions rather than post-hoc penalties.

quant-pharXiv:2608.05394•Aug 7, 2026•0 citations

Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations

Chinonso Onah, Kristel Michielsen

We formulate a global-position colored-permutation encoding for the capacitated vehicle routing problem. Each of the $K$ vehicles selects a disjoint partial permutation, and the sum of these $K$ color layers forms a full $n\times n$ permutation matrix that assigns every customer to exactly one visit position. This representation uses $n^2K$ binary decision variables arranged as $K$ color layers over a common permutation structure, while vehicle capacities are enforced by weighted sums over the entries of each color class, requiring no explicit load register and hence no extra logical qubits beyond the routing variables. In contrast, many prior quantum encodings introduce an explicit capacity or load representation with additional qubits. Our construction is designed to exploit the Constraint-Enhanced QAOA framework together with its encoded-manifold analyses. Building on a requirements-based view of quantum utility in CVRP, we develop a routing optimization formulation that directly targets one of the main near-term bottlenecks, namely the additional logical-qubit cost of vehicle labels and explicit capacity constraints. Our proposal shows strong algorithmic performance in addition to qubit efficiency. On a standard benchmark suite, our end-to-end pipeline recovers the independently verified optima. The feasibility oracle may also be of independent interest as a reusable polynomial-time decoding and certification primitive for quantum and quantum-inspired routing pipelines.

quant-pharXiv:2604.04570•Apr 7, 2026•5 citations

Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations

Chinonso Onah, Kristel F. L. Michielsen

Abstract We formulate a global-position colored-permutation encoding for the capacitated vehicle routing problem. Each of the K vehicles selects a disjoint partial permutation, and the sum of these K color layers forms a full n × n permutation matrix that assigns every customer to exactly one visit position. On the benchmark suite of [1], our end-to-end pipeline recovers the independently verified optima. This representation uses n2K binary decision variables arranged as K color layers over a common permutation structure, while vehicle capacities are enforced by weighted sums over the entries of each color class—requiring no explicit load register, and hence no extra logical qubits, beyond the routing variables. In contrast, prior quantum encodings introduce an explicit capacity/load representation with O(Q) or O(logQ) additional qubits for capacity Q [2, 3, 4, 5]. Our construction is designed to exploit the Constraint-Enhanced QAOA (CE-QAOA) framework [6] together with its encoded-manifold analyses [6, 7, 8]. Building on our recent requirements analysis of quantum utility in CVRP [9], we develop a routing optimization formulation that directly targets one of the main near-term bottlenecks, namely the additional logical-qubit cost of vehicle labels and explicit capacity constraints. Our proposal shows strong algorithmic performance in addition to qubit efficiency. All results are fully reproducible from the companion artifact archive in Ref. [10]. The feasibility oracle introduced in Alg. 3 may also be of independent interest as a reusable polynomial-time decoding and certification primitive for quantum and quantum-inspired routing pipelines.1

•Jun 12, 2026•0 citations

Enhancing vehicle routing problem through a qubit-efficient Symmetric Arc Reduction using Quantum Approximate Optimization Algorithm

Jayaraja A, Senthil Kumaran U

Introduction Finding the most efficient routes for a fleet of delivery vehicles remains a critical and costly challenge for nearly any logistics business. This core idea is known as the Vehicle Routing Problem (VRP). The primary goal is to minimize operational costs, such as the total travel distance or the number of trucks deployed, while ensuring all the customers are served. Because VRP is NP-hard, finding a perfect solution is often impossible, forcing industries to rely on classical approximate algorithms. However, quantum variational algorithms offer a new paradigm by iteratively optimizing parameters to navigate the solution space, presenting a new and promising avenue for finding better and faster solutions. Methods In this paper, we introduce Symmetric Arc Reduction in Quantum Approximate Optimization Algorithm (SAR-QAOA), which systematically eliminates redundant symmetric routing variables in the binary integer programming formulation prior to the Quadratic Unconstrained Binary Optimization (QUBO) formulation. The proposed SAR-QAOA encodes edge-based VRP while reducing the qubit requirement from n ( n −1) to n ( n −1)/2, thereby improving the resource efficiency of the QUBO formulation by prioritizing regions of the solution space that are more likely to contain high-quality solutions; SAR enhances both search accuracy and computational efficiency. Results Experimental results on noiseless quantum simulators validate the feasibility of the proposed formulation and its integration with the QAOA framework, providing a promising foundation for future investigations on larger routing problems and evolving quantum hardware.

Frontiers in Artificial Intelligence•Oct 1, 2026•0 citations
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−1N-1N−1 customers and KKK nonempty routes, the unreduced encoding uses exactly ∣E∣(1+⌈log⁡2(N−K+1)⌉)|E|(1+\lceil\log_2(N-K+1)\rceil)∣E∣(1+⌈log2​(N−K+1)⌉) logical problem qubits. A reversible compute-phase-uncompute implementation evaluates the flow penalties in O(N2log⁡N+Nlog⁡2N)O(N^2\log N+N\log^2N)O(N2logN+Nlog2N) logical gates on a complete graph, using O(log⁡N)O(\log N)O(logN) 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=4N=4N=4, K=1K=1K=1 counterexample. In the degree-only circuit, 78.05% of selected p=1p=1p=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.
Cooperative platooning can reduce the energy use of Connected and Autonomous Vehicle (CAV) fleets, but the routing problem becomes difficult when vehicles must meet on the same road segments at compatible times while moving through unstable urban traffic. This paper develops an edge-assisted, closed-loop evaluation pipeline for platooning-aware vehicle routing. Roadside Units estimate local traffic kinematics from video, classify segment-level flow stability, and activate platooning rewards only on road segments where close-gap coordination is physically appropriate. The resulting multi-vehicle routing problem is written directly as a Quadratic Unconstrained Binary Optimization (QUBO) model, so pairwise platooning interactions are represented as native quadratic Ising terms instead of requiring auxiliary MILP linearization variables. We evaluate the framework using a 24-hour microscopic SUMO simulation of Troy, NY, together with localized IBM Quantum hardware benchmarks. The SUMO study shows an 18.5%18.5\%18.5% reduction in fleet tractive-energy demand relative to a non-cooperative baseline. On 25-active-qubit benchmark instances executed on $\texttt{ibm_boston}$, Linear-Chain QAOA reduces two-qubit CNOT depth by 66.7%66.7\%66.7% compared with dense QAOA and samples the exact classical ground state with Pfeas=38.6%P_{\text{feas}} = 38.6\%Pfeas​=38.6% and Popt=14.2%P_{\text{opt}} = 14.2\%Popt​=14.2% at p=2p=2p=2. These results suggest that edge perception and shallow quantum optimization can work together as a useful component of closed-loop CAV platoon dispatching.
Capacitated vehicle routing with time windows (CVRPTW) is a natural target for coherent Ising machines (CIMs), but a direct multi-vehicle arc encoding scales as O(mN2) and exceeds the variable budget of current CIM-compatible systems. We argue the bottleneck is encoding density, not expressiveness, and present LSQ, a hardware-aware sparse Quadratic Unconstrained Binary Optimization (QUBO) framework that decouples CVRPTW into a compact customer-to-route assignment QUBO and a classical intra-route ordering step under a soft no-wait service convention. LKH candidate edges compress the per-route edge space from O(N2) to O(KN), and a per-route dynamic-penalty subroutine encodes time-window sensitivities as binary variables in a round-wise outer loop. On a six-vehicle, 51-node reference instance curated from long-term operational data, LSQ shrinks the maximum single-submission QUBO from 15,300 arc variables to 342 logicalQUBOvariables (∼45× compression), cuts travel time by 22.9% (74 vs. 96), and cuts route duration by 11.2% (174 vs. 196) against an OR-Tools soft-window baseline at the same fleet size. OR-Tools retains an advantage on raw time-window penalty (1600 vs. 3540) and runtime; under the scalar operational cost ∑kT(πk)+∑iℓi(τi), OR-Tools is therefore the better single-objective solver, and the comparison is a multi-objective trade-off rather than a scalar dominance claim. Ablations confirm that the LKH prior recovers Held–Karp on a 15-customer TSP at 53 vs. 120 variables and that the dynamic-penalty encoding reduces compressed time-window loss by 15.25% at constant travel. All hardware claims refer to QUBO sizing on a Kaiwu/CIM-compatible backend, not physical CIM execution.
Transportation routing problems such as the Traveling Salesperson Problem (TSP) and the Vehicle Routing Problem (VRP) are characterized by strict feasibility requirements involving customer assignment and visit rules, route sequencing, and depot-return logic alongside cost minimization. Most quantum routing formulations adopt Quadratic Unconstrained Binary Optimization (QUBO) encodings, where feasibility is incorporated indirectly via penalty terms in the cost Hamiltonian. While convenient for standard implementations of the Quantum Approximate Optimization Algorithm (QAOA), QUBO encodings allow the quantum search dynamics to allocate substantial probability to infeasible route configurations. This study develops a transportation-grounded constraint-aware Quantum Alternating Operator Ansatz (QAOA+) framework that embeds feasibility-preserving logic directly into the search operator. We introduce a custom mixer that functions as a quantum analogue of feasibility-preserving routing neighborhoods, using column-wise swap moves, it restricts evolution to feasible configurations while enabling structured exploration of valid routes. We compare three constraint-handling architectures: penalty-based QUBO QAOA, penalty free QAOA+ with the feasibility-preserving mixer, and a Hybrid QAOA+ combining mixer based feasibility with and penalty guidance. Results on small TSP and VRP instances show that constraint-handling architecture strongly influences feasible-route sampling, convergence behavior, and probability concentration over low-cost feasible routes. These findings position constraint-aware quantum search as a methodological extension of transportation routing search approaches, where feasibility is enforced through admissible quantum transitions rather than post-hoc penalties.
We formulate a global-position colored-permutation encoding for the capacitated vehicle routing problem. Each of the KKK vehicles selects a disjoint partial permutation, and the sum of these KKK color layers forms a full n×nn\times nn×n permutation matrix that assigns every customer to exactly one visit position. This representation uses n2Kn^2Kn2K binary decision variables arranged as KKK color layers over a common permutation structure, while vehicle capacities are enforced by weighted sums over the entries of each color class, requiring no explicit load register and hence no extra logical qubits beyond the routing variables. In contrast, many prior quantum encodings introduce an explicit capacity or load representation with additional qubits. Our construction is designed to exploit the Constraint-Enhanced QAOA framework together with its encoded-manifold analyses. Building on a requirements-based view of quantum utility in CVRP, we develop a routing optimization formulation that directly targets one of the main near-term bottlenecks, namely the additional logical-qubit cost of vehicle labels and explicit capacity constraints. Our proposal shows strong algorithmic performance in addition to qubit efficiency. On a standard benchmark suite, our end-to-end pipeline recovers the independently verified optima. The feasibility oracle may also be of independent interest as a reusable polynomial-time decoding and certification primitive for quantum and quantum-inspired routing pipelines.
Abstract We formulate a global-position colored-permutation encoding for the capacitated vehicle routing problem. Each of the K vehicles selects a disjoint partial permutation, and the sum of these K color layers forms a full n × n permutation matrix that assigns every customer to exactly one visit position. On the benchmark suite of [1], our end-to-end pipeline recovers the independently verified optima. This representation uses n2K binary decision variables arranged as K color layers over a common permutation structure, while vehicle capacities are enforced by weighted sums over the entries of each color class—requiring no explicit load register, and hence no extra logical qubits, beyond the routing variables. In contrast, prior quantum encodings introduce an explicit capacity/load representation with O(Q) or O(logQ) additional qubits for capacity Q [2, 3, 4, 5]. Our construction is designed to exploit the Constraint-Enhanced QAOA (CE-QAOA) framework [6] together with its encoded-manifold analyses [6, 7, 8]. Building on our recent requirements analysis of quantum utility in CVRP [9], we develop a routing optimization formulation that directly targets one of the main near-term bottlenecks, namely the additional logical-qubit cost of vehicle labels and explicit capacity constraints. Our proposal shows strong algorithmic performance in addition to qubit efficiency. All results are fully reproducible from the companion artifact archive in Ref. [10]. The feasibility oracle introduced in Alg. 3 may also be of independent interest as a reusable polynomial-time decoding and certification primitive for quantum and quantum-inspired routing pipelines.1
Introduction Finding the most efficient routes for a fleet of delivery vehicles remains a critical and costly challenge for nearly any logistics business. This core idea is known as the Vehicle Routing Problem (VRP). The primary goal is to minimize operational costs, such as the total travel distance or the number of trucks deployed, while ensuring all the customers are served. Because VRP is NP-hard, finding a perfect solution is often impossible, forcing industries to rely on classical approximate algorithms. However, quantum variational algorithms offer a new paradigm by iteratively optimizing parameters to navigate the solution space, presenting a new and promising avenue for finding better and faster solutions. Methods In this paper, we introduce Symmetric Arc Reduction in Quantum Approximate Optimization Algorithm (SAR-QAOA), which systematically eliminates redundant symmetric routing variables in the binary integer programming formulation prior to the Quadratic Unconstrained Binary Optimization (QUBO) formulation. The proposed SAR-QAOA encodes edge-based VRP while reducing the qubit requirement from n ( n −1) to n ( n −1)/2, thereby improving the resource efficiency of the QUBO formulation by prioritizing regions of the solution space that are more likely to contain high-quality solutions; SAR enhances both search accuracy and computational efficiency. Results Experimental results on noiseless quantum simulators validate the feasibility of the proposed formulation and its integration with the QAOA framework, providing a promising foundation for future investigations on larger routing problems and evolving quantum hardware.