Extremal Optimization for p-Spin Models

It was shown recently that finding ground states in the 3-spin model on a 2d dimensional triangular lattice poses an NP-hard problem [1]. We use the extremal optimization (EO) heuristic [2] to explore ground state energies and finite-size scaling corrections [3]. EO predicts the thermodynamic ground state energy with high accuracy, based on the observation that finite size corrections appear to decay purely with system size. Just as found in 3-spin models on $r$-regular graphs, there are no noticeable anomalous corrections to these energies. Interestingly, the results are sufficiently accurate to detect alternating patters in the energies when the lattice size $L$ is divisible by 6. Although ground states seem very prolific and might seem easy to obtain with simple greedy algorithms, our tests show significant improvement in the data with EO. \\[4pt] [1] PRE 83 (2011) 046709,\hfil\break [2] PRL 86 (2001) 5211,\hfil\break [3] S. Boettcher and S. Falkner (in preparation).