Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics versus quantum approaches
Open Access
- 29 August 2016
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 94 (2) , 022337
Abstract
To date, a conclusive detection of quantum speedup remains elusive. Recently, a team by Google Inc. [V. S. Denchev et al., Phys. Rev. X 6, 031015 (2016)] proposed a weak-strong cluster model tailored to have tall and narrow energy barriers separating local minima, with the aim to highlight the value of finite-range tunneling. More precisely, results from quantum Monte Carlo simulations as well as the D-Wave 2X quantum annealer scale considerably better than state-of-the-art simulated annealing simulations. Moreover, the D-Wave 2X quantum annealer is times faster than simulated annealing on conventional computer hardware for problems with approximately variables. Here, an overview of different sequential, nontailored, as well as specialized tailored algorithms on the Google instances is given. We show that the quantum speedup is limited to sequential approaches and study the typical complexity of the benchmark problems using insights from the study of spin glasses.
Keywords
All Related Versions
Funding Information
- National Science Foundation (DMR-1151387)
- National Aeronautics and Space Administration (NNX14AF62G)
This publication has 63 references indexed in Scilit:
- Thermally assisted quantum annealing of a 16-qubit problemNature Communications, 2013
- Mathematical foundation of quantum annealingJournal of Mathematical Physics, 2008
- Optimization using quantum mechanics: quantum annealing through adiabatic evolutionJournal of Physics A: General Physics, 2006
- Effects of a random noisy oracle on search algorithm complexityPhysical Review A, 2003
- Monte Carlo studies of the one-dimensional Ising spin glass with power-law interactionsPhysical Review B, 2003
- Quantum search by local adiabatic evolutionPhysical Review A, 2002
- Quantum Annealing of a Disordered MagnetScience, 1999
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- Spin glasses: Experimental facts, theoretical concepts, and open questionsReviews of Modern Physics, 1986
- Optimization by Simulated AnnealingScience, 1983