Unraveling Quantum Annealers using Classical Hardness
Loading...
Official URL
Full text at PDC
Publication date
2015
Authors
Advisors (or tutors)
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
Nature Publishing Group
Citation
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 spinglass 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.
Description
© Nature Publishing Group.
We thank Luis Antonio Fernández and David Yllanes for providing us with their analysis program for the PT correlation function. We also thank Marco Baity-Jesi for helping us to prepare the figures. We are indebted to Mohammad Amin, Luis Antonio Fernández, Enzo Marinari, Denis Navarro, Giorgio Parisi, Federico Ricci-Tersenghi and Juan Jesús Ruiz-Lorenzo for discussions. We thank Luis Antonio Fernández, Daniel Lidar, Felipe LLanes-Estrada, David Yllanes and Peter Young for their reading of a preliminary version of the manuscript. We thank D-Wave Systems Inc. for granting us access to the chip. We acknowledge the use of algorithms and source code for a classic solver, devised and written by Alex Selby, available for public usage at https://github.com/alex1770/QUBO-Chimera. Our simulated annealing runs were carried out on the Picasso supercomputer. The authors thankfully acknowledge the computer resources, technical expertise and assistance provided by the staff at the Red Española de Supercomputación. IH acknowledges support by ARO grant number W911NF-12-1-0523. VMM was supported by MINECO (Spain) through research contract No FIS2012-35719-C02.