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

TLDR

Quantum speedup detection remains elusive, and Google’s weak‑strong cluster model was introduced to emphasize finite‑range tunneling across tall, narrow energy barriers. The paper reviews sequential, non‑tailored, and specialized tailored algorithms on Google’s weak‑strong cluster instances to assess their performance. Quantum Monte Carlo and the D‑Wave 2X annealer outperform simulated annealing, with the latter running ~10⁸ times faster on ~10³‑variable problems, yet the observed speedup is confined to sequential methods and the benchmark’s complexity aligns with spin‑glass behavior.

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 $\sim 10^8$ times faster than simulated annealing on conventional computer hardware for problems with approximately $10^3$ 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.