Can Analog Quantum Computers Solve Spin Glasses?*

Recent developments in quantum technology have led to the manufacture of experimental programmable quantum annealing optimizers that contain thousands of quantum bits. These optimizers, also known as the ‘D-Wave’ processors, promise to solve practical optimization problems potentially faster than conventional computers. The claimed superiority of these annealers over traditional solvers and the degree to which they exploit their quantum capabilities is currently the center of a heated debate. In this context, specifically of importance is the question of how well these quantum annealers perform on hard problems with rugged free-energy landscapes for which classical methods are known to fail. I will describe attempts to identify such hard problems and characterize these devices by means of state-of-the-art methods borrowed from spin-glass theory, and present results pertaining to the performance of various classical algorithms and the D-wave processors on these.