Symmetry-based quantum algorithms for open-shop scheduling with hard constraints

Academia quantum., vol. 2

Abstract

Encoding hard-constrained optimization problems into a variational quantum algorithm often turns out to be a challenging task. In this work, we provide a solution for the class of open-shop scheduling problems (OSSPs), which we achieve by rigorously employing the symmetries of the classical problem. An established approach for encoding the hard constraints of the closely related traveling salesperson problem (TSP) into mixer Hamiltonians was recently given by Hadfield et al.’s Quantum Alternating Operator Ansatz (QAOA). For the OSSP, which contains TSP as a special case, we show that desired properties of similarly constructed mixers can be directly linked to a purely classical object: the group of feasibility-preserving bit value permutations. We also outline a generic way to construct QAOA-like mixers for these problems. We further propose a new variational quantum algorithm that incorporates the underlying group structure more naturally and, as a proof of principle, implement our new algorithm for a small OSSP instance on an IBM Q System One. Unlike the generic QAOA, our algorithm allows for bounding the amount and the domain of parameters necessary to reach every feasible solution from above: If J jobs should be distributed, optimizing at most J ( J − 1 ) 2 / 2 parameters should suffice to reach the optimum with certainty.

Authors 4

1. Lennart Binkowski

   Leibniz University Hannover

   Affiliation as printed

   Institute for Theoretical Physics, AG Quantum Information, Leibniz University Hannover, Hannover, Germany

2. Gereon Koßmann Aachen Institute for Quantum Information

   Fraunhofer Institute for Industrial Engineering · RWTH Aachen University

   Affiliation as printed

   Fraunhofer Institute for Industrial Engineering IAO, Stuttgart, Germany

   Institute for Quantum Information, RWTH Aachen University, Aachen, Germany

3. Christian Tutschku

   Fraunhofer Institute for Industrial Engineering

   Affiliation as printed

   Fraunhofer Institute for Industrial Engineering IAO, Stuttgart, Germany

4. René Schwonnek

   Leibniz University Hannover

   Affiliation as printed

   Institute for Theoretical Physics, AG Quantum Information, Leibniz University Hannover, Hannover, Germany