Numerical Results for Ground States of Spin Glasses on Bethe Lattices
arXiv:cond-mat/0208196 · doi:10.1140/epjb/e2003-00005-y
Abstract
The average ground state energy and entropy for +/- J spin glasses on Bethe lattices of connectivities k+1=3...,26 at T=0 are approximated numerically. To obtain sufficient accuracy for large system sizes (up to n=2048), the Extremal Optimization heuristic is employed which provides high-quality results not only for the ground state energies per spin e_{k+1} but also for their entropies s_{k+1}. The results show considerable quantitative differences between lattices of even and odd connectivities. The results for the ground state energies compare very well with recent one-step replica symmetry breaking calculations. These energies can be scaled for all even connectivities k+1 to within a fraction of a percent onto a simple functional form, e_{k+1} = E_{SK} sqrt(k+1) - {2E_{SK}+sqrt(2)} / sqrt(k+1), where E_{SK} = -0.7633 is the ground state energy for the broken replica symmetry in the Sherrington-Kirkpatrick model. But this form is in conflict with perturbative calculations at large k+1, which do not distinguish between even and odd connectivities. We find non-zero entropies s_{k+1} at small connectivities. While s_{k+1} seems to vanish asymptotically with 1/(k+1) for even connectivities, it is indistinguishable from zero already for odd k+1 >= 9.
11 pages, RevTex4, 28 ps-figures included, related papers available at http://www.physics.emory.edu/faculty/boettcher/
References in corpus (3)
Cited by in corpus (27)
- Energy exponents and corrections to scaling in Ising spin glasses
- Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses
- Finite size corrections in the Sherrington-Kirkpatrick model
- Numerical Results for Ground States of Mean-Field Spin Glasses at low Connectivities
- Universality-class dependence of energy distributions in spin glasses
- Comparing extremal and thermal Explorations of Energy Landscapes
- Conjecture on the maximum cut and bisection width in random regular graphs
- Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
- Replica Cluster Variational Method
- Ground state of the Bethe-lattice spin glass and running time of an exact optimization algorithm
- Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut
- Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
- Large Deviations of the Free-Energy in Diluted Mean-Field Spin-Glass
- Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
- Numerical estimate of finite size corrections to the free energy of the SK model using Guerra--Toninelli interpolation
- The metastable minima of the Heisenberg spin glass in a random magnetic field
- Ground State Properties of the Diluted Sherrington-Kirkpatrick Spin Glass
- Extremal optimization for sensor report pre-processing
- Thermodynamic Construction of an One-Step Replica-Symmetry-Breaking Solution in Finite Connectivity Spin Glasses
- On metastable configurations of small-world networks
- Reduction of Dilute Ising Spin Glasses
- The network source location problem: ground state energy, entropy and effects of freezing
- Numerical study of ground state energy fluctuations in spin glasses
- Physics of the Edwards-Anderson Spin Glass in Dimensions from Heuristic Ground State Optimization
- Study of longitudinal fluctuations of the Sherrington-Kirkpatrick model
- Computation of the Zero Temperature RSB parameter in Bethe Lattice Spin Glasses
- Free energy expansion of the spin glass with finite connectivity for RSB