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

• URL: http://arxiv.org/abs/2507.05373v1
• Date: Mon, 07 Jul 2025 18:02:13 GMT
• Title: Solving Large-Scale Vehicle Routing Problems with Hybrid Quantum-Classical Decomposition
• Authors: Andrew Maciejunes, John Stenger, Dan Gunlycke, Nikos Chrisochoides,
• Abstract summary: We present a two-level decomposition strategy for solving the Vehicle Routing Problem (VRP)<n>A Problem-Level Decomposition partitions a 13-node (156-qubit) VRP into smaller Traveling Salesman Problem (TSP) instances.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Improving Quantum and Classical Decomposition Methods for Vehicle Routing [2.4646794072984477]
  We propose an elaborate combination of two decomposition methods, namely graph shrinking and circuit cutting. Our results offer insights into the performance of algorithms for optimization problems within the constraints of current quantum technology.
  arXiv  Detail & Related papers  (2024-04-08T14:19:25Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  We propose a faster digital quantum algorithm for portfolio optimization using the digitized-counterdiabatic quantum optimization (DCQO) paradigm. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We experimentally demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2023-08-29T17:53:08Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness [2.854196251981274]
  In this study, we examine two decomposition methods for Mixed-Integer Linear Programming (MILP) We concentrate on breaking down the original problem into smaller subproblems, which are then solved iteratively using a combined quantum-classical hardware approach. Our experimental results demonstrate that this approach can save up to 90% of qubits compared to existing methods on quantum annealing and gate-based quantum computers.
  arXiv  Detail & Related papers  (2023-04-30T13:10:56Z)
• Reducing the Depth of Linear Reversible Quantum Circuits [0.0]
  In quantum computing the decoherence time of the qubits determines the computation time available. We propose a practical formulation of a divide and conquer algorithm that produces quantum circuits that are twice as shallow as those produced by existing algorithms. Overall, we manage to consistently reduce the total depth of a class of reversible functions, with up to 92% savings in an ancilla-free case and up to 99% when ancillary qubits are available.
  arXiv  Detail & Related papers  (2022-01-17T12:36:32Z)
• Optimized fermionic SWAP networks with equivalent circuit averaging for QAOA [2.3362993651992863]
  We optimize the execution of fermionic SWAP networks for Quantum Approximate Optimization Algorithm (QAOA) We introduce Equivalent Circuit Averaging, which randomizes over degrees of freedom in the quantum circuit compilation. We observe a 60% average reduction in error (total variation distance) for QAOA of depth p = 1 on four transmon qubits on a superconducting quantum processor.
  arXiv  Detail & Related papers  (2021-11-08T15:32:05Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
  We introduce a quantum circuit mapping, QXX, and its machine learning version, QXX-MLP. The latter infers automatically the optimal QXX parameter values such that the layed out circuit has a reduced depth. We present empiric evidence for the feasibility of learning the layout method using approximation.
  arXiv  Detail & Related papers  (2020-07-29T05:26:19Z)
• A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz [68.8204255655161]
  We describe a compilation strategy for Variational Quantum Eigensolver (VQE) algorithms. We use the Unitary Coupled Cluster (UCC) ansatz to reduce circuit depth and gate count.
  arXiv  Detail & Related papers  (2020-07-20T22:26:16Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.