A case study of variational quantum algorithms for a job shop scheduling problem
David Amaro, Matthias Rosenkranz, Nathan Fitzpatrick, Koji Hirano, Mattia Fiorentini
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. Combining F-VQE with error mitigation and causal
cones could allow quantum optimization heuristics to scale to relevant problem
sizes.