Solving spin glasses with optimized trees of clustered spins

We present an algorithm for the optimization and thermal equilibration of spin glasses, or more generally, cost functions of the Ising form $H={\sum }_{\langle ij\rangle }{J}_{ij}{s}_i{s}_j+{\sum }_i{h}_i{s}_i$, defined on graphs with arbitrary connectivity. The algorithm consists of two repeated steps: (i) the optimized construction of a random tree of spin clusters on the input problem graph, and (ii) the thermal sampling of the generated tree. The randomly generated trees are constructed so as to optimize a balance between the size of the tree and the complexity required to draw Boltzmann samples from it. We benchmark the algorithm on several classes of problems and demonstrate its advantages over existing approaches.

Figure 1

(a) A tree of clustered spins. Each tree node is a group, or a cluster, of spins that may or may not have edges between them. Edges between two tree nodes appear if and only if there are Ising interactions between their spins. (b) A tree of clustered spins embedded in a larger input problem graph. The tree nodes are marked with light blue ellipses encircling individual spins in the tree (green circles). Red circles are spins not belonging to the tree. The numerical labels denote the distance of a node to the tree root (labeled by 0).

Figure 2

Cycle contraction. When considering the addition of a spin (green circle) to an existing tree that forms a cycle with the tree, the structure can retain its tree form if the cycle is contracted by joining together existing nodes. In both examples depicted above, the addition of the new spin closes a cycle, or cycles, and may therefore warrant a contraction, i.e., the unification of existing nodes. In the present algorithm, nodes that are equidistant from the root node are joined together. After the cycle is contracted, the subgraph remains a tree of clustered spins (containing no cycles).

Figure 3

A random construction of a tree of clustered spins. (a) The input Ising problem graph. (b) A root node for the tree that is to be thermalized is chosen at random. (c) A random neighbor of the root is added to the growing tree. (d) All possible neighbors are added. (e) and (f) A “level-two” spin is chosen but can only be added on if two level-one spins “contract” to form a single cluster. (g) Another level-two spin is added. (h) The entire (visible) input graph, but one excluded spin, has become a tree of clustered spins.

Figure 4

A tree of fixed-size spin clusters. The connectivity graph is a randomly generated tree with 20 four-spin nodes. Edges exist between all the spins within a given node and between spins of neighboring nodes.

Figure 5

Typical optimization runtimes of single spin-flip (SSF) parallel tempering, random trees of single spins (TSS), and optimized random trees of spin clusters (TOSC) on random instances of trees of fixed-size clusters. Runtimes are shown on a log-log scale as a function of problem size. From left to right, the cluster sizes considered are $C=1$, 2, 4, and 6. While all three algorithms exhibit power-law scaling, the SSF and TSS algorithms scale with powers that grow with $C$, whereas the TOSC algorithm runtime scales linearly with problem size regardless of cluster size.

Figure 6

Average ratio of tree size $\langle \left|\mathbf{t}\right|\rangle$ to problem size $N$ of TSS and TOSC on random instances of trees of fixed-size clusters. While trees of single spins cover less and less of the input graph with growing cluster size $C$, the TOSC tree sizes tend to cover the entire input graph in the large problem size limit.

Figure 7

Typical runtimes to thermalization of single spin-flip (SSF) parallel tempering, random trees of single spins (TSS), and optimized random trees of spin clusters (TOSC) on random instances of trees of fixed-size clusters. Runtimes are shown on a log-log scale as a function of problem size. From left to right, the cluster sizes considered are $C=1$, 2, and 4. While all three algorithms exhibit power-law scaling, TOSC scales favorably with size as compared to SSF and TSS with a scaling that approaches linear as cluster size grows.

Figure 8

A two-cell by three-cell section of a Chimera graph. Each cell is a bipartite $K_{4,4}$ graph. Spins are connected either horizontally or vertically to similarly positioned spins in adjacent cells.

Figure 9

Performance of TOSC against SSF and TSS on random Range 1 and Range 3 Chimera instances. (a) Runtime scaling for Range 1 problems. (b) Runtime scaling for Range 3 problems. (c) Average tree size $\langle \left|\mathbf{t}\right|\rangle$ to problem size $N$ as a function of problem size for both TSS and TOSC. Also shown is the average TOSC cluster size $\langle \left|\mathbf{s}\right|\rangle$ (dashed line).

Figure 10

Algorithmic scaling of TOSC, TSS, and SSF on random Chimera instances of size $N=512$. While for both SSF and TSS the runtime scaling with mixing time is approximately linear (with a slope slightly less 1), the TOSC scaling is about three times milder, exhibiting a superior robustness against thermal hardness.