Exponentially Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians

We study the performance of the D-Wave 2X quantum annealing machine on systems with well-controlled ground-state degeneracy. While obtaining the ground state of a spin-glass benchmark instance represents a difficult task, the gold standard for any optimization algorithm or machine is to sample all solutions that minimize the Hamiltonian with more or less equal probability. Our results show that while naive transverse-field quantum annealing on the D-Wave 2X device can find the ground-state energy of the problems, it is not well suited in identifying all degenerate ground-state configurations associated with a particular instance. Even worse, some states are exponentially suppressed, in agreement with previous studies on toy model problems [New J. Phys. 11, 073021 (2009)]. These results suggest that more complex driving Hamiltonians are needed in future quantum annealing machines to ensure a fair sampling of the ground-state manifold.

Figure 1

Histograms of the number of times a particular ground-state configuration is found using the DW2X quantum annealer ($20\mu \mathrm{s}$ annealing time) sorted by rank. Data for Chimera lattice instances with $N=8c^2$ sites and $N_{\mathrm{GS}}=3\times 2^k$ ground states are shown. The horizontal axis is normalized by $N_{\mathrm{GS}}$ for easier display of the data. In all cases studied, certain ground states are exponentially suppressed (note the vertical logarithmic axis).

Figure 2

Histogram of the number of times a particular ground-state configuration is found using the DW2X quantum annealer ($20\mu \mathrm{s}$ annealing time) sorted by rank, after adding extra Gaussian noise to the couplers with variance ${\sigma }_J^2$ and biases with variance ${\sigma }_h^2$. Data for Chimera lattice instances with $N=8c^2$ sites and $N_{\mathrm{GS}}=3\times 2^k$ ground states are shown. The horizontal axis is normalized by $N_{\mathrm{GS}}$ for easier display of the data. In all cases studied, noise minimally affects the exponential bias of the sampling (note the vertical logarithmic axis).

Figure 3

Histogram of the number of times a particular ground-state configuration is found either using classical heuristics [using the isoenergetic cluster algorithm (ICA) [36] and the Hamze–de Freitas–Selby algorithm (HFS) 40, 41], as well as the DW2X quantum annealer. Example data for Chimera lattice instances with $N=8c^2$ sites and $N_{\mathrm{GS}}=3\times 2^k$ ground states. While the classical algorithms sample the ground-state configurations fairly, the DW2X device has a bias of more than 2 orders of magnitude.

Figure 4

Comparison of ${\mathrm{\Theta }}_{\max }$ (maximum absolute difference of the empiric cumulative distribution with respect to the expected distribution) for the distribution of ground states found by the DW2X against a uniform random distribution. Each point corresponds to a specific instance and the error bars are computed by bootstrapping the data. The closer the points are to the diagonal, the more the ground states for that specific instance have been uniformly sampled. As one can see, DW2X does not uniformly sample the ground states. The example data are for Chimera lattices with $N=8c^2$ sites and $N_{\mathrm{GS}}=3\times 2^k$ ground states. For the analysis, we considered only those instances for which DW2X found at least 50 solutions (independently of the ground-state configuration).

Figure 5

Comparison of ${\mathrm{\Theta }}_{\max }$ (defined as the maximum absolute difference of the empiric cumulative distribution with respect to the expected one) for the distribution of ground states found by the DW2X for two different annealing times, $20\mu \mathrm{s}$ and $200\mu \mathrm{s}$. Each point in the plot corresponds to a specific instance and the error bars are computed by bootstrapping the data. Only instances for which DW2X has found a solution for both annealing times are represented. The data are for Chimera lattice instances with $N=8c^2$ sites and $N_{\mathrm{GS}}=3\times 2^k$ ground states. Even though there is a slight improvement by increasing the total annealing time, ${\mathrm{\Theta }}_{\max }$ remains quite large, thus showing that sampling remains strongly biased even when the annealing time is increased tenfold.