Solving the vehicle routing problem via quantum support vector machines
Open Access
- 6 June 2024
- journal article
- research article
- Published by Springer Nature in Quantum Machine Intelligence
- Vol. 6 (1) , 1-17
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 employ 6 and 12 qubit circuits, respectively, to build and evaluate a hybrid quantum machine learning approach for solving VRP of 3- and 4-city scenarios. The approach employs quantum support vector machines (QSVMs) trained using a variational quantum eigensolver on a static or dynamic 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 comparedKeywords
All Related Versions
Funding Information
- University of Technology Sydney
This publication has 25 references indexed in Scilit:
- Covariant quantum kernels for data with group structureNature Physics, 2024
- Variational quantum algorithmsNature Reviews Physics, 2021
- A divide-and-conquer algorithm for quantum state preparationScientific Reports, 2021
- Quantum Bridge Analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange4OR, 2020
- Supervised learning with quantum-enhanced feature spacesNature, 2019
- Efficiently embedding QUBO problems on adiabatic quantum computersQuantum Information Processing, 2019
- Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity2019
- Quantum algorithms: an overviewnpj Quantum Information, 2016
- A variational eigenvalue solver on a photonic quantum processorNature Communications, 2014
- The unconstrained binary quadratic programming problem: a surveyJournal of Combinatorial Optimization, 2014