Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing
quant-ph, cs.DM
Submitted: 2024-12-20
Updated: 2026-04-24
Code: https://github.com/fwgfau/qvrp
License: http://creativecommons.org/licenses/by/4.0/
The gist: Motivated by recent progress in quantum hardware and algorithms researchers have developed quantum heuristics for optimization problems, aiming for advantages over classical methods.
Terminology
Abstract
Motivated by recent progress in quantum hardware and algorithms researchers have developed quantum heuristics for optimization problems, aiming for advantages over classical methods. To date, quantum hardware is still error-prone and limited in size such that quantum heuristics cannot be scaled to relevant problem sizes and are often outperformed by their classical counterparts. Moreover, if provably optimal solutions are desired, one has to resort to classical exact methods. As however quantum technologies may improve considerably in future, we demonstrate in this work how quantum heuristics with limited resources can be integrated in large-scale exact optimization algorithms for NP-hard problems. To this end, we consider vehicle routing as prototypical NP-hard problem. We model the pricing and separation subproblems arising in a branch-price-and-cut algorithm as quadratic unconstrained binary optimization problems. This allows to use established quantum heuristics like quantum annealing or the quantum approximate optimization algorithm for their solution. A key feature of our algorithm is that it profits not only from the best solution returned by the quantum heuristic but from all solutions below a certain cost threshold, thereby exploiting the inherent randomness is quantum algorithms. Moreover, we reduce the requirements on quantum hardware since the subproblems, which are solved via quantum heuristics, are smaller than the original problem. We provide an experimental study comparing quantum annealing to simulated annealing and to established classical algorithms in our framework. While our hybrid quantum-classical approach is still outperformed by purely classical methods, our results reveal that both pricing and separation may be well suited for quantum heuristics if quantum hardware improves.
Sources
- Challenges and Opportunities in Quantum Optimization
- Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
- Realistic Runtime Analysis for Quantum Simplex Computation
- A Quantum Approximate Optimization Algorithm
- On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization
- A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem
- Quantum Robustness Verification: A Hybrid Quantum-Classical Neural Network Certification Algorithm
- Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness
- Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
- A Neural Separation Algorithm for the Rounded Capacity Inequalities
- Knapsack Problem variants of QAOA for battery revenue optimisation
- Adiabatic quantum computing solution of the knapsack problem
- A practical heuristic for finding graph minors
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements