Exact ground states of Ising spin glasses
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 spins. Spins and might be coupled with coupling strength . Usually, the couplings are either Gaussian distributed following the probability distribution with
or the bimodal distribution, with negative values is used. We study Ising spins, i.e. the spin variable for spin is one-dimensional and can take only the two values or .
An external magnetic field of strength might be present. The energy (Hamiltonian) of a system with spin configuration 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 of a graph . Two nodes and are connected by an edge if and only if spin and are coupled by a nonzero coupling strength .
For modelling the external field, we introduce a new node 0 representing the source of the field and having spin . Node 0 is connected via an edge to all other spins . We set the weight of edge as .
We let the graph consist of the nodes and edges of together with the field node 0 and the field edges . By setting the field couplings as , we can write the Hamiltonian as
A spin configuration corresponds to a partition of the nodes , where and . We split the sum in the right hand side of 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 .
Hence, minimizing the Hamiltonian is equivalent to maximizing the weight of the cut in the graph over all possible sets . 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 grid with periodic boundary conditions, interactions and no external field.
The first figure shows the instance of the max-cut problem. The solid lines have edge weight (i.e., the coupling strength in the spin-glass instance is ), the dashed lines weight . 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 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)] .