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:2604.04570

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

Chinonso Onah, Kristel Michielsen

quant-phcs.CCcs.DMcs.ITmath-phSubmitted Apr 6, 2026• Announced Apr 7, 2026• 0 citations
v1 · Apr 6, 2026v2 · Apr 29, 2026v3 · May 4, 2026
arXivHTMLPDF

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\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.

Related papers

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

Data and Implementation: Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored Permutations

Chinonso Onah

We formulate capacitated vehicle routing as a colored permutation problem: each of the K vehicles selects a disjoint partial permutation, and the sum of these K submatrices forms a full n × n permutation matrix that assigns everycustomer to exactly one visit position. This representation requires no explicit load register (and hence no extra qubits) beyondthe routing variables. In contrast, prior quantum encodings introduce an explicit capacity/load representation with O(Q) or O(log Q) additional qubits for capacity Q [1, 2]. Our construction is designed to satisfy the kernel requirement of the Constraint-Enhanced QAOA (CE-QAOA) framework [3], making the resulting VRP instances compatible with its feasibility- and finite-shot guarantees [4, 5]. On the full benchmark suite of [6], our p = 1 CE–QAOA implementation recovers the certified optimum for every instance, without decomposition. All results are fully reproducible from the companion artifact archive in Ref. [7].

•Feb 27, 2026•0 citations

Requirements for Early Quantum Utility and Quantum Utility in the Capacitated Vehicle Routing Problem

Chinonso Onah, Kristel F. L. Michielsen

We introduce a transparent, encoding-agnostic framework for determining when the Capacitated Vehicle Routing Problem (CVRP) can achieve early quantum advantage. Our analysis shows this is unlikely on noisy intermediate scale quantum (NISQ) hardware even in best case scenarios that use the most qubit-efficient direct encodings. Closed-form resource counts, combined with recent device benchmarks, yield three decisive go/no-go figures of merit: the quantum feasibility point and the qubit- and gate-feasibility lines, which place any CVRP instance on a single decision diagram. Contrasting a direct QUBO mapping with a space-efficient higher-order (HOBO) encoding reveals a large gap. Applied to early-advantage benchmarks such as Golden-5, our diagram shows that HOBO circuits require only 7,685 qubits, whereas comparable QUBO encodings still exceed 200,000 qubits. In addition to identifying candidate instances for early quantum advantage in CVRP, the framework provides a unifying go/no-go metric that ingests any CVRP encoding together with any hardware profile and highlights when quantum devices could challenge classical heuristics. Quantum advantage in CVRP would likely require innovative problem decomposition techniques.

arXiv:2509.11469•Sep 14, 2025•0 citations

A feasibility-preserved quantum approximate solver for the Capacitated Vehicle Routing Problem

Ningyi Xie, Xinwei Lee, Dongsheng Cai +3 more

Abstract The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. The CVRP extends from the Vehicle Routing Problem (VRP), aiming to determine the most efficient plan for a fleet of vehicles to deliver goods to a set of customers, subject to the limited carrying capacity of each vehicle. As the number of possible solutions skyrockets when the number of customers increases, finding the optimal solution remains a significant challenge. Recently, the Quantum Approximate Optimization Algorithm (QAOA), a quantum-classical hybrid algorithm, has exhibited enhanced performance in certain combinatorial optimization problems compared to classical heuristics. However, its ability diminishes notably in solving constrained optimization problems including the CVRP. This limitation primarily arises from the typical approach of encoding the given problems as penalty-inclusive binary optimization problems. In this case, the QAOA faces challenges in sampling solutions satisfying all constraints. Addressing this, our work presents a new binary encoding for the CVRP, with an alternative objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. The search space is further restricted by the constraint-preserving mixing operation. We examine and discuss the effectiveness of the proposed encoding under the framework of the variant of the QAOA, Quantum Alternating Operator Ansatz (AOA), through its application to several illustrative examples. Compared to the typical QAOA approach, the proposed method not only preserves the feasibility but also achieves a significant enhancement in the probability of measuring optimal solutions.

arXiv:2308.08785•Quantum Information Processing•Jul 29, 2024•24 citations

Quantum Optimization Pipeline for the Capacitated Vehicle Routing Problem (CVRP)

Ninad Hirani

