Patch-planting spin-glass solution for benchmarking

We introduce an algorithm to generate (not solve) spin-glass instances with planted solutions of arbitrary size and structure. First, a set of small problem patches with open boundaries is solved either exactly or with a heuristic, and then the individual patches are stitched together to create a large problem with a known planted solution. Because in these problems frustration is typically smaller than in random problems, we first assess the typical computational complexity of the individual patches using population annealing Monte Carlo, and introduce an approach that allows one to fine-tune the typical computational complexity of the patch-planted system. The scaling of the typical computational complexity of these planted instances with various numbers of patches and patch sizes is investigated and compared to random instances.

Figure 1

Schematic diagram of the patch-planting method for a two-dimensional lattice. First, the ground state for each (easily solvable) patch (A–D) is computed using free boundary conditions. Then a ground state configuration of each patch is selected. Edge spins between the patches are represented by empty and full circles. Couplers between the edge spins between adjacent patches are added under the condition that all interactions are satisfied, i.e., if two spins have the same value (i.e., both full or both empty circles), a ferromagnetic coupler (straight blue line) is added. If, however, two adjacent spins are different, then an antiferromagnetic coupler (red wiggly line) is added. The direct product of the ground state of the patches A–D is then the ground state of the large planted system.

Figure 2

Distribution of $Я$ [defined in Eq. (3)] for various system sizes [$L=4$ (a), 8 (b), 12 (c), 16 (d), and 20 (e)] in three space dimensions. For increasing system size, the typical complexity of the problems grows, which is mirrored by the distributions of $Я$ shifting to the right.

Figure 3

Correlation of the probability to find the ground state of simulated annealing $p_{\mathrm{SA}}$ and the log of entropic family size of population annealing $Я$ for three-dimensional systems with $L=4$ and $L=6$ at $\beta =5$ (data taken from Refs. [45] and [9]). When $Я$ is larger, it is also more difficult to find the ground state, i.e., $p_{\mathrm{SA}}$ is smaller. Note that $p_{\mathrm{SA}}$ drops very rapidly as $L$ increases, while it is easier to measure $Я$.

Figure 4

Scaling of the logarithm of the entropic family size $Я={log}_{10}{\rho }_s$ by varying the number of patches $M$ (triangles, labeled with “PP”). The line is a power-law fit of the form $Я\left(L_0\right)M^{\alpha }$, where $Я\left(L_0\right)$ is $Я$ of a single patch. From the fit, we obtain $\alpha =0.31\left(3\right)$. We also compare to random problems on a three-dimensional lattice (circles). In this case a power-law fit results in ${\alpha }^{\prime }=0.37\left(4\right)$, i.e., the two classes scale similarly, yet with two different exponents.

Figure 5

Scaling exponent $\alpha$ ($Я\sim M^{\alpha }$; see Fig. 4), by varying the patch size $L_0$ but keeping the number of patches fixed to $M=8$.

Figure 6

Comparison of the distribution of $Я$ for $L=16$ in three space dimensions, but with different patch sizes $L_0=4$ (a) and 8 (b). There is a noticeable shift in the distributions of $Я$. Therefore, to patch harder instances, one should use as large patch sizes as possible.

Figure 7

Distributions of $Я$ for $M=8$ ($L=12$) patches of size $L_0=6$ using either easy patches (a) or hard patches (b). As expected, the distribution shifts to the right when harder patches are used.

Figure 8

Comparison of the typical complexity of the patched instances with random instances. The patched instances shown in panels (b), (d), and (e) are generally computationally easier than their random counterparts shown in panels (a) and (c), for a given system size. Note the overlap between the distributions, i.e., by mining the data one can obtain very hard patched problems.

Figure 9

Sketch of the different patch geometries used on the D-Wave 2X quantum annealer chip. Each gray block represents a ${\mathrm{K}}_{44}$ call with 8 sites. (a) A zoom of such cell. (a–d) The shading represents the different patches used from $M=1$ (a) to $M=4$ (d).

Figure 10

Distributions of $Я$ on a chimera graph with $N=1097$ for random instances and patched instances with different number of patches $M$. There are 1000 instances each, and the patched instances were chosen from the hardest ones out of ${10}^4$ instances in each class. Note that the patched problems with $M=2$ (b) and random (a) are comparable. Panels (c) and (d) show that problems become easier for smaller patches, i.e., a larger number of patches.

Figure 11

Sorted probabilities to find the ground state $p_{\mathrm{succ}}$ from experiments with the D-Wave 2X quantum annealer for $N=1097$ sites and different number of patches $M$. As in Fig. 10, random instances and instances with $M=2$ are comparable.

Figure 12

Correlation of $Я$ and $p_{\mathrm{succ}}$ for experiments on the D-Wave machine with $N=1097$. Data for random instances, as well as instances with different numbers of patches $M$.