Solving The Vehicle Routing Problem via Quantum Support Vector Machines
arXiv:2308.04849 · doi:10.1007/s42484-024-00161-4
Abstract
The Vehicle Routing Problem (VRP) is an example of a combinatorial optimization problem that has attracted academic attention due to its potential use in various contexts. VRP aims to arrange vehicle deliveries to several sites in the most efficient and economical manner possible. Quantum machine learning offers a new way to obtain solutions by harnessing the natural speedups of quantum effects, although many solutions and methodologies are modified using classical tools to provide excellent approximations of the VRP. In this paper, we implement and test hybrid quantum machine learning methods for solving VRP of 3 and 4-city scenarios, which use 6 and 12 qubit circuits, respectively. The proposed method is based on quantum support vector machines (QSVMs) with a variational quantum eigensolver on a fixed or variable ansatz. Different encoding strategies are used in the experiment to transform the VRP formulation into a QSVM and solve it. Multiple optimizers from the IBM Qiskit framework are also evaluated and compared.
arXiv comment13 pages, 7 figures, and 2 tables
References in corpus (15)
- Quantum entanglement
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- Supervised learning with quantum enhanced feature spaces
- Quantum support vector machine for big data classification
- Quantum algorithms: an overview
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Robust data encodings for quantum classifiers
- A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
- A divide-and-conquer algorithm for quantum state preparation
- Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
- Covariant quantum kernels for data with group structure
- The complexity of quantum support vector machines
- Analysis of The Vehicle Routing Problem Solved via Hybrid Quantum Algorithms in Presence of Noisy Channels