Quantum Optimization Pipeline for the Capacitated Vehicle Routing Problem (CVRP) This repository presents a research-oriented implementation of classical and quantum optimization techniques for solving the Capacitated Vehicle Routing Problem (CVRP). The project serves as an educational and experimental framework for studying hybrid quantum-classical optimization methods and benchmarking their performance on combinatorial optimization problems. The implementation includes: Classical CVRP optimization using Google OR-Tools Mathematical formulation of the routing problem Transformation of the optimization problem into a Quadratic Unconstrained Binary Optimization (QUBO) model Conversion of the QUBO formulation into an Ising Hamiltonian Implementation of the Quantum Approximate Optimization Algorithm (QAOA) using Qiskit Classical versus quantum performance comparison Route visualization and benchmarking Modular Python code designed for experimentation and future extensions The project is intended as a foundation for exploring applications of Quantum Computing, Operations Research, and Hybrid Quantum-Classical Optimization in real-world routing and logistics problems. It provides a reproducible environment for understanding optimization workflows, evaluating quantum algorithms, and extending the framework toward more complex scenarios such as dynamic vehicle routing and emergency ambulance dispatch. Keywords: Quantum Computing, Quantum Optimization, QAOA, QUBO, Ising Model, Capacitated Vehicle Routing Problem (CVRP), Operations Research, OR-Tools, Qiskit, Combinatorial Optimization, Hybrid Quantum-Classical Algorithms. This software was developed as part of a research internship focused on quantum optimization and serves as a learning and experimentation platform for future research.

•Jul 23, 2026•0 citations

Quantum Heuristic Approach to Vehicle Routing Problem

Jun Suk Kim, Donghyeon Lee, Chang Wook Ahn

Quantum optimization has recently drawn considerable attention as one of the possible applications of noisy intermediate-scale quantum computation, yet the problem of qubit requirement remains a major bottleneck when combinatorial optimization problems are converted into quantum circuits. This issue becomes especially critical in solving the capacitated vehicle routing problem (CVRP) with the quantum approximate optimization algorithm (QAOA), since the number of required qubits increases polynomially with respect to the number of nodes. This study investigates whether a heuristic divide-and-conquer strategy can be adapted to the quantum setting so as to improve qubit efficiency while preserving the optimization capability to a reasonable extent. The proposed method decomposes a single CVRP into multiple traveling salesman problems (TSPs) by the sweeping-based clustering method, searches for the sector configuration with the smallest angle sum by Grover’s search algorithm, and then solves each sector-wise TSP with the QAOA aided by the gravitational search algorithm. Experiments on five benchmark datasets show that the proposed approach attains feasible solutions within 3.4 to 12.7% of the reinforcement-learning baseline on the main test set. These results suggest that the proposed approach serves as a plausible quantum heuristic framework for constrained routing optimization, with the advantage of reducing the qubit burden by decomposing the original problem into smaller subproblems.

