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:2507.05373 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Solving Large-Scale Vehicle Routing Problems with Hybrid Quantum-Classical Decomposition

Andrew Maciejunes, John Stenger, Daniel Gunlycke, Nikos P. Chrisochoides

Published Aug 30, 2025• 3 citations
arXivHTMLPDF

Abstract

We present a two-level decomposition strategy for solving the Vehicle Routing Problem (VRP) using the Quantum Approximate Optimization Algorithm. A Problem-Level Decomposition partitions a 13-node (156-qubit) VRP into smaller Traveling Salesman Problem (TSP) instances. Each TSP is then further cut via Circuit-Level Decomposition, enabling execution on near-term quantum devices. Our approach achieves up to 95% reductions in the circuit depth, 96% reduction in the number of qubits and a 99.5% reduction in the number of 2-qubit gates. We demonstrate this hybrid algorithm on the standard edge encoding of the VRP as well as a novel amplitude encoding. These results demonstrate the feasibility of solving VRPs previously too complex for quantum simulators and provide early evidence of potential quantum utility.

DOI
10.1109/qce65121.2025.00234

Related papers

32 - Nested Two Level Decomposition for Quantum Computing

Maciejunes, Andrew, Stenger, John, Gunlycke, Dan +1 more

Abstract—We present a two-level decomposition strategy for solving the Vehicle Routing Problem (VRP) using the Quantum Approximate Optimization Algorithm (QAOA). A Problem-Level Decomposition (PLD) partitions a 9-node (72-qubit) VRP into smaller Traveling Salesman Problem (TSP) instances. Each TSP is then further simplified via Circuit-Level Decomposition (CLD), enabling execution on near-term quantum devices. Our approach achieves up to 90% reductions in circuit depth and qubit count. These results demonstrate the feasibility of solving VRPs previously too complex for quantum simulators and provide early evidence of potential quantum utility.

•Apr 4, 2025•0 citations

Hierarchical QAOA for the Vehicle Routing Problem via Clustered Decomposition and Local Feasibility Repair

S. Dash, Shreya Banerjee, Prasanta Kumar Panigrahi

We propose a hierarchical quantum approximate optimization framework for solving large-scale Vehicle Routing Problems (VRP) using Quantum Approximate Optimization Algorithm (QAOA). The method decomposes a VRP instance into balanced clusters of customer nodes. We formulate intra-cluster routing as Open loop Traveling Salesman Problems (OTSPs), and inter-cluster routing as a reduced VRP over the cluster representatives and depot. We then map the sub-problems to Ising Hamiltonians and solve with both standard and multi-angle QAOA variants at fixed depth p=3, and merge them to produce a routing path for the original VRP. Additionally, to improve solution feasibility and success probability, we introduce a polynomial-time post-processing protocol that samples candidate bit-strings from the QAOA output using a probability threshold and performs exhaustive local 1 and 2 bit-flip searches around these candidates. Benchmarking on 100 randomly generated 13-node, two-vehicle VRP instances, we show that the post-processed standard-QAOA implementation achieves high success rates and approximation ratios within 1.2-1.5 compared to classical optimizer (Gurobi) solutions, while requiring only 12 logical qubits per subproblem instead of 156 qubits for a direct edge-based encoding. These results provide a proof-of-concept demonstration that hierarchical decomposition, shallow QAOA, and local bit-flip repair can offer a scalable and resource-efficient pathway toward larger VRP instances on near-term quantum devices.

arXiv:2511.00506•Nov 1, 2025•1 citation

Improving Quantum and Classical Decomposition Methods for Vehicle Routing

Laura S. Herzog, Friedrich Wagner, Christian Ufrecht +4 more

Quantum computing is a promising technology to address combinatorial optimization problems, for example via the quantum approximate optimization algorithm (QAOA). Its potential, however, hinges on scaling toy problems to sizes relevant for industry. In this study, we address this challenge by an elaborate combination of two decomposition methods, namely graph shrinking and circuit cutting. Graph shrinking reduces the problem size before encoding into QAOA circuits, while circuit cutting decomposes quantum circuits into fragments for execution on medium-scale quantum computers. Our shrinking method adaptively reduces the problem such that the resulting QAOA circuits are particularly well-suited for circuit cutting. Moreover, we integrate two cutting techniques which allows us to run the resulting circuit fragments sequentially on the same device. We demonstrate the utility of our method by successfully applying it to the archetypical traveling salesperson problem (TSP) which often occurs as a sub-problem in practically relevant vehicle routing applications. For a TSP with seven cities, we are able to retrieve an optimum solution by consecutively running two 7-qubit QAOA circuits. Without decomposition methods, we would require five times as many qubits. Our results offer insights into the performance of algorithms for combinatorial optimization problems within the constraints of current quantum technology.

