Reaching states below the threshold energy in spin glasses via quantum annealing

Although quantum annealing is usually considered as a method for locating the ground states of difficult spin-glass and optimization problems, its use in approximate optimization - finding low- but not zero-energy states in a reasonably short amount of time - is no less important. Here we investigate the behavior of quantum annealing at approximate optimization in the canonical mean-field spin-glass models, the spherical p-spin models, and find that it performs surprisingly well. Whereas it had long been assumed that infinite-range spin glasses have a unique "threshold" energy at which all quench and annealing dynamics become trapped until exponential timescales, recent work has shown that two-stage quenches can in fact reach states below the naive threshold in more generic situations. We demonstrate that quantum annealing is also capable of exploiting this effect to locate sub-threshold states in O(1) time. Not only can it attain energies as far below the threshold as classical annealing algorithms, but it can do so significantly faster: for an annealing schedule taking time τ, the residual energy under quantum annealing decays as τ^-α with an exponent up to twice as large as that of simulated annealing in the cases considered. Importantly, by deriving and numerically solving closed integro-differential equations that hold in the thermodynamic limit, our results are free from finite-size effects and hold for annealing times that are unambiguously independent of system size.