Ground States of the Mean-Field Spin Glass with 3-Spin Couplings

Abstract

We use heuristic optimization methods in extensive computations to determine with low systematic error ground state configurations of the mean-field $p$-spin glass model with $p=3$. Here, all possible triplets in a system of $N$ Ising spins are connected with a bond. This model has been of recent interest, since it exhibits the ``overlap gap condition'', which should make it prohibitive to find ground states asymptotically with local search methods when compared, for instance, with the $p=2$ case better-known as the Sherrington-Kirkpatrick model (SK). Indeed, it proves more costly to find good approximations for $p=3$ than for SK, even for our heuristic. Compared to SK, the ground-state behavior for $p=3$ is quite distinct also in other ways. For SK, finite-size corrections for large system sizes $N\to \infty$ of both, the ensemble average over ground state energy densities and the width of their distribution, vary anomalously with non-integer exponents. In the $p=3$ case here, the energy density and its distribution appear to scale with $\ln N/N$ and $1/N$ corrections, respectively. The distribution itself is consistent with a Gumbel form. Even more stark is the contrast for the bond-diluted case, where SK has shown previously a notable variation of the anomalous corrections exponent with the bond density, while for $p=3$ no such variation is found here. Hence, for the 3-spin model, all measured corrections scale the same as for the random energy model (REM), corresponding to $p=\infty$. This would suggest that all $p$-spin models with $p\ge 3$ exhibit the same ground-state corrections as in REM.

RevTex 4.2, 5 pages, 5 pdf-figures incl., related information can be found at https://faculty.college.emory.edu/sites/boettcher/

References in corpus (10)

• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Reexamining classical and quantum models for the D-Wave One processor
• Finite size corrections in the Sherrington-Kirkpatrick model
• Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection
• Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut
• HUBO and QUBO models for Prime factorization
• Local field distributions in spin glasses
• Exact Enumeration of Ground States in the Sherrington-Kirkpatrick Spin Glass
• Deep reinforced learning heuristic tested on spin-glass ground states: The larger picture
• Full quantum theory of nonequilibrium phonon condensation and phase transition