arXiv:2404.05551•Apr 8, 2024•2 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

Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm

Utkarsh Azad, Bikash K. Behera, Emad A. Ahmed +2 more

Intelligent transportation systems (ITS) are a critical component of Industry 4.0 and 5.0, particularly having applications in logistic management. One of their crucial utilization is in supply-chain management and scheduling for optimally routing transportation of goods by vehicles at a given set of locations. This paper discusses the broader problem of vehicle traffic management, more popularly known as the Vehicle Routing Problem (VRP), and investigates the possible use of near-term quantum devices for solving it. For this purpose, we give the Ising formulation for VRP and some of its constrained variants. Then, we present a detailed procedure to solve VRP by minimizing its corresponding Ising Hamiltonian using a hybrid quantum-classical heuristic called Quantum Approximate Optimization Algorithm (QAOA), implemented on the IBM Qiskit platform. We compare the performance of QAOA with classical solvers such as CPLEX on problem instances of up to 15 qubits. We find that performance of QAOA has a multifaceted dependence on the classical optimization routine used, the depth of the ansatz parameterized by$p$, initialization of variational parameters, and problem instance itself.

arXiv:2002.01351•IEEE Transactions on Intelligent Transportation Systems•May 13, 2022•149 citations

Hardware-Efficient Quantum Optimization for Transportation Networks via Compressed Adiabatic Evolution

Talha Azfar, Ruimin Ke, Sean He +2 more

Transportation systems such as urban logistics, vehicle routing, and infrastructure planning require solving large-scale combinatorial optimization problems under complex constraints. Problems such as the vehicle routing problem (VRP), traveling salesman problem (TSP), and facility location problem (FLP) involve large discrete search spaces and the need to generate multiple feasible solutions in real time. In this work, we develop a hardware-grounded hybrid quantum optimization framework that uses Approximate Quantum Compilation (AQC) to compress early segments of digitized adiabatic evolution into shallow circuits. The compressed prefix is combined with variational layers, enabling a systematic study of how initialization, circuit depth, and expressivity interact on near-term quantum hardware. All experiments are performed on an IBM gate-based quantum computer, and circuits are evaluated as stochastic generators of candidate transportation plans. Results show that moderate prefix compression reduces two-qubit gate depth while maintaining or improving feasible solution discovery, particularly for routing problems. These benefits depend on compatibility between the compressed prefix and the variational ansatz: while standard QAOA effectively leverages AQC initialization, linear-chain QAOA shows limited improvement. Overall, this work demonstrates that hybrid AQC-QAOA methods provide a practical pathway for hardware-efficient quantum optimization, positioning quantum algorithms as candidate generators within transportation decision-making workflows.

