Fair sampling of ground-state configurations of binary optimization problems

Although many efficient heuristics have been developed to solve binary optimization problems, these typically produce correlated solutions for degenerate problems. Most notably, transverse-field quantum annealing—the heuristic employed in current commercially available quantum annealing machines—has been shown to often be exponentially biased when sampling the solution space. Here we present an approach to sample ground-state (or low-energy) configurations for binary optimization problems. The method samples degenerate states with almost equal probability and is based on a combination of parallel tempering Monte Carlo with isoenergetic cluster moves. We illustrate the approach using two-dimensional Ising spin glasses, as well as spin glasses on the D-Wave Systems quantum annealer chimera topology. In addition, a simple heuristic to approximate the number of solutions of a degenerate problem is introduced.

Figure 1

Scatter plot of $Q_{\mathrm{num}}\sqrt{n}$ as a function of the ground-state degeneracy $G-1$ for different spin-glass instances with different system sizes $N$ on a Chimera graph. The data points for $\mathrm{PT}+\mathrm{ICM}$ (blue/darker dots) are closer to the theoretical limit than those from PT (red/lighter dots), and the improvement improves as the system size increases. The dotted line represents ideal uniform sampling of ground-state configurations, i.e., $Q_{\mathrm{num}}/Q_{\mathrm{th}}=1$. Note that any other heuristic, such as simulated or quantum annealing, would perform worse than PT [33, 45]. Data for (a) $N=1152$, (b) $N=800$, (c) $N=512$, (d) $N=288$, and (e) $N=128$.

Figure 2

Median ratio $Q_{\mathrm{num}}/Q_{\mathrm{th}}$ for spin-glass instances on Chimera as a function of the system size $N$. The data points show that $\mathrm{PT}+\mathrm{ICM}$ (blue squares) performs better than PT (red circles) for all system sizes and the gain is more significant with increasing system size. Statistical error bars are determined by a bootstrap analysis.

Figure 3

Scatter plot of $Q_{\mathrm{num}}/Q_{\mathrm{th}}$ as a function of the estimated ground-state degeneracy $G$ for different spin-glass instances with system size $N=800$ on a Chimera graph. Both data for PT and $\mathrm{PT}+\mathrm{ICM}$ suggest that the more ground-state configurations, the easier to sample all ground-state configurations with near-equal probabilities using these heuristics.

Figure 4

Median ratio $Q_{\mathrm{num}}/Q_{\mathrm{th}}$ as a function of Hamming distance for different spin-glass Sidon instances ($J_{ij}\in \{\pm 5,\pm 6,\pm 7\}$) [22] with system size $N=800$ and degeneracy $G=2$ (up to spin reversal symmetry) on a Chimera graph. Data for PT and $\mathrm{PT}+\mathrm{ICM}$ suggest that the larger the Hamming distance between ground-state configurations, the harder it is to sample all ground-state configurations with near-equal probability and the more $\mathrm{PT}+\mathrm{ICM}$ improves fair sampling over PT. Note that the bar chart represents median ratios $Q_{\mathrm{num}}/Q_{\mathrm{th}}$ between Hamming distance $1–2, 2–4, 4–8, 8–16, 16–32$, and $32–400$, respectively. The statistical error bars are determined by a bootstrap analysis. Bars are color coded with the number of instances that have a particular Hamming distance.

Figure 5

Two examples of ground-state configurations with different Hamming distances on a Chimera graph for system size $N=128$. The lines represents the distance between two binary strings (ground-state configurations). Each dot in the figure represents a ground-state configuration, black (thick) lines are 1-bit differences, red lines (medium shade) are 2-bit differences, and lighter colors (light gray or blue) indicate an even greater difference. In the first example (a) all ground-state configurations are related by 1-bit differences, while in the second example (b) the Hamming distances between certain ground-state configurations can be large—which means that it takes longer for the system to move from one ground-state configuration to another, therefore causing larger fluctuations in the ground-state frequency. Larger Hamming distances have been omitted for better visibility.

Figure 6

Scatter plot of $Q_{\mathrm{num}}\sqrt{n}$ as a function of the ground-state degeneracy $G-1$ for different spin-glass instances with different system sizes $N$ on a two-dimensional lattice. The data points for $\mathrm{PT}+\mathrm{ICM}$ (blue/dark color) are closer to the theoretical limit than those for PT (red/light color), and this improvement gets better as the system size increases. Data for (a) $N=1024$, (b) $N=784$, (c) $N=576$, (d) $N=256$, and (e) $N=144$.

Figure 7

Median ratio $Q_{\mathrm{num}}/Q_{\mathrm{th}}$ for spin-glass instances as a function of the system size $N$ on a two-dimensional lattice. The data points show that $\mathrm{PT}+\mathrm{ICM}$ (blue squares) performs better than PT (red circles) for all system sizes, and the gain is more significant with increasing system size. Statistical error bars are determined by a bootstrap analysis.