Mathematics•Mar 18, 2026•0 citations
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
We formulate capacitated vehicle routing as a colored permutation problem: each of the K vehicles selects a disjoint partial permutation, and the sum of these K submatrices forms a full n × n permutation matrix that assigns everycustomer to exactly one visit position. This representation requires no explicit load register (and hence no extra qubits) beyondthe routing variables. In contrast, prior quantum encodings introduce an explicit capacity/load representation with O(Q) or O(log Q) additional qubits for capacity Q [1, 2]. Our construction is designed to satisfy the kernel requirement of the Constraint-Enhanced QAOA (CE-QAOA) framework [3], making the resulting VRP instances compatible with its feasibility- and finite-shot guarantees [4, 5]. On the full benchmark suite of [6], our p = 1 CE–QAOA implementation recovers the certified optimum for every instance, without decomposition. All results are fully reproducible from the companion artifact archive in Ref. [7].
We introduce a transparent, encoding-agnostic framework for determining when the Capacitated Vehicle Routing Problem (CVRP) can achieve early quantum advantage. Our analysis shows this is unlikely on noisy intermediate scale quantum (NISQ) hardware even in best case scenarios that use the most qubit-efficient direct encodings. Closed-form resource counts, combined with recent device benchmarks, yield three decisive go/no-go figures of merit: the quantum feasibility point and the qubit- and gate-feasibility lines, which place any CVRP instance on a single decision diagram. Contrasting a direct QUBO mapping with a space-efficient higher-order (HOBO) encoding reveals a large gap. Applied to early-advantage benchmarks such as Golden-5, our diagram shows that HOBO circuits require only 7,685 qubits, whereas comparable QUBO encodings still exceed 200,000 qubits. In addition to identifying candidate instances for early quantum advantage in CVRP, the framework provides a unifying go/no-go metric that ingests any CVRP encoding together with any hardware profile and highlights when quantum devices could challenge classical heuristics. Quantum advantage in CVRP would likely require innovative problem decomposition techniques.
Abstract The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. The CVRP extends from the Vehicle Routing Problem (VRP), aiming to determine the most efficient plan for a fleet of vehicles to deliver goods to a set of customers, subject to the limited carrying capacity of each vehicle. As the number of possible solutions skyrockets when the number of customers increases, finding the optimal solution remains a significant challenge. Recently, the Quantum Approximate Optimization Algorithm (QAOA), a quantum-classical hybrid algorithm, has exhibited enhanced performance in certain combinatorial optimization problems compared to classical heuristics. However, its ability diminishes notably in solving constrained optimization problems including the CVRP. This limitation primarily arises from the typical approach of encoding the given problems as penalty-inclusive binary optimization problems. In this case, the QAOA faces challenges in sampling solutions satisfying all constraints. Addressing this, our work presents a new binary encoding for the CVRP, with an alternative objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. The search space is further restricted by the constraint-preserving mixing operation. We examine and discuss the effectiveness of the proposed encoding under the framework of the variant of the QAOA, Quantum Alternating Operator Ansatz (AOA), through its application to several illustrative examples. Compared to the typical QAOA approach, the proposed method not only preserves the feasibility but also achieves a significant enhancement in the probability of measuring optimal solutions.
Quantum Optimization Pipeline for the Capacitated Vehicle Routing Problem (CVRP) This repository presents a research-oriented implementation of classical and quantum optimization techniques for solving the Capacitated Vehicle Routing Problem (CVRP). The project serves as an educational and experimental framework for studying hybrid quantum-classical optimization methods and benchmarking their performance on combinatorial optimization problems. The implementation includes: Classical CVRP optimization using Google OR-Tools Mathematical formulation of the routing problem Transformation of the optimization problem into a Quadratic Unconstrained Binary Optimization (QUBO) model Conversion of the QUBO formulation into an Ising Hamiltonian Implementation of the Quantum Approximate Optimization Algorithm (QAOA) using Qiskit Classical versus quantum performance comparison Route visualization and benchmarking Modular Python code designed for experimentation and future extensions The project is intended as a foundation for exploring applications of Quantum Computing, Operations Research, and Hybrid Quantum-Classical Optimization in real-world routing and logistics problems. It provides a reproducible environment for understanding optimization workflows, evaluating quantum algorithms, and extending the framework toward more complex scenarios such as dynamic vehicle routing and emergency ambulance dispatch. Keywords: Quantum Computing, Quantum Optimization, QAOA, QUBO, Ising Model, Capacitated Vehicle Routing Problem (CVRP), Operations Research, OR-Tools, Qiskit, Combinatorial Optimization, Hybrid Quantum-Classical Algorithms. This software was developed as part of a research internship focused on quantum optimization and serves as a learning and experimentation platform for future research.
Quantum optimization has recently drawn considerable attention as one of the possible applications of noisy intermediate-scale quantum computation, yet the problem of qubit requirement remains a major bottleneck when combinatorial optimization problems are converted into quantum circuits. This issue becomes especially critical in solving the capacitated vehicle routing problem (CVRP) with the quantum approximate optimization algorithm (QAOA), since the number of required qubits increases polynomially with respect to the number of nodes. This study investigates whether a heuristic divide-and-conquer strategy can be adapted to the quantum setting so as to improve qubit efficiency while preserving the optimization capability to a reasonable extent. The proposed method decomposes a single CVRP into multiple traveling salesman problems (TSPs) by the sweeping-based clustering method, searches for the sector configuration with the smallest angle sum by Grover’s search algorithm, and then solves each sector-wise TSP with the QAOA aided by the gravitational search algorithm. Experiments on five benchmark datasets show that the proposed approach attains feasible solutions within 3.4 to 12.7% of the reinforcement-learning baseline on the main test set. These results suggest that the proposed approach serves as a plausible quantum heuristic framework for constrained routing optimization, with the advantage of reducing the qubit burden by decomposing the original problem into smaller subproblems.