Spin Glass

Problem Definition

Spin Glass is a type of disordered magnetic system that exhibits a glassy behavior. The Hamiltonian of the system on a simple graph $G$ is given by

\[H(G, \sigma) = \sum_{(i,j) \in E(G)} J_{ij} \sigma_i \sigma_j\]

where $J_{ij}$ is the coupling strength between spins $i$ and $j$ and $\sigma_i$ is the spin variable that can take values in $\{-1, 1\}$.

This definition naturally extends to the case of a HyperGraph.

Interfaces

To define a SpinGlass problem, we need to specify the graph, the coupling strength $J_{ij}$, and possibly the external field $h_i$ for each spin $i$.

julia> using ProblemReductions, ProblemReductions.Graphs
julia> graph = smallgraph(:petersen){10, 15} undirected simple Int64 graph
julia> J = rand([1, -1], ne(graph))  # coupling strength15-element Vector{Int64}:
  1
 -1
 -1
  1
  1
 -1
 -1
  1
 -1
  1
  1
  1
 -1
 -1
  1
julia> h = rand([1, -1], nv(graph))  # external field10-element Vector{Int64}:
 -1
  1
  1
 -1
  1
 -1
  1
 -1
  1
 -1
julia> spinglass = SpinGlass(graph, J, h)  # Define a spin glass problemSpinGlass{HyperGraph, Vector{Int64}}(HyperGraph(10, [[1, 2], [1, 5], [1, 6], [2, 3], [2, 7], [3, 4], [3, 8], [4, 5], [4, 9], [5, 10]  …  [1], [2], [3], [4], [5], [6], [7], [8], [9], [10]]), [1, -1, -1, 1, 1, -1, -1, 1, -1, 1  …  -1, 1, 1, -1, 1, -1, 1, -1, 1, -1])

Here, we also define an external field $h_i$ for each spin $i$. The resulting spin glass problem is defined on a HyperGraph, where external fields are associated with hyperedges connecting single spins.

The required functions, variables, flavors, and evaluate, and optional functions, findbest, are implemented for the spin glass problem.

julia> variables(spinglass)  # degrees of freedom10-element Vector{Int64}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
julia> flavors(spinglass)  # flavors of the spins2-element Vector{Int64}:
  1
 -1
julia> evaluate(spinglass, [0, 1, 1, 0, 1, 1, 1, 0, 0, 1])  # energy of a configurationERROR: AssertionError: all((x->begin
            #= /home/runner/work/ProblemReductions.jl/ProblemReductions.jl/src/models/SpinGlass.jl:68 =#
            x == -1 || x == 1
        end), config)
julia> findbest(spinglass, BruteForce())  # solve the problem with brute force27-element Vector{Vector{Int64}}:
 [1, -1, 1, 1, -1, 1, 1, 1, 1, 1]
 [1, -1, 1, 1, -1, -1, 1, 1, 1, 1]
 [-1, -1, 1, 1, -1, -1, 1, 1, 1, 1]
 [1, -1, 1, 1, -1, 1, 1, -1, 1, 1]
 [1, -1, -1, 1, -1, 1, 1, -1, 1, 1]
 [1, -1, 1, 1, -1, 1, 1, 1, -1, 1]
 [1, -1, 1, 1, -1, 1, -1, 1, -1, 1]
 [1, -1, -1, -1, 1, 1, 1, -1, -1, 1]
 [1, -1, 1, 1, -1, 1, 1, -1, -1, 1]
 [1, -1, -1, 1, -1, 1, 1, -1, -1, 1]
 ⋮
 [-1, 1, -1, -1, -1, 1, -1, -1, -1, 1]
 [1, -1, -1, -1, -1, 1, -1, -1, -1, 1]
 [1, -1, 1, 1, 1, 1, -1, 1, -1, -1]
 [1, -1, 1, -1, 1, 1, -1, 1, -1, -1]
 [1, 1, -1, -1, 1, 1, -1, 1, -1, -1]
 [1, -1, -1, -1, 1, 1, -1, 1, -1, -1]
 [1, -1, 1, 1, -1, 1, -1, 1, -1, -1]
 [1, 1, -1, -1, 1, 1, -1, -1, -1, -1]
 [1, -1, -1, -1, 1, 1, -1, -1, -1, -1]