Exact Ground States of Spin Glasses

The Spin Glass Ground State Server

One of the dominant themes in the history of physics in this century has been the effort to understand condensed states of matter. This began with very simple systems and has gradually developed to include more and more complex and subtle states and phenomena. Spin Glasses are the current frontier in this development, the most complex kind of condensed state encountered so far in solid state physics.

In trying to understand these systems, experimentalists have used a wide spectrum of probes in ingenious ways, and theorists have invented an equally wide variety of models and new theoretical concepts. The resulting developments have had an impact, not only on other parts of physics, but also on other fields such as computer science, mathematics, and biology.

Though the main target surely is to get a deep understanding of these systems which should result in a closed theory about these complex phenomena, experiments to study spin glass behaviour are very important. `Experiments' that are performed on computers can also give information about the validity of modelling systems in a certain way.

What is a spin glass?

The simplest answer is that it is a collection of spins (i.e. magnetic moments) whose low-temperature state is a frozen disordered one, rather than the kind of uniform or periodic pattern we are accustomed to find in conventional magnets. It appears that in order to produce such a state, two ingredients are necessary:

There must be competition among the different interactions between the moments, in the sense that no single configuration of the spins in uniquely favoured by all interactions (this is commonly called `frustration').
These interactions must be at least partially random.

Experimentally, it does not seem hard to find spin glasses. Quite the contrary, spin glass behaviour has been seen in virtually every kind of systems which people have been able to make that satisfies these requirements.

What is our spin glass model?

We study Ising spins, i.e., spins that can either be `up' or `down'. They interact with each other when they are nearest neighbors on the underlying regular grid.
In the next figure, you see a one-dimensional spin glass of size 6:

1D Spin Glass planar

In this kind of system no frustration can occur. But if we impose periodic boundary conditions, as one usually does to model `infinite' systems one might get the situation you see in the next figure. Here the leftmost spin interacts with the rightmost one.

1D Spin Glass periodic boundary condition

The leftmost spin `wants' to align with the rightmost spin, because of the positive interaction between them. This interaction which cannot be satisfied leads to the so-called frustration. In this situation, no configuration of `up' and `down' spins exists, which satisfies all interactions. The depicted configuration is nevertheless a ground state, since it only leaves one interaction unsatisfied. It minimizes the energy which increases with the number of unsatisfied interactions. If the interactions are allowed to differ also in magnitude (not only in sign), the situation is a little bit more complicated.

What we do:

The systems we investigate are two- or three-dimensional Ising spin glass systems with periodic boundary conditions. The interactions differ either only in sign (+/- J) or also in magnitude (Gaussian distribution). Here you see a ground state of a 8 x 8 spin glass (lines are drawn where negative interactions take effect) and one of a 70 x 70 spin glass (interactions are not shown).

2D Spin Glass 8x8 2D Spin Glass 70x70

If one computes the ground state configuration of these systems one can get information about many properties. The special thing we do is that we transform the problem of finding a spin configuration with lowest energy to the problem of finding a cut of maximum weight in a weighted graph (MAXCUT-Problem).

We solve these problems to optimality using a Branch-and-Cut approach (References). With our method we can compute two-dimensional systems of size up to 100 x 100 (Gaussian distribution, 60 x 60 for +/-J) within moderate computation time (at most 4 hours on average).

Since three-dimensional spin glasses lead to much harder MAXCUT-problems, the computational effort is much higher. We are currently working on the problem of solving these instances faster.

Smaller (2D) systems are solvable very quickly, so we are able to run big numbers of samples to get statistically stable answers to certain questions. What kind of properties we study is explained in the papers mentioned below.