The Ising Partition Function: Zeros and Deterministic Approximation

Abstract

We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters $\beta$ (the interaction) and $\lambda$ (the external field), except for the case $|\lambda |=1$ (the "zero-field" case). A randomized algorithm (FPRAS) for all graphs, and all $\beta ,\lambda$, has long been known. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the "decay of correlations" property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions. Our approach extends to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters. In order to achieve this extension, we establish a tight version of the Lee-Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher.

clarified presentation of combinatorial arguments, added new results on optimality of univariate Lee-Yang theorems

References in corpus (2)

• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Inapproximability of the Tutte polynomial

Cited by in corpus (11)

• Algorithmic Pirogov-Sinai theory
• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• Fisher zeros and correlation decay in the Ising model
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Efficient Algorithms for Approximating Quantum Partition Functions
• Weighted counting of solutions to sparse systems of equations
• Correlation decay and partition function zeros: Algorithms and phase transitions
• Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
• More on zeros and approximation of the Ising partition function
• Zeros and approximations of Holant polynomials on the complex plane
• Computing the probability of intersection