Experiments ( by researchers at USC, ETH Zurich, and the Center for Quantum Information Science and Technology, Microsoft Research) have demonstrated that quantum annealing with more than one hundred qubits takes place in the D-Wave One device, despite limited qubit coherence times. The key evidence is the rich, correlation between the success probabilities on the device and a simulated quantum annealer. In particular we see a bimodal distribution of easy and hard instances, where the hard instances are characterized by avoided level crossings with small gaps. Sensitivity to these small gaps of the quantum model demonstrates that the device has sufficient ground state quantum coherence to realize a quantum annealing of a transverse field Ising model. Considering the pure annealing time, the performance for typical (median) instances matches that of a highly optimised classical annealing code on a high-end Intel CPU.
While for 108 spins a majority of optimization problems is still relatively easy, experiments using up to 512 spins on the next generation device will enter a very interesting regime where almost all instances become hard for both simulated annealing and simulated quantum annealing. Simulated annealers require about three orders of magnitude more computational effort for N = 512 spins compared to N = 108 spins for our problems, and there will be potential to see advantages of a quantum annealer over classical algorithms.
Quantum speedup can then be detected by comparing the scaling results of the simulated classical and quantum annealers to experiments, as we discuss in detail in the supplementary material. Going to even larger problem sizes we soon approach the limits of classical computers. Optimistically extrapolating using the observed scaling, the median time to find the best solution for our test problem will increase from milliseconds to minutes for 2048 variables, and months for 4096 variables, and the scaling might be much worse if fat tailed distributions start to dominate, as we had previously observed for other Monte Carlo algorithms. A quantum annealer showing better scaling than classical algorithms for these problem sizes would be an exciting breakthrough, validating the potential of quantum information processing to outperform its classical counterpart.