Materials science

Binary number

Diagonal matrix

Eigenvalues and eigenvectors

Composite material

Geometry

Combinatorics

Physics

Dimension (graph theory)

Mathematics

Mathematical optimization

Quadratic equation

Diagonal

Quantum mechanics

Gaussian

Discrete mathematics

Hamiltonian (control theory)

Random matrix

Matrix (chemical analysis)

Applied mathematics

Arithmetic

Let A be a symmetric random matrix with independent and identically distributed Gaussian entries above the diagonal. We consider the problem of maximizing the quadratic form associated to A over binary vectors. 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 ε > 0, outputs a feasible solution whose value is at least (1 - ε) of the optimum, with probability converging to one as the dimension n of the matrix diverges. The algorithm's time complexity is of order n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> . 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.

Optimization of the Sherrington-Kirkpatrick Hamiltonian