paper

Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches

arXiv:1604.01746 · doi:10.1103/PhysRevA.94.022337

Abstract

To date, a conclusive detection of quantum speedup remains elusive. Recently, a team by Google Inc.~[V.~S.~Denchev {\em et al}., Phys.~Rev.~X {\bf 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.

14 pages, 8 figures, 4 tables

References in corpus (14)

Cited by in corpus (67)