updated 2023-12-04
“Spin glass” refers to a model exhibiting a weirdo “glassy” state of matter. There is no universal mathematical definition of a spin glass. Typically, the phrase refers to the physical phenomena of ground states of magnetic alloys that are “frozen” in their configuration at low temperatures.
This is typically modeled by a probability distribution on the overall state of the particles \(\sigma \in\{-1,+1\}^N\). Each of the particles \(\sigma_i\) are also called sites.
The Hamiltonian is
\[H(\sigma) = \sum_{k=1}^\infty c_k \langle J^{(k)}, \sigma^{\otimes k} \rangle\]where we have fixed parameters \(c_k \in \mathbb{R}\), and a random disorder matrix or interaction matrix \(J^{(k)}\). This is a random symmetric Gaussian tensor of order \(k\). (If \(J^{(k)}\) is a random matrix of Booleans instead of Gaussians, we say this is “boolean disorder”. The behavior is qualitatively the same as for “Gaussian disorder”)
Physical states can be thought of as samples from the Gibbs distribution, which weighs the likelihood you are likely to see different spin configurations based on relative energies and a temperature parameter. Given an inverse temperature \(\beta\), the probability of a given configuration \(\sigma\) is
\[\Pr[\sigma] \propto e^{\beta H(\sigma)}.\]Historically: People studied the free energy of magnetic alloys (an Ising model, where each particle has “positive” or “negative” spin i.e. a Boolean) on a lattice (because physics, \(\mathbb{Z}^2\) or \(\mathbb{Z}^3\)).
The lattice is too hard, so we relax to a “mean-field model”, where all particles are connected to all other particles. Here, we can finally get a mathematical handle on the behavior of the model.
We usually consider a spin glass with the following characteristics:
mixed-spin or purespherical or Ising domainA pure spin glass (of level \(p\)) only has \(p\)-body interactions. By contrast, a mixed-spin spin glass could have interactions of any number of terms.
We can see this with the mixture polynomial \(\xi(s)\):
\[\xi(s) = \sum_{k=1}^\infty c^2_k s^k\]With a pure spin spin glass, \(c_k = 0\) except when \(k = p\).
An Ising spin glass has the spin configurations \(\sigma \in \{+1,-1\}^N\). Sometimes, this is too challenging, so we consider spherical spin glasses, where the domain of spin configurations \(\{-1,+1\}^N\) is relaxed to the sphere of radius \(\sqrt{N}\) in \(\mathbb{R}^N\).
Think of the sphere as a relaxation of the hypercube. The ground state energy for the Ising model is an upper bound to the ground state energy for the spherical model. However, because the sphere is a connected set (whereas the hypercube is discrete), properties of spherical spin glasses may be easier to determine using (e.g.) calculus.
Sherrington and Kirkpatrick [SK75] heuristically computed the free energy of a simple nontrivial spin glass using the “replica method”. However, their “RS ansatz” is not physical at low temperature.
To fix this, Parisi [Par80] introduced the “RSB ansatz” (aka Parisi ansatz). We can use this to describe the free energy at any temperature using a variational principle.
How does this work? We call \(P(\gamma)\) the Parisi functional, where \(\gamma: [0,1] \to \mathbb{R}\) is any nondecreasing function (\(\gamma\) is called the “functional order parameter”).
\[GSED = min_{\gamma} P(\gamma)\]If \(\gamma\) is constant, this is replica symmetric* (RS). If there is a point where \(\gamma\) is increasing, we call it **replica symmetry breaking (RSB).
If \(\gamma\) takes exactly \(k\) nonzero values, then we call it \(k\)-RSB. (For example, 1-RSB, 2-RSB, …)
If it is not RS, and not \(k\)-RSB for some constant \(k\), then \(\gamma\) takes on an infinite number of nonzero values. We call this \(\infty\)-RSB. But this could mean lots of things:
We can view the \(\gamma\) like an unnormalized cumulative distribution function; i.e. \(\gamma(0_-) = 0\). Every PDF will have support at least at one point (perhaps at zero). Every additional point is considered “replica symmetry breaking”.
Mean-field models are dense, where all things are connected to all things. Sparse models have \(o(N)\) average degree.
The physicists’ dream is to study Ising models on sparse, “physical” graphs (like the lattice \(\mathbb{Z}^3\)). Unfortunately, we only have good results for random graphs, not lattices. A sparse, random interaction matrix is called a diluted mean-field model.
For example:
When the models are random, we can prove properties about sparse models using a corresponding dense versions. This uses important properties of sparse random graphs, which are expanders, and almost all small neighborhoods are trees. On the other hand, these are “not physical” (\(\mathbb{Z}^3\) does not have these properties).
Random CSPs are sparse models. However, some of the properties of dense spin glasses do actually appear if you look closely and in the right places.
When studying CSPs, it’s mathematically useful to introduce \(\beta\) (a smoothening parameter). CSPs don’t intrinsically have a notion of temperature.
When CSPs are in the “unsatisfiable regime”, (e.g. the clause density is high enough), we can relate the optimal value to the ground state energy density of a dense spin glass.
This is known in several settings:
Is this relationship true in general? This is a natural question to ask, and for now, is open. However, major progress was made on this by a paper of Panchenko and Talagrand:
What is an OGP? See [Gamarnik21] for a reference, or this talk for a decent exposition.
If there is an OGP, then algorithms that do not see the whole graph (i.e., local algorithms with at most \(\log N\) depth) will not find optimal solutions. In fact, all algorithms that are insensitive to small changes in the input will be obstructed by an OGP. See [CLSS21].
For the spin glass problems, an OGP means there is some interval \([a,b]\) where \(0 < a < b < 1\) where \(\gamma\) is constant, yet \(\gamma\) changes value both in \([0,a]\) and also in \([b,1]\). We typically think about OGP at low temperature.
A key takeaway: If the Parisi minimizer is RS or fRSB, then there is no overlap gap property. Otherwise, there is an OGP, even if it is \(\infty\)-RSB!
We also know that some CSPs exhibit an OGP, because the associated dense spin glass model does. This connection is usually done via the Guerra-Tonnineli interpolation.
From [CLSS21], it turns out that OGPs obstruct local classical and local quantum algorithms from well-approximating random MAX \(k\)-XOR instances.
This is the canonical spin glass people study; i.e. the pure model at \(p=2\).
At high temperature (when \(\beta < \beta_c\)), we know the SK Model is \(RS\) (or 0-RSB) [ALR87], [Bol18]. There exists an efficient algorithm to output solutions to the free energy. this is done by solving the TAP equations iteratively by Bolthausen [Bol12].
At low temperature (when \(\beta > \beta_c\)), the SK Model is \(\infty\)-RSB [ACZ20]. There exists an efficient algorithm to output solutions to the free energy. Assuming fRSB, this is done by an AMP algorithm that discretizes the dynamics of the Auffinger-Chen Principle rewrite of the Parisi-Variational Principle. This algorithm is due to Montanari [Mon19].
Some other cool papers:
Some results for SK generalize to mixed-spin models, especially if they are even (i.e. \(c_k = 0\) when \(k\) is odd).
We also know several things about the Parisi functional for any Ising spin glass:
A rewrite of the Parisi-Variational Principle in terms of a functional min-max principle is provided by the Auffinger-Chen Principle [AC17]. The AC Principle gives a rewrite of the PVP in terms of an auxiliary stochastic process (a drifted Brownian motion) that does a random walk in the cavity field component of the initial free-entropy term (\(\Phi(1, x)\)).
Define \(P\) as the Parisi functional. Then
By [AMS20] and [Sel21], we know the following things:
On even mixed-spin glasses, we know a few more things:
Consider the following statements:
What is the \(k\) in \(k\)RSB for a given CSP?
It’s conjectured that \(p\)-XOR, \(p > 2\), is \(k\)RSB for some value \(k>0\), but not fRSB. What is the number \(k\) as a function of \(p\)?
[Juspreet] \(k \sim p\)? [Chris] \(k = C^p\)? [Kunal] \(k = \infty\)?
Other interesting papers:
theres also a new book out: “spin glass theory and far beyond” with most chapters on arXiv.
For all mixed-spin models on the hypercube, we know that at high enough temperature, it is RS (need a citation), and at zero temperature, it is \(\infty-RSB\) [ACZ17]. But we suspect more:
On the SK model, we know of the dAT line (?) that suggests that at there is a single transition from RS to something else at inverse temperature \(\beta = 1\). We know the something else is not RS, and we suspect it is fRSB.
For other pure \(p\)-spin models where \(p > 2\), we know of a second transition [Gardner85]. At the lowest temperature, we expect there to be gaps in the support of increasing points in \(\gamma\) (i.e. overlap gaps); this is proven for even \(p\). I’m not sure what happens at the intermediate temperature.
Primarily written with Juspreet Singh Sandhu, Chris Jones, and Jonathan Shi.
More to add? Email me at kmarw@uchicago.edu.