Algorithms approximate complex spin glass models with weak fields efficiently
Approximate Counting for Mixed $p$-Spin Glasses in Weak External Fields via Cluster Expansion
Data Structures and Algorithms
Summary
Calculating important quantities in certain complex physics models, like spin glasses, is usually very hard. This paper presents algorithms that can efficiently approximate these calculations when external effects are weak and the system size is large. The authors build on past mathematical methods to simplify the problem into smaller parts and use clever random sampling to manage complexity. Their approach ensures good accuracy with high probability and runs in reasonable time as the system grows.
What this means in practice
- •For statistical physicists: Use the new algorithms to approximate partition functions of disordered spin systems under weak external fields efficiently for better theoretical analysis.
- •For machine learning engineers: Incorporate the approximation techniques when modeling complex energy landscapes in large neural networks related to spin glass theory.
Authors
Qiang Wu
Abstract
We give algorithms for approximating the partition function $Z_N$ of the Sherrington--Kirkpatrick (SK) model and finite mixed Ising $p$-spin models with $p\ge 3$. The algorithms apply at a fixed margin below the second-moment threshold $β_{\mathrm f}$ with homogeneous weak external fields $|h|\leqρ_0N^{-1/4}$, for fixed $ρ_0>0$. For any accuracy $\varepsilon\in(0,1)$ and failure parameter $δ\in(0,1)$, they approximate $\log Z_N$ to additive error $\varepsilon$. The number of exact operations is polynomial jointly in $N$, $\varepsilon^{-1}$, and $δ^{-1}$. The disorder variables have i.i.d symmetric distribution with unit variance. The failure probability is at most $δ$ plus an explicit disorder tail bound. This tail bound tends to zero under a finite fourth moment condition. Our approach builds on the cluster expansions of Aizenman--Lebowitz--Ruelle~\cite{ALR87} and Dey--Wu~\cites{DW23,DW26}. For higher-order mixtures, we retain hypergraphs using few vertices and evaluate their total weight deterministically through local spin averages and inclusion--exclusion. For SK, we impose cutoffs on the number of vertices of degree at least three and on the total number of edges. We estimate the retained sum using randomized color coding~\cite{AYZ95}. A lower tail control based on reverse hypercontractivity~\cite{MOS13} converts the mean-square approximation of the normalized partition function into logarithmic accuracy.