  There have been multiple attempts to design synthetic benchmark problems with
the goal of detecting quantum speedup in current quantum annealing machines. To
date, classical heuristics have consistently outperformed quantum-annealing
based approaches. Here we introduce a class of problems based on frustrated
cluster loops - deceptive cluster loops - for which all currently known
state-of-the-art classical heuristics are outperformed by the D-Wave 2000Q
quantum annealing machine. While there is a sizable constant speedup over all
known classical heuristics, a noticeable improvement in the scaling remains
elusive. These results represent the first steps towards a detection of
potential quantum speedup, albeit without a scaling improvement and for
synthetic benchmark problems.
