Hard scheduling problems for early quantum annealer

We present a parameterized family of single machine scheduling problem that exhibits an easy-hard-easy phase transition. As the parameter is varied, the problem goes through a fast transition from being almost trivial to find a solution to almost always has no solution, this sharp transition accompanies a peak in computational effort. While implementing realistic-sized problems on an early quantum annealing device is still a challenge in near future, using a benchmarking problem set of small size but in a well-defined hard family, one can gain insight to a how the solving time scales for the whole family.[1] We will report quantum annealing results on this and other related problems. [1] E. G. Rieffel, D. Venturelli, B. OGorman, M. B. Do, E. M. Prystay, and V. N. Smelyanskiy, Quantum Information Processing 14, 1 (2015).