Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities

Recent tests performed on the D-Wave Two quantum annealer have revealed no clear evidence of speedup over conventional silicon-based technologies. Here we present results from classical parallel-tempering Monte Carlo simulations combined with isoenergetic cluster moves of the archetypal benchmark problem-an Ising spin glass-on the native chip topology. Using realistic uncorrelated noise models for the D-Wave Two quantum annealer, we study the best-case resilience, i.e., the probability that the ground-state configuration is not affected by random fields and random-bond fluctuations found on the chip. We thus compute classical upper-bound success probabilities for different types of disorder used in the benchmarks and predict that an increase in the number of qubits will require either error correction schemes or a drastic reduction of the intrinsic noise found in these devices. We restrict this study to the exact ground state, however, the approach can be trivially extended to the inclusion of excited states if the success metric is relaxed. We outline strategies to develop robust, as well as hard benchmarks for quantum annealing devices, as well as any other (black box) computing paradigm affected by noise.