Optimal solving of a scheduling problem using quantum annealing metaheuristics on the D-Wave quantum solver
Wojciech Bożejko, Ryszard Klempous, Jarosław Pempera +4 more
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. The main disadvantage of calculations on quantum computers is their non-determinism. For optimization problems, of course, it is possible to get surprisingly good results but without a guarantee of the actual optimality of the result, i.e, an assurance that there exists no better solution which could potentially be found by the quantum machine. In this paper, we propose an novel approach that provides such a guarantee of optimality. We generate a solution that is optimal in the strict mathematical sense, without probabilistic considerations. To accomplish this, we use the D-Wave quantum machine working as a sampler implementing quantum annealing -- an approach considered a hardware metaheuristic -- to obtain upper and lower bounds on the value of the objective function of the problem under consideration. Then, we use the Branch and Bound scheme controlled by quantum annealing. This allows us to obtain very quickly -- in constant time -- the boundaries of the considered subproblems. Our approach is a combination of calculations realized on a quantum machine controlled by procedures implemented on a classical computer, allowing us to generate optimal solutions to the NP-hard problems of task scheduling on a single machine with a total weighted tardiness criterion. The proposed quantum algorithm shows a significant advantage over the classical CPU approach both in terms of calculation time and the number of generated solution tree nodes.
•Apr 26, 2023•0 citations