Harnessing spin-glass theory to probe quantum annealers

Recent developments in quantum technology have led to the manufacturing of experimental programmable quantum annealing optimizers containing hundreds of quantum bits. These optimizers, also known as the ‘D-Wave’ chips, promise to solve practical optimization problems potentially faster than conventional ‘classical’ computers. The quantum nature of these optimizers has recently become the center of a heated debate within the Quantum Computing community (and well beyond it) about the claimed superiority of these annealers over traditional devices and the degree to which they exploit their quantum capabilities. 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 expected to fail. I will describe attempts to identify such hard "D-Wave-specific" problems 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 Two chip on these.