Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimization of the Sherrington-Kirkpatrick Hamiltonian
61
0
0.0
(
0
)
Authors
Andrea Montanari
Ask ChatGPT about the research
No Arabic abstract
Let ${boldsymbol A}in{mathbb R}^{ntimes n}$ be a symmetric random matrix with independent and identically distributed Gaussian entries above the diagonal. We consider the problem of maximizing $langle{boldsymbol sigma},{boldsymbol A}{boldsymbol sigma}rangle$ over binary vectors ${boldsymbol sigma}in{+1,-1}^n$. 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 sigma}_*in{-1,+1}^n$ such that $langle{boldsymbol sigma}_*,{boldsymbol A}{boldsymbol sigma}_*rangle$ is at least $(1-varepsilon)$ of the optimum value, with probability converging to one as $ntoinfty$. The algorithms time complexity is $C(varepsilon), n^2$. 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.
rate research
Read More
Some recent results concerning the Sherrington-Kirkpatrick model are reported. For $T$ near the critical temperature $T_c$, the replica free energy of the Sherrington-Kirkpatrick model is taken as the starting point of an expansion in powers of $delta Q_{ab} = (Q_{ab} - Q_{ab}^{rm RS})$ about the Replica Symmetric solution $Q_{ab}^{rm RS}$. The expansion is kept up to 4-th order in $delta{bm Q}$ where a Parisi solution $Q_{ab} = Q(x)$ emerges, but only if one remains close enough to $T_c$. For $T$ near zero we show how to separate contributions from $xll Tll 1$ where the Hessian maintains the standard structure of Parisi Replica Symmetry Breaking with bands of eigenvalues bounded below by zero modes. For $Tll x leq 1$ the bands collapse and only two eigenvalues, a null one and a positive one, are found. In this region the solution stands in what can be called a {sl droplet-like} regime.
To test the stability of the Parisi solution near T=0, we study the spectrum of the Hessian of the Sherrington-Kirkpatrick model near T=0, whose eigenvalues are the masses of the bare propagators in the expansion around the mean-field solution. In the limit $Tll 1$ two regions can be identified. In the first region, for $x$ close to 0, where $x$ is the Parisi replica symmetry breaking scheme parameter, the spectrum of the Hessian is not trivial and maintains the structure of the full replica symmetry breaking state found at higher temperatures. In the second region $Tll x leq 1$ as $Tto 0$, the components of the Hessian become insensitive to changes of the overlaps and the bands typical of the full replica symmetry breaking state collapse. In this region only two eigenvalues are found: a null one and a positive one, ensuring stability for $Tll 1$. In the limit $Tto 0$ the width of the first region shrinks to zero and only the positive and null eigenvalues survive. As byproduct we enlighten the close analogy between the static Parisi replica symmetry breaking scheme and the multiple time-scales approach of dynamics, and compute the static susceptibility showing that it equals the static limit of the dynamic susceptibility computed via the modified fluctuation dissipation theorem.
An expansion for the free energy functional of the Sherrington-Kirkpatrick (SK) model, around the Replica Symmetric SK solution $Q^{({rm RS})}_{ab} = delta_{ab} + q(1-delta_{ab})$ is investigated. In particular, when the expansion is truncated to fourth order in. $Q_{ab} - Q^{({rm RS})}_{ab}$. The Full Replica Symmetry Broken (FRSB) solution is explicitly found but it turns out to exist only in the range of temperature $0.549...leq Tleq T_c=1$, not including T=0. On the other hand an expansion around the paramagnetic solution $Q^{({rm PM})}_{ab} = delta_{ab}$ up to fourth order yields a FRSB solution that exists in a limited temperature range $0.915...leq T leq T_c=1$.
We study in detail the quantum Sherrington-Kirkpatrick (SK) model, i.e. the infinite-range Ising spin glass in a transverse field, by solving numerically the effective one-dimensional model that the quantum SK model can be mapped to in the thermodynamic limit. We find that the replica symmetric (RS) solution is unstable down to zero temperature, in contrast to some previous claims, and so there is not only a line of transitions in the (longitudinal) field-temperature plane (the de Almeida-Thouless, AT, line) where replica symmetry is broken, but also a quantum de Almeida-Thouless (QuAT) line in the transverse field-longitudinal field plane at $T = 0$. If the QuAT line also occurs in models with short-range interactions its presence might affect the performance of quantum annealers when solving spin glass-type problems with a bias (i.e. magnetic field).
We investigate generalized Sherrington--Kirkpatrick glassy systems without reflection symmetry. In the neighbourhood of the transition temperature we in general uncover the structure of the glass state building the full-replica-symmetry breaking solution. Physical example of explicitly constructed solution is given.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
