Exact ground states of Ising spin glasses

From cophywiki
Jump to: navigation, search


This article gives a model for computing the ground states for a special case of spin glasses where each spin has just two states (Ising spin glasses). In this model a configuration/state can be represented as a cut in the graph of interactions. Furthermore the energy of such states correspond to the cut values and computing a maximum cut yields a so called ground state of the instance (cf. spin glass).


Let a spin glass consist of n spins. Spins i and j might be coupled with coupling strength J_{ij}. Usually, the couplings are either Gaussian distributed following the probability distribution P(J) with

 P(J) = \frac{1}{\sqrt{2\pi}} \exp ( -J^2/2 ).

or the bimodal \pm J distribution, with 50\% negative values is used. We study Ising spins, i.e. the spin variable S_{i} for spin i is one-dimensional and can take only the two values +1 or -1.

An external magnetic field of strength h might be present. The energy (Hamiltonian) of a system with spin configuration \omega=(S_1,\ldots,S_n) is

 H(\omega) = -\sum\limits_{(ij)} J_{ij}S_{i} S_{j}-h\sum\limits_{i=1}^n S_{i}, \,\!

where the sum \scriptstyle\sum\limits_{(ij)} runs over the coupled spins.

Modelling an Ising spin glass as a graph

We identify the spins with the node set V=\{1,\ldots,n\} of a graph G=(V,E). Two nodes i and j are connected by an edge e \in E if and only if spin i and j are coupled by a nonzero coupling strength J_{ij} \neq 0.

For modelling the external field, we introduce a new node 0 representing the source of the field and having spin S_{0}. Node 0 is connected via an edge (0,i) to all other spins i \in V. We set the weight of edge (i,j) \in E as c_{ij} := - J_{ij}.

We let the graph G_{0}=(V_{0}, E_{0}) consist of the nodes and edges of G together with the field node 0 and the field edges (0,i). By setting the field couplings c_{0i}=J_{0i} as c_{0i}=J_{0i}=h, we can write the Hamiltonian as

H(\omega)=-\sum\limits_{(ij) \in E_0} J_{ij}S_i S_j.\,\!

A spin configuration \omega corresponds to a partition of the nodes V_0=V^+ \cup V^-, where V^+ := \{ i \in V_{0} \mid S_i=+1\} and V^- := \{i \in V_{0} \mid S_i=-1\}. We split the sum in the right hand side of H(\omega) as

    H(\omega) = -\sum\limits_{(i,j) \in E_{0},\; S_i = S_j} J_{ij} \; +
    \sum\limits_{(i,j) \in E_{0},\; S_i \neq S_j} J_{ij} \;\!

We add to both sides of the equation the sum of all couplings in the graph which is a constant and end up with

    H(\omega) + \sum\limits_{(ij) \in E_{0}} J_{ij} = 2 \sum\limits_{(ij) \in
      \delta (V^+)} J_{ij}.\,\!

Therefore, we have expressed the energy function in terms of cuts in G.

Hence, minimizing the Hamiltonian is equivalent to maximizing the weight of the cut in the graph G_{0} over all possible sets V^+ \subseteq V. We conclude that determining ground states of Ising spin glasses can be determined by calculating maximum cuts in the graph associated with the spin glass system.

As an example, we show an instance on a 3\times 3 grid with periodic boundary conditions, \pm J interactions and no external field.

The first figure shows the instance of the max-cut problem. The solid lines have edge weight 1 (i.e., the coupling strength in the spin-glass instance is -1), the dashed lines weight -1. The second figure shows an optimum solution. The dash-dotted lines correspond to the cut edges.

Error creating thumbnail: File missing
3x3 config.jpg

Therefore, determining ground states of Ising spin glasses is \scriptstyle\mathcal{NP}-hard in general. However, polynomially solvable cases exist.

For example, the two-dimensional planar Ising spin glass on a lattice with nearest-neighbor interactions, free boundary conditions in at least one direction and no magnetic field amounts to solving a max-cut problem in a planar graph, which is polynomially solvable. Fast programs exist in practice.

The two-dimensional Ising spin glass with periodic boundary conditions, no external magnetic field and \pm J interactions [Saul and Kardar (1994)] is a polynomial problem. More generally, it remains polynomial if the genus of the graph is bounded by a constant and the sizes of the integral edge weights are bounded in absolute value by a polynomial in the size of the graph [Galluccio et al.(2001)] . For (unbounded) Gaussian distributed couplings the question is still open. As soon as an external field is present, the problem becomes \scriptstyle\mathcal{NP}-hard for all kinds of spin interactions . Furthermore, the Ising spin glass in three dimensional grids is \scriptstyle\mathcal{NP}-hard [Barahona(1982)] .