Advances in Quantum Algorithms & Devices: Quantum versus classical annealing

I will discuss several recent findings about the computational power of quantum annealing, either on quantum hardware or as “simulated quantum annealing” by quantum Monte Carlo (QMC) simulations on a classical computer. The failure to so far observe quantum speedup on D-Wave Two is in contradiction to previous QMC results that indicated quantum speedup for spin glasses. This apparent contradiction can be resolved by taking the continuous time limit in the QMC simulations. We find that continuous time QMC simulations agree with the behavior of d-Wave and show no speedup for 2D spin glasses. However, QMC simulations with large time steps gain further advantage: they “cheat” by ignoring what happens during a (large) time step, and can thus outperform both simulated quantum annealers and classical annealers. While this is good news for the development of quantum inspired classical optimization algorithms, it further raises the bar for quantum annealers.

A second topic that I will discuss is how to optimally run a quantum annealer. Investigating the behavior of the tails of the distribution of runtimes for very hard instances we find that adiabatically slow annealing is far from optimal. On the contrary, many repeated relatively fast annealing runs can be orders of magnitude faster for hard problems. The intuitive explanation is that hard instances, which are stuck in the “wrong” minimum can be solved faster by perturbing them.

Finally, I will discuss the prospects of quantum annealing outperforming classical annealing on hard optimization problems.