Challenges in Solving Scheduling Problems with the D-Wave Quantum Annealer
TimeTuesday, June 23rd3:15pm - 3:20pm
DescriptionQuantum annealing is emerging as a potential accelerator for solving combinatorial optimization problems by exploiting fundamental quantum mechanical properties. In order to utilize quantum annealing, problems must undergo preparatory steps, such as formulation as a quadratic unconstrained binary optimization problem and graph minor embedding, to ensure compatibility with the quantum annealing hardware. However, the time and computational overhead incurred in these steps can offset the potential acceleration. Focusing on the job-shop scheduling problem (JSP) with varying instance parameters, the challenges and overheads of adapting and solving a problem with quantum annealing are analyzed. Observations made during the various phases of quantum annealing and results from many JSP instances are used to determine general properties of problems for which the current implementation of quantum annealing has limited practicality. In order to address the current limitations, strategies to improve quantum annealing performance and modify problems to be more amenable to quantum annealing are introduced, leading to a recommendation for better embedding algorithms and hybrid quantum-classical methods.