Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0706.2866 · Physical Review B

Matching Kasteleyn cities for spin glass ground states

Creighton K. Thomas, A. Alan Middleton

Published Dec 17, 2007• 41 citations
arXivHTMLPDF

Abstract

As spin glass materials have extremely slow dynamics, devious numerical methods are needed to study low-temperature states. A simple and fast optimization version of the classical Kasteleyn treatment of the Ising model is described and applied to two-dimensional Ising spin glasses. The algorithm combines the Pfaffian and matching approaches to directly strip droplet excitations from an excited state. Extended ground states in Ising spin glasses on a torus, which are optimized over all boundary conditions, are used to compute precise values for ground state energy densities.

DOI
10.1103/physrevb.76.220406

Related papers

Droplets in the two-dimensional ±J Ising spin glass

Alexander K. Hartmann

By using problem-dependent mappings to computer-science problems and by applying sophisticated algorithms, one can numerically study some important problems much better compared to applying standard approaches, such as Monte Carlo simulations. Here, by using calculations of ground states of suitable perturbed systems, droplets are obtained in two-dimensional $\ifmmode\pm\else\textpm\fi{}J$ spin glasses, which are in the focus of a currently very lively debate. By using a sophisticated matching algorithm, exact ground states of large systems up to ${L}^{2}={256}^{2}$ spins can be generated. Furthermore, no equilibration or extrapolation to $T=0$ is necessary. Three different $\ifmmode\pm\else\textpm\fi{}J$ models are studied here: (a) with free boundary conditions, (b) with fixed boundary conditions, and (c) a diluted system wherein a fraction $p=0.125$ of all bonds is zero. For large systems, the droplet energy shows for all three models a power-law behavior ${E}_{\text{dp}}\ensuremath{\sim}{L}^{{\ensuremath{\theta}}_{\text{dp}}^{\ensuremath{'}}}$ with ${\ensuremath{\theta}}_{\text{dp}}^{\ensuremath{'}}<0$. This is different from the previous studies of domain walls, wherein a convergence to a constant nonzero value $({\ensuremath{\theta}}_{\text{DW}}=0)$ was found. After correcting for the noncompactness of the droplets, the results are likely to be compatible with ${\ensuremath{\theta}}_{\text{dp}}\ensuremath{\approx}\ensuremath{-}0.29$ for all three models. This is in accordance with the Gaussian system wherein ${\ensuremath{\theta}}_{\text{dp}}=\ensuremath{-}0.287(4)$ ($\ensuremath{\nu}\ensuremath{\approx}3.5$ via $\ensuremath{\nu}=\ensuremath{-}1/{\ensuremath{\theta}}_{\text{dp}}$). Nevertheless, the disorder-averaged spin-spin correlation exponent $\ensuremath{\eta}$ is determined here via the probability to have a nonzero-energy droplet, and $\ensuremath{\eta}\ensuremath{\approx}0.22$ is found for all three models, in contrast to the model with the Gaussian interactions, where $\ensuremath{\eta}=0$ is exact.

Physical Review B•Apr 18, 2008•20 citations

Large-scale low-energy excitations in the two-dimensional Ising spin glass

Alexander K. Hartmann, A. P. Young

We study large-scale, low-energy excitations in the Ising spin glass with Gaussian interactions in two dimensions at zero temperature, using an optimization algorithm to determine exact ground states. Periodic boundary conditions are applied. Our results for the fractal dimension of the surface, ${d}_{s},$ and stiffness exponent, ${\ensuremath{\theta}}^{\ensuremath{'}},$ for ``droplet'' excitations, are in reasonable agreement with estimates from ``domain wall'' calculations, and so support the predictions of the ``droplet theory.'' Restricting our analysis to small lattices, we do not find an effective value of ${\ensuremath{\theta}}^{\ensuremath{'}}$ close to $\ensuremath{-}0.47$ as has been recently proposed. The effects of averaging over droplets of different sizes are studied and are also found to be too small to give ${\ensuremath{\theta}}^{\ensuremath{'}}\ensuremath{\approx}\ensuremath{-}0.47$ for smaller sizes. Larger corrections to finite-size scaling would be needed in three and four dimensions in order for the numerical data used to support the ``TNT'' scenario to be compatible with the droplet theory prediction that the stiffness exponent is the same for droplets and domain walls.

arXiv:cond-mat/0205659•Physical review. B, Condensed matter•Sep 16, 2002•45 citations

Ground-state properties of the two-dimensional SWAP spin-glass ensemble

Alexander K. Hartmann, Leticia F. Cugliandolo, Marco Tarzia

We study the recently introduced SWAP ensemble for Ising spin-glasses, where the spins obtain varying lengths, with length scale $Δ\in [0, 2]$. The lengths can be exchanged in the spirit of the SWAP algorithm for glassy poly-disperse hard-sphere systems. Using an annealing schedule, if the annealing is slow enough, ground states of the corresponding Ising Hamiltonian, where the spin lengths are incorporated into the bonds, can be obtained with high probability. We prove this statement for two-dimensional systems with sizes of up to $L^2=1024^2$ spins by comparison with exact ground states obtained by using graph matching algorithms. In particular, we analyze the nature of the obtained realizations of the disorder by calculating exact zero-temperature domain-wall energies, from exact ground state calculations using periodic and anti-periodic boundary conditions. For medium or large values of $Δ$, e.g. $Δ=1$, the realizations turn ferromagnetic if the annealing is slow enough, i.e., they lose their zero-temperature spin-glass property. If $Δ$ is small, the realizations remain glassy, but the SWAP annealing does not easily find a true ground state.

arXiv:2610.05046•Oct 4, 2026•0 citations

Low-temperature behavior of two-dimensional Gaussian Ising spin glasses

J. Houdayer, Alexander K. Hartmann

We perform Monte Carlo simulations of large two-dimensional Gaussian Ising spin glasses down to very low temperatures $\ensuremath{\beta}=1∕T=50$. Equilibration is ensured by using a cluster algorithm including Monte Carlo moves consisting of flipping fundamental excitations. We study the thermodynamic behavior using the Binder cumulant, the spin-glass susceptibility, the distribution of overlaps, the overlap with the ground state, and the specific heat. We confirm that ${T}_{c}=0$. All results are compatible with an algebraic divergence of the correlation length with an exponent $\ensuremath{\nu}$. We find $\ensuremath{-}1∕\ensuremath{\nu}=\ensuremath{-}0.295(40)$, which is compatible with the value for the domain-wall and droplet exponent $\ensuremath{\theta}\ensuremath{\approx}\ensuremath{-}0.29$ found previously in ground-state studies. Hence the thermodynamic behavior of this model seems to be governed by one single exponent.

arXiv:cond-mat/0402036•Physical Review B•Jul 1, 2004•133 citations

Exact low-energy landscape and relaxation phenomena in ISING spin glasses

Klotz, T., S. Kobe

All ground states and low-lying excitations of a +/- I Ising spin glass model on a cubic 4 x 4 x 4 lattice with periodical boundary conditions were calculated using a method of combinatorical optimization. The structure of states in the phase space is enlightened by a representation by means of clusters in the configuration space and their connectivity. The relaxation behaviour of the system can be described by random walks in the high-dimensional phase space. Rewriting this task as an eigenvalue problem the influence of `entropic barriers' in comparison with an unstructured system can be studied, leading to a better understanding of the anomalous slow dynamic behaviour.

arXiv:cond-mat/9406023•Jun 1, 1994•7 citations

Droplets in the two-dimensional +-J spin glass: evidence for (non-) universality

Alexander K. Hartmann

Using mappings to computer-science problems and by applying sophisticated algorithms, one can study numerically many problems much better compared to applying standard approaches like Monte Carlo simulations. Here, using calculations of ground states of suitable perturbed systems, droplets are obtained in two-dimensional +-J spin glasses, which are in the focus of a currently very lifely debate. Since a sophisticated matching algorithm is applied here, exact ground states of large systems up to L^2=256^2 spins can be generated. Furthermore, no equilibration or extrapolation to T=0 is necessary. Three different +-J models are studied here: a) with open boundary conditions, b) with fixed boundary conditions and c) a diluted system where a fraction p=0.125 of all bonds is zero. For large systems, the droplet energy shows for all three models a power-law behavior E_D L^θ'_D with θ'_D<0. This is different from previous studies of domain walls, where a convergence to a constant non-zero value (θ_dw=0) has been found for such models. After correcting for the non-compactness of the droplets, the results are likely to be compatible with θ_D= -0.29 for all three models. This is in accordance with the Gaussian system where θ_D=-0.287(4) (ν=3.5 via ν=-1/θ_D). Nevertheless, the disorder-averaged spin-spin correlation exponent ηis determined here via the probability to have a non-zero-energy droplet, and η~0.22$ is found for all three models, this being in contrast to the behavior of the model with Gaussian interactions, where exactly η=0.

arXiv:0704.2748•Apr 20, 2007•0 citations
As spin glass materials have extremely slow dynamics, devious numerical methods are needed to study low-temperature states. A simple and fast optimization version of the classical Kasteleyn treatment of the Ising model is described and applied to two-dimensional Ising spin glasses. The algorithm combines the Pfaffian and matching approaches to directly strip droplet excitations from an excited state. Extended ground states in Ising spin glasses on a torus, which are optimized over all boundary conditions, are used to compute precise values for ground state energy densities.
By using problem-dependent mappings to computer-science problems and by applying sophisticated algorithms, one can numerically study some important problems much better compared to applying standard approaches, such as Monte Carlo simulations. Here, by using calculations of ground states of suitable perturbed systems, droplets are obtained in two-dimensional $\ifmmode\pm\else\textpm\fi{}J$ spin glasses, which are in the focus of a currently very lively debate. By using a sophisticated matching algorithm, exact ground states of large systems up to L2=2562{L}^{2}={256}^{2}L2=2562 spins can be generated. Furthermore, no equilibration or extrapolation to T=0T=0T=0 is necessary. Three different $\ifmmode\pm\else\textpm\fi{}J$ models are studied here: (a) with free boundary conditions, (b) with fixed boundary conditions, and (c) a diluted system wherein a fraction p=0.125p=0.125p=0.125 of all bonds is zero. For large systems, the droplet energy shows for all three models a power-law behavior ${E}_{\text{dp}}\ensuremath{\sim}{L}^{{\ensuremath{\theta}}_{\text{dp}}^{\ensuremath{'}}}$ with ${\ensuremath{\theta}}_{\text{dp}}^{\ensuremath{'}}<0$. This is different from the previous studies of domain walls, wherein a convergence to a constant nonzero value $({\ensuremath{\theta}}_{\text{DW}}=0)$ was found. After correcting for the noncompactness of the droplets, the results are likely to be compatible with ${\ensuremath{\theta}}_{\text{dp}}\ensuremath{\approx}\ensuremath{-}0.29$ for all three models. This is in accordance with the Gaussian system wherein ${\ensuremath{\theta}}_{\text{dp}}=\ensuremath{-}0.287(4)$ ($\ensuremath{\nu}\ensuremath{\approx}3.5$ via $\ensuremath{\nu}=\ensuremath{-}1/{\ensuremath{\theta}}_{\text{dp}}$). Nevertheless, the disorder-averaged spin-spin correlation exponent $\ensuremath{\eta}$ is determined here via the probability to have a nonzero-energy droplet, and $\ensuremath{\eta}\ensuremath{\approx}0.22$ is found for all three models, in contrast to the model with the Gaussian interactions, where $\ensuremath{\eta}=0$ is exact.
We study large-scale, low-energy excitations in the Ising spin glass with Gaussian interactions in two dimensions at zero temperature, using an optimization algorithm to determine exact ground states. Periodic boundary conditions are applied. Our results for the fractal dimension of the surface, ds,{d}_{s},ds​, and stiffness exponent, ${\ensuremath{\theta}}^{\ensuremath{'}},$ for ``droplet'' excitations, are in reasonable agreement with estimates from ``domain wall'' calculations, and so support the predictions of the ``droplet theory.'' Restricting our analysis to small lattices, we do not find an effective value of ${\ensuremath{\theta}}^{\ensuremath{'}}$ close to $\ensuremath{-}0.47$ as has been recently proposed. The effects of averaging over droplets of different sizes are studied and are also found to be too small to give ${\ensuremath{\theta}}^{\ensuremath{'}}\ensuremath{\approx}\ensuremath{-}0.47$ for smaller sizes. Larger corrections to finite-size scaling would be needed in three and four dimensions in order for the numerical data used to support the ``TNT'' scenario to be compatible with the droplet theory prediction that the stiffness exponent is the same for droplets and domain walls.
We study the recently introduced SWAP ensemble for Ising spin-glasses, where the spins obtain varying lengths, with length scale Δ∈[0,2]Δ\in [0, 2]Δ∈[0,2]. The lengths can be exchanged in the spirit of the SWAP algorithm for glassy poly-disperse hard-sphere systems. Using an annealing schedule, if the annealing is slow enough, ground states of the corresponding Ising Hamiltonian, where the spin lengths are incorporated into the bonds, can be obtained with high probability. We prove this statement for two-dimensional systems with sizes of up to L2=10242L^2=1024^2L2=10242 spins by comparison with exact ground states obtained by using graph matching algorithms. In particular, we analyze the nature of the obtained realizations of the disorder by calculating exact zero-temperature domain-wall energies, from exact ground state calculations using periodic and anti-periodic boundary conditions. For medium or large values of ΔΔΔ, e.g. Δ=1Δ=1Δ=1, the realizations turn ferromagnetic if the annealing is slow enough, i.e., they lose their zero-temperature spin-glass property. If ΔΔΔ is small, the realizations remain glassy, but the SWAP annealing does not easily find a true ground state.
We perform Monte Carlo simulations of large two-dimensional Gaussian Ising spin glasses down to very low temperatures $\ensuremath{\beta}=1∕T=50$. Equilibration is ensured by using a cluster algorithm including Monte Carlo moves consisting of flipping fundamental excitations. We study the thermodynamic behavior using the Binder cumulant, the spin-glass susceptibility, the distribution of overlaps, the overlap with the ground state, and the specific heat. We confirm that Tc=0{T}_{c}=0Tc​=0. All results are compatible with an algebraic divergence of the correlation length with an exponent $\ensuremath{\nu}$. We find $\ensuremath{-}1∕\ensuremath{\nu}=\ensuremath{-}0.295(40)$, which is compatible with the value for the domain-wall and droplet exponent $\ensuremath{\theta}\ensuremath{\approx}\ensuremath{-}0.29$ found previously in ground-state studies. Hence the thermodynamic behavior of this model seems to be governed by one single exponent.
All ground states and low-lying excitations of a +/- I Ising spin glass model on a cubic 4 x 4 x 4 lattice with periodical boundary conditions were calculated using a method of combinatorical optimization. The structure of states in the phase space is enlightened by a representation by means of clusters in the configuration space and their connectivity. The relaxation behaviour of the system can be described by random walks in the high-dimensional phase space. Rewriting this task as an eigenvalue problem the influence of `entropic barriers' in comparison with an unstructured system can be studied, leading to a better understanding of the anomalous slow dynamic behaviour.
Using mappings to computer-science problems and by applying sophisticated algorithms, one can study numerically many problems much better compared to applying standard approaches like Monte Carlo simulations. Here, using calculations of ground states of suitable perturbed systems, droplets are obtained in two-dimensional +-J spin glasses, which are in the focus of a currently very lifely debate. Since a sophisticated matching algorithm is applied here, exact ground states of large systems up to L^2=256^2 spins can be generated. Furthermore, no equilibration or extrapolation to T=0 is necessary. Three different +-J models are studied here: a) with open boundary conditions, b) with fixed boundary conditions and c) a diluted system where a fraction p=0.125 of all bonds is zero. For large systems, the droplet energy shows for all three models a power-law behavior E_D L^θ'_D with θ'_D<0. This is different from previous studies of domain walls, where a convergence to a constant non-zero value (θ_dw=0) has been found for such models. After correcting for the non-compactness of the droplets, the results are likely to be compatible with θ_D= -0.29 for all three models. This is in accordance with the Gaussian system where θ_D=-0.287(4) (ν=3.5 via ν=-1/θ_D). Nevertheless, the disorder-averaged spin-spin correlation exponent ηis determined here via the probability to have a non-zero-energy droplet, and η~0.22$ is found for all three models, this being in contrast to the behavior of the model with Gaussian interactions, where exactly η=0.