Algorithmic Pirogov-Sinai theory

Abstract

We develop an efficient algorithmic approach for approximate counting and sampling in the low-temperature regime of a broad class of statistical physics models on finite subsets of the lattice ${\mathbb{Z}}^d$ and on the torus $(\mathbb{Z}/n\mathbb{Z}{)}^d$. Our approach is based on combining contour representations from Pirogov-Sinai theory with Barvinok's approach to approximate counting using truncated Taylor series. Some consequences of our main results include an FPTAS for approximating the partition function of the hard-core model at sufficiently high fugacity on subsets of ${\mathbb{Z}}^d$ with appropriate boundary conditions and an efficient sampling algorithm for the ferromagnetic Potts model on the discrete torus $(\mathbb{Z}/n\mathbb{Z}{)}^d$ at sufficiently low temperature.

We fixed a typo in the series expansion for log Z(z) on page 20

References in corpus (6)

• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Cluster expansion for abstract polymer models. New bounds from an old approach
• The Ising Partition Function: Zeros and Deterministic Approximation
• FPTAS for #BIS with Degree Bounds on One Side
• Weighted counting of solutions to sparse systems of equations
• A condition for long-range order in discrete spin systems with application to the antiferromagnetic Potts model

Cited by in corpus (8)

• Classical simulation of short-time quantum dynamics
• Quantum many-body systems in thermal equilibrium
• Efficient Algorithms for Approximating Quantum Partition Functions
• Correlation decay and partition function zeros: Algorithms and phase transitions
• Sampling from the low temperature Potts model through a Markov chain on flows
• Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature
• Absence of zeros implies strong spatial mixing
• Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence