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 reveal no clear evidence of speedup over conventional technologies. Here, we present results from classical parallel-tempering Monte Carlo simulations 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 fidelity, i.e., the probability that the ground-state configuration is affected by random fields and random bond fluctuations found on the chip. We compute upper-bound success probabilities for different instance classes based on these simple error models and present strategies on how to develop robust and hard benchmark instances.