Exact ground states of Ising spin glasses

From Cophy

Contents 1 Introduction 2 Definitions 3 Modelling an Ising spin glass as a graph

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₁,...,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₀. 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₀ = (V₀,E₀) 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₀ = V ⁺ ∪V ⁻ , where V ⁺ : = {i ∈ V₀ | S_i = + 1} and V ⁻ : = {i ∈ V₀ | 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₀ 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)] .