# Exact ground states of Ising spin glasses

## Contents |

### Introduction

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).

### Definitions

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

or the bimodal ±*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
ω = (*S*_{1},...,*S*_{n}) is

where the sum runs over the coupled spins.

### Modelling an Ising spin glass as a graph

We identify the spins with the node set *V* = {1,...,*n*} of
a graph *G* = (*V*,*E*).
Two nodes *i* and *j* are connected by an edge *e* ∈ *E* if and
only if spin *i* and *j* are coupled by a
nonzero coupling strength *J*_{ij}≠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* ∈ *V*.
We set the weight of edge (*i*,*j*) ∈ *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

A spin configuration ω corresponds to a partition of
the nodes *V*_{0} = *V*^{ + }∪*V*^{ − }, where
*V*^{ + }: = {*i* ∈ *V*_{0} | *S*_{i} = + 1} and
*V*^{ − }: = {*i* ∈ *V*_{0} | *S*_{i} = − 1}.
We split the sum in the right hand side of *H*(ω) as

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

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*^{ + } ⊆ *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×3 grid with periodic boundary conditions, ±*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.

Therefore, determining ground states of Ising spin glasses is
-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 ±*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
-hard for all kinds of spin interactions .
Furthermore, the Ising spin glass in three dimensional grids is
-hard [Barahona(1982)] .