https://doi.org/10.1140/epjqt/s40507-022-00123-4
Research
A case study of variational quantum algorithms for a job shop scheduling problem
1
Cambridge Quantum Computing Limited, SW1P 1BX, London, UK
2
Cambridge Quantum Computing Limited, Terrington House 13-15 Hills Road, CB2 1NL, Cambridge, UK
3
Nippon Steel Corporation, 20-1 Shintomi, 293-8511, Futtsu, Chiba, Japan
b
matthias.rosenkranz@cambridgequantum.com
Received:
13
August
2021
Accepted:
28
January
2022
Published online:
10
February
2022
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.
Key words: Combinatorial optimization / Variational quantum algorithms / Heuristics / Quantum hardware
© The Author(s) 2022
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
