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

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 $\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.

Figure 1

Sketch of the weak-strong clusters and networks. (a) Structure of a weak-strong cluster. Two ${\text{K}}_{4,4}$ cells of the chimera lattice are connected ferromagnetically (blue lines, $J=1$), as well as all spins within each ${\text{K}}_{4,4}$ cell. Black dots correspond to qubits in the strong cluster with a biasing magnetic field $h_1=-1$. The white dots represent the weak cluster, where each site is coupled to a weaker field $h_2=-\lambda h_1$ with $\lambda =0.44<0.5$ in the opposite direction. The white lines represent the connections from the strong cluster to neighboring strong clusters of a weak-strong pair. (b) Weak-strong cluster network: each rectangle represents a weak-strong cluster. The different weak-strong clusters are connected via a spin-glass backbone where the interactions can take values $J_{\overline{x}{\overline{x}}^{\prime }}=\pm 1$. Here, red lines represent $J=-1$. Note that the connections between clusters only occur between the strong clusters.

Figure 2

Top panel: computational scaling (for 99% success) for different classical algorithms compared with the experimental results using the $\mathrm{DW}2\mathrm{X}\mathrm{chip}$ [47]. As one can see, both general classical algorithms [isoenergetic cluster moves (ICM) either using parallel tempering (PT) or replica Monte Carlo (RMC)] and tailored classical algorithms for the weak-strong cluster model [hybrid cluster moves (HCM), super-spin approximation (SS), Hamze–de-Freitas–Selby (HFS)] have a comparable scaling with the quantum inspired classical algorithm [quantum Monte Carlo (QMC)] and the $\mathrm{DW}2\mathrm{X}\mathrm{device}$ [72]. Moreover, for the classical tailored algorithms, the overall scaling prefactor is also comparable with the $\mathrm{DW}2\mathrm{X}\mathrm{device}$. For HCM, random instances with $no$ broken qubits have been used. Bottom panel: analysis of the scaling factors by using either linear regression, or a log-corrected regression for ${log}_{10}{T}_{\text{ann}}$. In the figure, bars represent the confidence intervals. For the scaling analysis, we used a stretched exponential that fits better the numerical data (see Appendix pp1). Interestingly, the general-purposes classical algorithm ICM, together with the chimera-optimized classical algorithm (HFS) and the cluster-optimized algorithms (HCM and SS) have the best scaling. (QMC and SA data taken from Ref. [47].) All the simulations (excluding HCM) have been run on the same instances used in [47].

Figure 3

Double-scaling effect produced by the combination of a noisy system and a nonoptimal annealing time. We display data for the $\mathrm{DW}2\mathrm{X}\mathrm{device}$ (as in [47]) compared to the annealing of a noisy two-energy level model (2LV) with a nonoptimal (linear) annealing schedule and a fixed total annealing time ($T_{\text{ann}}=500$). The numerical study shows that, for small systems, the scaling is mainly dominated by the noise while, for large systems, the scaling is mainly dominated by the asymptotic behavior.

Figure 4

Three representative overlap distributions $P\left(q\right)$ for different problem sizes $n$. The $y$ axes are in arbitrary units and rescaled such that ${\int }_0^{1}P\left(q\right)=1$. While some instances have either one dominant narrow valley or valleys with thin barriers that allow for finite-range tunneling (top), others have multiple structures (middle and bottom), suggesting that the valleys are separated by barriers that might be too wide for any finite-range tunneling to be beneficial during the optimization.

Figure 5

Ratio of single-peak to multipeak overlap distributions as a function of the number of qubits $n$. For increasing system size, multipeak instances with barriers too wide for finite-range tunneling increase due to the influence of the spin-glass backbone. Note that already for the largest system size studied, multivalley instances dominate.

Figure 6

Values for the remaining fit parameters $a$ and $c$ for either the log-corrected fit $a+b\sqrt{n}+c{log}_{10}\left(\sqrt{n}\right)$ or the linear fit $a+b\sqrt{n}$. In the panels, bars represent the confidence interval.

Figure 7

Scaling analysis of ${log}_{10}{T}_{\text{ann}}$ by using a log-corrected fit of the form $f\left(n\right)=a+b\sqrt{n}+c{log}_{10}\left(\sqrt{n}\right)$, where $n$ is the number of qubits. The panels show the values of the fit parameters and how well the function $f\left(n\right)$ fits the data.

Figure 8

Scaling analysis of ${log}_{10}{T}_{\text{ann}}$ by using a linear fit of the form $f\left(n\right)=a+b\sqrt{n}$, where $n$ is the number of qubits. The panels show the values of the fit parameters and how well $f\left(n\right)$ fits the data. For the fit, only the last three data points are used.