Quantum Optimization: Spin Glasses and Wavefunction Annealing

Arnab Das, Bikas K. Chakrabarti

Jun‐ichi Inoue

Javier Rodríguez-Laguna

A technique inspired by quantum annealing is proposed in order to obtain the classical ground state of a spin glass by tracking the full wavefunction of a given system within the subspace of matrix product states, using the density matrix renormalization group. The technique is exemplified within the problem of obtaining the classical ground state of an Ising spin glass on ladder geometries. Its performance is evaluated and related to the entanglement entropy.

Arnab Das, Bikas K. Chakrabarti

Christopher L. Baldwin

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.

Davide Venturelli, Salvatore Mandrà, Sergey Knysh +3 more

Quantum computing promises to be more efficient and significantly faster than today's classical computing. Researchers compare the performance of a quantum annealer with that of classical algorithms for the first time on hard spin-glass problems.