Unraveling Quantum Annealers using Classical Hardness
Open Access
- 20 October 2015
- journal article
- research article
- Published by Springer Nature in Scientific Reports
- Vol. 5 (1) , 15324
Abstract
Recent advances in quantum technology have led to the development and manufacturing of experimental programmable quantum annealing optimizers that contain hundreds of quantum bits. These optimizers, commonly referred to as ‘D-Wave’ chips, promise to solve practical optimization problems potentially faster than conventional ‘classical’ computers. Attempts to quantify the quantum nature of these chips have been met with both excitement and skepticism but have also brought up numerous fundamental questions pertaining to the distinguishability of experimental quantum annealers from their classical thermal counterparts. Inspired by recent results in spin-glass theory that recognize ‘temperature chaos’ as the underlying mechanism responsible for the computational intractability of hard optimization problems, we devise a general method to quantify the performance of quantum annealers on optimization problems suffering from varying degrees of temperature chaos: A superior performance of quantum annealers over classical algorithms on these may allude to the role that quantum effects play in providing speedup. We utilize our method to experimentally study the D-Wave Two chip on different temperature-chaotic problems and find, surprisingly, that its performance scales unfavorably as compared to several analogous classical algorithms. We detect, quantify and discuss several purely classical effects that possibly mask the quantum behavior of the chip.Keywords
All Related Versions
This publication has 39 references indexed in Scilit:
- Defining and detecting quantum speedupScience, 2014
- Evidence for quantum annealing with more than one hundred qubitsNature Physics, 2014
- Janus II: A new generation application-driven computer for spin-system simulationsComputer Physics Communications, 2014
- Quantum adiabatic Markovian master equationsNew Journal of Physics, 2012
- Quantum annealing with manufactured spinsNature, 2011
- Janus: An FPGA-Based System for High-Performance Scientific ComputingComputing in Science & Engineering, 2008
- Simulating spin systems on IANUS, an FPGA-based computerComputer Physics Communications, 2008
- Decoherence, the measurement problem, and interpretations of quantum mechanicsReviews of Modern Physics, 2005
- Quantum Mechanics Helps in Searching for a Needle in a HaystackPhysical Review Letters, 1997
- Exchange Monte Carlo Method and Application to Spin Glass SimulationsJournal of the Physical Society of Japan, 1996