Fast counting and sampling for ferromagnetic two-spin systems
2026-07-06 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors introduce two new ways to represent ferromagnetic two-spin systems using different mathematical models. These new representations help them create an efficient method to sample and estimate the partition function, which is a key quantity in understanding these systems. Their method works faster than previous ones, especially for graphs with limited connections, and also improves speed for more complex graphs. This advances the computational tools available for studying these physical models.
ferromagnetic two-spin systemspartition functionsampling algorithmweighted subgraph modelrandom cluster modelapproximation algorithmbounded degree graphspolynomial timerandomised algorithm
Authors
Weiming Feng, Heng Guo, Yichun Yang
Abstract
We introduce two new models equivalent to ferromagnetic two-spin systems: a weighted subgraph model and a random cluster type model. Using these new connections, we obtain an efficient sampling algorithm and a new randomised algorithm that efficiently approximates the partition function of ferromagnetic two-spin systems in certain parameter regimes. No efficient sampling algorithms are known before in this regime, and our new estimation algorithm runs in near-quadratic time for bounded degree graphs and in polynomial time for general graphs, improving upon the previous algorithm of Guo, Liu, and Lu (2020).