Extremal optimization for Sherrington-Kirkpatrick spin glasses

摘要: Extremal Optimization (EO), a new local search heuristic, is used to approximate ground states of the mean-field spin glass model introduced by Sherrington and Kirkpatrick. The implementation extends applicability EO systems with highly connected variables. Approximate sufficient accuracy and statistical significance are obtained for more than N=1000 variables using ±J bonds. data reproduces well-known Parisi solution average state energy model about 0.01%, providing high degree of confidence in heuristic. results support less 1% rational values ω=2/3 finite-size correction exponent, ρ=3/4 fluctuation exponent energies, neither one which has been analytically yet. probability density function energies skewed identical within numerical error found Gaussian But comparison infinite-range models finite connectivity shows that skewness connectivity-dependent.