Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
Authors:
Open Access
- 1 September 2015
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review X
- Vol. 5 (3) , 031026
Abstract
There has been considerable progress in the design and construction of quantum annealing devices. However, a conclusive detection of quantum speedup over traditional silicon-based machines remains elusive, despite multiple careful studies. In this work we outline strategies to design hard tunable benchmark instances based on insights from the study of spin glasses—the archetypal random benchmark problem for novel algorithms and optimization devices. We propose to complement head-to-head scaling studies that compare quantum annealing machines to state-of-the-art classical codes with an approach that compares the performance of different algorithms and/or computing architectures on different classes of computationally hard tunable spin-glass instances. The advantage of such an approach lies in having to compare only the performance hit felt by a given algorithm and/or architecture when the instance complexity is increased. Furthermore, we propose a methodology that might not directly translate into the detection of quantum speedup but might elucidate whether quantum annealing has a “quantum advantage” over corresponding classical algorithms, such as simulated annealing. Our results on a 496-qubit D-Wave Two quantum annealing device are compared to recently used state-of-the-art thermal simulated annealing codes.Keywords
All Related Versions
Funding Information
- National Science Foundation (DMR-1151387)
- Office of the Director of National Intelligence
- IARPA
This publication has 79 references indexed in Scilit:
- Thermodynamic glass transition in a spin glass without time-reversal symmetryProceedings of the National Academy of Sciences, 2012
- Mathematical foundation of quantum annealingJournal of Mathematical Physics, 2008
- Persistence and memory in patchwork dynamics for glassy modelsPhysical Review B, 2008
- Simulating spin systems on IANUS, an FPGA-based computerComputer Physics Communications, 2008
- Temperature and Disorder Chaos in Three-Dimensional Ising Spin GlassesPhysical Review Letters, 2007
- Optimization using quantum mechanics: quantum annealing through adiabatic evolutionJournal of Physics A: General Physics, 2006
- Temperature Chaos and Bond Chaos in Edwards-Anderson Ising Spin Glasses: Domain-Wall Free-Energy MeasurementsPhysical Review Letters, 2005
- Quantum search by local adiabatic evolutionPhysical Review A, 2002
- Ising Spin Glasses in a Magnetic FieldPhysical Review Letters, 1999
- Quantum Annealing of a Disordered MagnetScience, 1999