Average case complexity of low-dimensional Ising spin glasses

Finding ground states of Ising spin glasses is a notoriously hard problem for which there is to date no known efficient general case algorithm [F.Barahona, Journal of Physics A, 15, 3241, 1982]. We present strong numerical evidence that the complexity of the average case low-dimensional spin glass is polynomial in the number of vertices. To this end we present an efficient exact solver based on local constraint satisfaction for finding ground states of this system with an average case complexity polynomial in system size, exponential in the degree of the graph and polynomial in $1/h$, where $h$ is the on-site field. Numerical studies are done in two and three dimensions, and using scaling arguments we conjecture that polynomial complexity holds. We present results for bi-modal and Gaussian distributed couplings and on-site fields and discuss boundary cases on which the complexity of the algorithm is exponential.