quant-pharXiv:2604.26175•Apr 30, 2026•0 citations
We present a two-level decomposition strategy for solving the Vehicle Routing Problem (VRP) using the Quantum Approximate Optimization Algorithm. A Problem-Level Decomposition partitions a 13-node (156-qubit) VRP into smaller Traveling Salesman Problem (TSP) instances. Each TSP is then further cut via Circuit-Level Decomposition, enabling execution on near-term quantum devices. Our approach achieves up to 95% reductions in the circuit depth, 96% reduction in the number of qubits and a 99.5% reduction in the number of 2-qubit gates. We demonstrate this hybrid algorithm on the standard edge encoding of the VRP as well as a novel amplitude encoding. These results demonstrate the feasibility of solving VRPs previously too complex for quantum simulators and provide early evidence of potential quantum utility.
Abstract—We present a two-level decomposition strategy for solving the Vehicle Routing Problem (VRP) using the Quantum Approximate Optimization Algorithm (QAOA). A Problem-Level Decomposition (PLD) partitions a 9-node (72-qubit) VRP into smaller Traveling Salesman Problem (TSP) instances. Each TSP is then further simplified via Circuit-Level Decomposition (CLD), enabling execution on near-term quantum devices. Our approach achieves up to 90% reductions in circuit depth and qubit count. These results demonstrate the feasibility of solving VRPs previously too complex for quantum simulators and provide early evidence of potential quantum utility.
We propose a hierarchical quantum approximate optimization framework for solving large-scale Vehicle Routing Problems (VRP) using Quantum Approximate Optimization Algorithm (QAOA). The method decomposes a VRP instance into balanced clusters of customer nodes. We formulate intra-cluster routing as Open loop Traveling Salesman Problems (OTSPs), and inter-cluster routing as a reduced VRP over the cluster representatives and depot. We then map the sub-problems to Ising Hamiltonians and solve with both standard and multi-angle QAOA variants at fixed depth p=3, and merge them to produce a routing path for the original VRP. Additionally, to improve solution feasibility and success probability, we introduce a polynomial-time post-processing protocol that samples candidate bit-strings from the QAOA output using a probability threshold and performs exhaustive local 1 and 2 bit-flip searches around these candidates. Benchmarking on 100 randomly generated 13-node, two-vehicle VRP instances, we show that the post-processed standard-QAOA implementation achieves high success rates and approximation ratios within 1.2-1.5 compared to classical optimizer (Gurobi) solutions, while requiring only 12 logical qubits per subproblem instead of 156 qubits for a direct edge-based encoding. These results provide a proof-of-concept demonstration that hierarchical decomposition, shallow QAOA, and local bit-flip repair can offer a scalable and resource-efficient pathway toward larger VRP instances on near-term quantum devices.
Quantum computing is a promising technology to address combinatorial optimization problems, for example via the quantum approximate optimization algorithm (QAOA). Its potential, however, hinges on scaling toy problems to sizes relevant for industry. In this study, we address this challenge by an elaborate combination of two decomposition methods, namely graph shrinking and circuit cutting. Graph shrinking reduces the problem size before encoding into QAOA circuits, while circuit cutting decomposes quantum circuits into fragments for execution on medium-scale quantum computers. Our shrinking method adaptively reduces the problem such that the resulting QAOA circuits are particularly well-suited for circuit cutting. Moreover, we integrate two cutting techniques which allows us to run the resulting circuit fragments sequentially on the same device. We demonstrate the utility of our method by successfully applying it to the archetypical traveling salesperson problem (TSP) which often occurs as a sub-problem in practically relevant vehicle routing applications. For a TSP with seven cities, we are able to retrieve an optimum solution by consecutively running two 7-qubit QAOA circuits. Without decomposition methods, we would require five times as many qubits. Our results offer insights into the performance of algorithms for combinatorial optimization problems within the constraints of current quantum technology.
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.
Intelligent transportation systems (ITS) are a critical component of Industry 4.0 and 5.0, particularly having applications in logistic management. One of their crucial utilization is in supply-chain management and scheduling for optimally routing transportation of goods by vehicles at a given set of locations. This paper discusses the broader problem of vehicle traffic management, more popularly known as the Vehicle Routing Problem (VRP), and investigates the possible use of near-term quantum devices for solving it. For this purpose, we give the Ising formulation for VRP and some of its constrained variants. Then, we present a detailed procedure to solve VRP by minimizing its corresponding Ising Hamiltonian using a hybrid quantum-classical heuristic called Quantum Approximate Optimization Algorithm (QAOA), implemented on the IBM Qiskit platform. We compare the performance of QAOA with classical solvers such as CPLEX on problem instances of up to 15 qubits. We find that performance of QAOA has a multifaceted dependence on the classical optimization routine used, the depth of the ansatz parameterized byppp, initialization of variational parameters, and problem instance itself.
Transportation systems such as urban logistics, vehicle routing, and infrastructure planning require solving large-scale combinatorial optimization problems under complex constraints. Problems such as the vehicle routing problem (VRP), traveling salesman problem (TSP), and facility location problem (FLP) involve large discrete search spaces and the need to generate multiple feasible solutions in real time. In this work, we develop a hardware-grounded hybrid quantum optimization framework that uses Approximate Quantum Compilation (AQC) to compress early segments of digitized adiabatic evolution into shallow circuits. The compressed prefix is combined with variational layers, enabling a systematic study of how initialization, circuit depth, and expressivity interact on near-term quantum hardware. All experiments are performed on an IBM gate-based quantum computer, and circuits are evaluated as stochastic generators of candidate transportation plans. Results show that moderate prefix compression reduces two-qubit gate depth while maintaining or improving feasible solution discovery, particularly for routing problems. These benefits depend on compatibility between the compressed prefix and the variational ansatz: while standard QAOA effectively leverages AQC initialization, linear-chain QAOA shows limited improvement. Overall, this work demonstrates that hybrid AQC-QAOA methods provide a practical pathway for hardware-efficient quantum optimization, positioning quantum algorithms as candidate generators within transportation decision-making workflows.