Computing Exact Ground States of Ising Spin Glasses
A spin-glass instance in the Ising model is given by n spins that can
either point up or down. Spin i and j are
coupled with coupling strength Jij. We mainly
consider systems in which spins are
located on the sites of a d-dimensional
lattice with nearest neighbor interactions.
The Hamiltonian energy function H is given by
where the sum runs over all coupled spins. For a spin i pointing up, its spin variable Si takes value
Si=1,
otherwise Si=-1. A ground state is a spin
configuration that attains the global minimum
of the energy function H. In contrast to
heuristic algorithms used by many physicists,
we determine provably exact ground states. Calculating
an exact ground state of a spin glass in the
Ising model amounts to determining a maximum
cut in the associated graph of
interactions. The algorithm has been
developed at the Computer Science Department in
Cologne in collaboration with several other
researchers. It is quite effective in practice and makes it possible
to gain further insight into the ruling physics of the systems.
