Replica cluster move

The Chayes-Matcha-Redner (CMR) representation is a graphical representation of the Ising spin glass[2] which extends the standard FK representation. It is based on the observation that the total Hamiltonian of two independent Ising replicas α and β,

${\displaystyle H=-\sum _{<ij>}J_{ij}{\big (}\sigma _{i}^{\alpha }\sigma _{j}^{\alpha }+\sigma _{i}^{\beta }\sigma _{j}^{\beta }{\big )},}$

can be written as the Hamiltonian of a 4-state clock model.[4] To see this, we define the following mapping

${\displaystyle (\sigma ^{\alpha },\sigma ^{\beta })\to \theta$ :\quad {\big \{}(+1,+1),(+1,-1),(-1,-1),(-1,+1){\big \}}\mapsto {\big \{}0,{\frac {\pi }{2}},\pi ,{\frac {3\pi }{2}}{\big \}},}

where ${\displaystyle \theta }$ is the orientation of the 4-state clock,[5] then the total Hamiltonian can be represented as

${\displaystyle H=-2J_{ij}\sum _{<ij>}\cos(\theta _{j}-\theta _{i}).}$

In the graphical representation of this model, there are two types of bonds that can be open, referred to as blue and red.[2] To generate the bonds on the lattice, the following rules are imposed:

• If ${\displaystyle J_{ij}\cos(\theta _{j}-\theta _{i})=1}$, or when the interactions on edge ${\displaystyle (i,j)}$ are satisfied on both replicas, then a blue bond is open with probability ${\displaystyle p_{\text{blue}}=1-e^{-4\beta |J_{ij}|}}$.
• If ${\displaystyle J_{ij}\cos(\theta _{j}-\theta _{i})=0}$, or when the interaction on edge ${\displaystyle (i,j)}$ is satisfied in exactly one replica, then a red bond is open with probability ${\displaystyle p_{\text{red}}=1-e^{-2\beta |J_{ij}|}}$.
• Otherwise, a closed bond is formed.

Under these rules, it can be checked that a cycle of open bonds can only contain an even number of red bonds.[6][7] A cluster formed with blue bonds is referred to as a blue cluster, and a super-cluster formed together with both blue and red bonds is referred to as a grey cluster.

Once the clusters are generated, there are two types of non-local updates that can be made to the clock states independently in the clock clusters (and thus the spin states in both replicas). First, for every blue cluster, we can flip (or rotate ${\displaystyle 180^{\circ }}$) the clock states with some arbitrary probability. Following this, for every grey cluster (blue clusters connected with red bonds), we can rotate all the clock states simultaneously by a random angle.

It can be shown that both updates are consistent with the bond-formation rules, and satisfy detailed balance.[2] Therefore, an algorithm based on this CMR representation will be correct when used in conjunction with other ergodic algorithms. However, the algorithm is not necessarily efficient, as a giant grey cluster will tend to span the entire lattice at sufficiently low temperatures (e.g. even at paramagnetic phases of spin-glass models).

The Houdayer cluster move is a simpler cluster algorithm based on a site percolation process on sites with negative spin overlaps. It is discovered by Jerome Houdayer in 2001.[8] For two independent Ising replicas, we can define the spin overlap as

${\displaystyle q_{i}=\sigma _{i}^{\alpha }\sigma _{j}^{\beta },}$

and a cluster is formed by randomly selecting a site and percolating through the adjacent sites with ${\displaystyle q=-1}$ (with a percolation ratio of 1) until the maximal cluster is formed. The spins in the cluster are then exchanged between the two replicas. It can be shown that the exchange update is isoenergetic, meaning that the total energy is conserved in the update. This gives an acceptance ratio of 1 as calculated from the Metropolis-Hastings rule. In other words, the update is rejection-free.