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.
If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks