Spin glasses are disordered magnetic systems where spins can interact with random ferromagnetic or antiferromagnetic couplings. The goal is to minimize the system's energy — finding the global minimum of a highly non-convex energy landscape (often modeled as an Ising model with random couplings).

To compare algorithms for solving spin glass problems, it's important to understand how each method tackles the problem of finding ground states in highly rugged and frustrated energy landscapes. Here's a breakdown of the comparison between:

• (a) Greedy algorithms
• (b) Simulated annealing (SA)
• (c) Parallel tempering (PT)

Implementation Snippets

Let's walk through a minimal version of each algorithm, assuming a 2D Ising model where each spin $s_i \in \{-1,+1\}$.

https://gist.github.com/viadean/504198820de5c1c366685c39097b5c9f

Notes:

• J[i][j] is the coupling matrix (random ±1 or Gaussian).
• Each method assumes spins initialized randomly: spins = [random.choice([-1, 1]) for _ in range(N)].
• For PT, we initialize multiple such spin states (replicas) at different temperatures.

https://gist.github.com/viadean/ea54338a3c4961da2cabb47ade0dae7c

Here’s the Energy vs. Iteration plot comparing the three algorithms on a smaller spin glass problem:

Observations:

• Greedy: Quickly drops energy but gets stuck — classic local minima behavior.
• Simulated Annealing: Slower, smoother descent, escapes some traps, better final energy.
• Parallel Tempering: Most consistent energy drop and lowest final energy — despite slower start.

This clearly shows PT’s advantage in escaping local minima by using multiple temperature layers.