KBD algorithm

The KBD algorithm is a cluster update algorithm designed for the fully frustrated Ising model in two dimensions, or more generally any two dimensional spin glass with frustrated plaquettes arranged in a checkered pattern. It is discovered in 1990 by Daniel Kandel, Radel Ben-Av, and Eytan Domany, and generalized by P. D. Coddington and L. Han in 1994. It is the inspiration for cluster algorithms used in quantum monte carlo simulations.

The KBD algorithm is a cluster update algorithm designed for the fully frustrated Ising model in two dimensions, or more generally any two dimensional spin glass with frustrated plaquettes arranged in a checkered pattern. It is discovered in 1990 by Daniel Kandel, Radel Ben-Av, and Eytan Domany, and generalized by P. D. Coddington and L. Han in 1994. It is the inspiration for cluster algorithms used in quantum monte carlo simulations. We begin by decomposing the square lattice down into plaquettes arranged in a checkered pattern (such that the plaquettes only overlap vertex-wise but not edge-wise). Since the spin model is fully-frustrated, each plaquette must contain exactly one or three negative interactions. If the plaquette contains three negative interactions, then no bonds can be formed. However, if the plaquette contains one negative interaction, then two parallel bonds can be formed (perpendicular to the negative edge) with probability p = 1-e^{-4\beta} , where \beta is the inverse temperature of the spin model. The bonds will then form clusters on the lattice, on which the spins can be collectively flipped (either with the SW rule or the Wolff rule ). It can be shown that the update satisfies detailed balance, meaning that correctness is guaranteed if the algorithm is used in conjunction with ergodic algorithms like single spin-flip updates.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1317063592 under CC BY-SA 4.0; modifications have been made.