Optimization of the Sherrington-Kirkpatrick Hamiltonian

Let boldsymbol A∈mathbb Rn× n be a symmetric random matrix with independent and identically distributed Gaussian entries above the diagonal. We consider the problem of maximizing langleboldsymbol σ,boldsymbol Aboldsymbol σrangle over binary vectors boldsymbol σ∈+1,-1n. In the language of statistical physics, this amounts to finding the ground state of the Sherrington-Kirkpatrick model of spin glasses. The asymptotic value of this optimization problem was characterized by Parisi via a celebrated variational principle, subsequently proved by Talagrand. We give an algorithm that, for any varepsilon>0, outputs boldsymbol σ_*∈-1,+1n such that langleboldsymbol σ_*,boldsymbol Aboldsymbol σ_*rangle is at least (1-varepsilon) of the optimum value, with probability converging to one as n→∞. The algorithm's time complexity is C(varepsilon), n2. It is a message-passing algorithm, but the specific structure of its update rules is new. As a side result, we prove that, at (low) non-zero temperature, the algorithm constructs approximate solutions of the Thouless-Anderson-Palmer equations.