Exact Ground States of Large Two-Dimensional Planar Ising Spin Glasses

Abstract

Studying spin-glass physics through analyzing their ground-state properties has a long history. Although there exist polynomial-time algorithms for the two-dimensional planar case, where the problem of finding ground states is transformed to a minimum-weight perfect matching problem, the reachable system sizes have been limited both by the needed CPU time and by memory requirements. In this work, we present an algorithm for the calculation of exact ground states for two-dimensional Ising spin glasses with free boundary conditions in at least one direction. The algorithmic foundations of the method date back to the work of Kasteleyn from the 1960s for computing the complete partition function of the Ising model. Using Kasteleyn cities, we calculate exact ground states for huge two-dimensional planar Ising spin-glass lattices (up to 3000x3000 spins) within reasonable time. According to our knowledge, these are the largest sizes currently available. Kasteleyn cities were recently also used by Thomas and Middleton in the context of extended ground states on the torus. Moreover, they show that the method can also be used for computing ground states of planar graphs. Furthermore, we point out that the correctness of heuristically computed ground states can easily be verified. Finally, we evaluate the solution quality of heuristic variants of the Bieche et al. approach.

11 pages, 5 figures; shortened introduction, extended results; to appear in Physical Review E 78

References in corpus (6)

• Lower Critical Dimension of Ising Spin Glasses
• The critical exponents of the two-dimensional Ising spin glass revisited: Exact Ground State Calculations and Monte Carlo Simulations
• Finite Size Scaling Analysis of Exact Ground States for +/-J Spin Glass Models in Two Dimensions
• Matching Kasteleyn Cities for Spin Glass Ground States
• Genetic embedded matching approach to ground states in continuous-spin systems
• Ground-State and Domain-Wall Energies in the Spin-Glass Region of the 2D $\pm J$ Random-Bond Ising Model

Cited by in corpus (14)

• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Efficient Exact Inference in Planar Ising Models
• Domain-wall excitations in the two-dimensional Ising spin glass
• Effects of setting the temperatures in the parallel tempering Monte Carlo algorithm
• A dedicated algorithm for calculating ground states for the triangular random bond Ising model
• Estimating the Density of States of Frustrated Spin Systems
• Scaling behavior of domain walls at the T=0 ferromagnet to spin-glass transition
• Information theoretic approach to ground-state phase transitions for two and three-dimensional frustrated spin systems
• The upper critical dimension of the negative-weight percolation problem
• Optimizing glassy p-spin models
• Feeding the multitude: A polynomial-time algorithm to improve sampling
• Mean-field behavior of the negative-weight percolation model on random regular graphs
• Ordering Behavior of the Two-Dimensional Ising Spin Glass with Long-Range Correlated Disorder
• Force network analysis of jammed solids