A case study of variational quantum algorithms for a job shop scheduling problem
Open Access
- 10 February 2022
- journal article
- research article
- Published by Springer Nature in EPJ Quantum Technology
- Vol. 9 (1) , 1-20
Abstract
Combinatorial optimization models a vast range of industrial processes aiming at improving their efficiency. In general, solving this type of problem exactly is computationally intractable. Therefore, practitioners rely on heuristic solution approaches. Variational quantum algorithms are optimization heuristics that can be demonstrated with available quantum hardware. In this case study, we apply four variational quantum heuristics running on IBM’s superconducting quantum processors to the job shop scheduling problem. Our problem optimizes a steel manufacturing process. A comparison on 5 qubits shows that the recent filtering variational quantum eigensolver (F-VQE) converges faster and samples the global optimum more frequently than the quantum approximate optimization algorithm (QAOA), the standard variational quantum eigensolver (VQE), and variational quantum imaginary time evolution (VarQITE). Furthermore, F-VQE readily solves problem sizes of up to 23 qubits on hardware without error mitigation post processing.Keywords
All Related Versions
This publication has 34 references indexed in Scilit:
- Barren plateaus in quantum neural network training landscapesNature Communications, 2018
- Quantum circuit learningPhysical Review A, 2018
- Quantum Computing in the NISQ era and beyondQuantum, 2018
- Hardware-efficient variational quantum eigensolver for small molecules and quantum magnetsNature, 2017
- A variational eigenvalue solver on a photonic quantum processorNature Communications, 2014
- The unconstrained binary quadratic programming problem: a surveyJournal of Combinatorial Optimization, 2014
- Ising formulations of many NP problemsFrontiers in Physics, 2014
- Scheduling2012
- A fast quantum mechanical algorithm for database search1996
- A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation1994