Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses

Abstract

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 the applicability of EO to systems with highly connected variables. Approximate ground states of sufficient accuracy and with statistical significance are obtained for systems with more than N=1000 variables using $\pm J$ bonds. The data reproduces the well-known Parisi solution for the average ground state energy of the model to about 0.01%, providing a high degree of confidence in the heuristic. The results support to less than 1% accuracy rational values of $\omega =2/3$ for the finite-size correction exponent, and of $\rho =3/4$ for the fluctuation exponent of the ground state energies, neither one of which has been obtained analytically yet. The probability density function for ground state energies is highly skewed and identical within numerical error to the one found for Gaussian bonds. But comparison with infinite-range models of finite connectivity shows that the skewness is connectivity-dependent.

Substantially revised, several new results, 5 pages, 6 eps figures included, (see http://www.physics.emory.edu/faculty/boettcher/ for related information)

References in corpus (11)

• Lower Critical Dimension of Ising Spin Glasses
• Analysis of the infinity-replica symmetry breaking solution of the Sherrington-Kirkpatrick model
• Energy exponents and corrections to scaling in Ising spin glasses
• Numerical Results for Ground States of Mean-Field Spin Glasses at low Connectivities
• Interface energies in Ising spin glasses
• Improved extremal optimization for the Ising spin glass
• Low-Temperature Excitations of Dilute Lattice Spin Glasses
• Large deviations in spin-glass ground-state energies
• Numerical Results for Ground States of Spin Glasses on Bethe Lattices
• Jamming Model for the Extremal Optimization Heuristic
• Exploring Valleys of Aging Systems: The Spin Glass Case

Cited by in corpus (36)

• Stiffness of the Edwards-Anderson Model in all Dimensions
• Large Deviations in the Free-Energy of Mean-Field Spin-Glasses
• Finite size corrections in the Sherrington-Kirkpatrick model
• Quantum speedup of branch-and-bound algorithms
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Phase diagram and large deviations in the free-energy of mean-field spin-glasses
• Free energy fluctuations and chaos in the Sherrington-Kirkpatrick model
• Probing the tails of the ground state energy distribution for the directed polymer in a random medium of dimension $d=1,2,3$ via a Monte-Carlo procedure in the disorder
• Dynamics and Correlations among Soft Excitations in Marginally Stable Glasses
• Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
• Large Deviations of the Free-Energy in Diluted Mean-Field Spin-Glass
• One-dimensional infinite component vector spin glass with long-range interactions
• Universality class of replica symmetry breaking, scaling behavior, and the low-temperature fixed-point order function of the Sherrington-Kirkpatrick model
• Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
• Interface free-energy exponent in the one-dimensional Ising spin glass with long-range interactions in both the droplet and broken replica symmetry regions
• An exact relation between free energy fluctuations and bond chaos in the Sherrington-Kirkpatrick model
• Hysteretic Optimization For Spin Glasses
• Finding Ground States of Sherrington-Kirkpatrick Spin Glasses with Hierarchical BOA and Genetic Algorithms
• Numerical estimate of finite size corrections to the free energy of the SK model using Guerra--Toninelli interpolation
• Exact Enumeration of Ground States in the Sherrington-Kirkpatrick Spin Glass
• Ground State Properties of the Diluted Sherrington-Kirkpatrick Spin Glass
• Solving combinatorial optimization problems through stochastic Landau-Lifshitz-Gilbert dynamical systems
• Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
• Deep reinforced learning heuristic tested on spin-glass ground states: The larger picture
• Ground States of the Sherrington-Kirkpatrick Spin Glass with Levy Bonds
• Sampling the ground-state magnetization of d-dimensional p-body Ising models
• Classical Annealing of Sherrington-Kirkpatrick Spin Glass Using Suzuki-Kubo Mean-field Ising Dynamics
• Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
• Analysis of Evolutionary Algorithms on the One-Dimensional Spin Glass with Power-Law Interactions
• Physics of the Edwards-Anderson Spin Glass in Dimensions $d=3,\dots ,8$ from Heuristic Ground State Optimization
• Reply to Comment "Density of states and critical behavior of the three-dimensional Coulomb Glass"
• Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
• Quantum Annealing in SK Model Employing Suzuki-Kubo-deGennes Quantum Ising Mean Field Dynamics
• Qubit-efficient quantum combinatorial optimization solver
• Quantum-inspired search method for low-energy states of classical Ising Hamiltonians