Papers for

statistical physics simulators

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Efficient sampling algorithm for spin glass model below critical threshold

Sampling from the Sherrington-Kirkpatrick Model up to Criticality

Abstract: We prove that the simulated annealing algorithm efficiently samples from the Sherrington-Kirkpatrick model at inverse temperature $β< 1$ to an arbitrary inverse polynomial accuracy in total variation.

Tue 13 OctData Structures and Algorithms
The gist
There is a complex physical model called the Sherrington-Kirkpatrick model that helps scientists understand certain types of magnets and disorder. Sampling from this model means generating typical examples that follow the model’s random behavior. The authors show that a commonly used method, simulated annealing, can efficiently do this sampling when the temperature is above a certain level (below the critical inverse temperature value of 1). This means they can accurately generate examples from the model quickly under these conditions.
Open → 2610.17717v1

Improved mixing time bounds for sampling spin models on graphs

Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $β\leq \frac{1}{2}+\varepsilon$

Abstract: We introduce a new family of trickledown theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state spin systems. In this technique instead of upper-bounding the influence matrix of a link of co-dimension 2 by $λI$ (where $λ$ is the second eigenvalue of the link), we upper-bound the influence matrix after a carefully chosen rank-1 shift. The rank-1 shift allows for a significantly smaller upper-bound but it comes at the cost of bounding the average loss due to rank-1 perturbations. As an application we use this method to show that the natural Glauber dynamics mixes in polynomial time to generate samples from the Sherrington-Kirkpatrick model for $β\leq \tfrac{1}{2}+\varepsilon$, for an absolute constant $\varepsilon>0$. At the heart of the proof we manage to bound the loss due to rank-1 perturbations by averaging over all links of co-dimension 2.

Fri 11 SeptData Structures and Algorithms
The gist
Sampling complex systems made of many interacting parts is challenging and important for physics and computer science. The authors developed a new mathematical technique that improves how quickly a well-known sampling process, Glauber dynamics, can reliably generate typical configurations of the Sherrington-Kirkpatrick spin model. Their method involves a subtle adjustment called a rank-1 perturbation, allowing them to prove faster convergence up to a certain temperature threshold. This ensures that, for moderate interaction strengths, sampling can be done efficiently using this approach.
Open → 2609.13138v1