Probing for quantum speedup in spin-glass problems with planted solutions
Top Cited Papers
Open Access
- 23 October 2015
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 92 (4) , 042325
Abstract
The availability of quantum annealing devices with hundreds of qubits has made the experimental demonstration of a quantum speedup for optimization problems a coveted, albeit elusive goal. Going beyond earlier studies of random Ising problems, here we introduce a method to construct a set of frustrated Ising-model optimization problems with tunable hardness. We study the performance of a D-Wave Two device (DW2) with up to 503 qubits on these problems and compare it to a suite of classical algorithms, including a highly optimized algorithm designed to compete directly with the DW2. The problems are generated around predetermined ground-state configurations, called planted solutions, which makes them particularly suitable for benchmarking purposes. The problem set exhibits properties familiar from constraint satisfaction (SAT) problems, such as a peak in the typical hardness of the problems, determined by a tunable clause density parameter. We bound the hardness regime where the DW2 device either does not or might exhibit a quantum speedup for our problem set. While we do not find evidence for a speedup for the hardest and most frustrated problems in our problem set, we cannot rule out that a speedup might exist for some of the easier, less frustrated problems. Our empirical findings pertain to the specific D-Wave processor and problem set we studied and leave open the possibility that future processors might exhibit a quantum speedup on the same problem set.Keywords
All Related Versions
Funding Information
- U.S. Department of Energy (DE-AC05-00OR22725)
- Army Research Office (W911NF-12-1-0523, W911NF-11-1-0268)
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
- European Research Council (SIMCOFE)
This publication has 45 references indexed in Scilit:
- Quantum annealing: The fastest route to quantum computation?The European Physical Journal Special Topics, 2015
- Goals and opportunities in quantum simulationNature Physics, 2012
- Quantum annealing with manufactured spinsNature, 2011
- Quantum computersNature, 2010
- Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising modelPhysical Review B, 2002
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- Quantum annealing: A new method for minimizing multidimensional functionsChemical Physics Letters, 1994
- Global energy minimum searches using an approximate solution of the imaginary time Schroedinger equationThe Journal of Physical Chemistry, 1993
- Quantum stochastic optimizationStochastic Processes and their Applications, 1989
- Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuationsPhysical Review B, 1989