Performance of Quantum Annealers on Hard Scheduling Problems

We analyze the performance of three generations of quantum annealers (housed at NASA Ames), D-Wave Two, 2X and 2000Q, on hard scheduling problems. We quantify the improvements of each generation in both absolute time-to-solution and scaling of the time-to-solution with respect to problem sizes. We examined the contributions to this improvement, including the effect of hardware improvements and of the shorter anneal times available on the more recent annealers. We also examined how stronger or weaker ferromagnetic couplings enforcing constraints within vertex models (physical qubits representing the same logical qubit after embedding) affect performance. Our results offer insights about how future quantum annealers can be designed and programmed to be more effective at solving pragmatic optimization problems like the scheduling problems.