Paper Info
Title
Polynomial-time approximation algorithms for the Ising model
Abstract
The paper presents a randomised algorithm which evaluates the partition function of an arbitrary ferromagnetic Ising system to any specified degree of accuracy. The running time of the algorithm increases only polynomially with the size of the system (i.e., the number of sites) and a parameter which controls the accuracy of the result. Further approximation algorithms are presented for the mean energy and the mean magnetic moment of ferromagnetic Ising systems.The algorithms are based on Monte Carlo simulation of a suitably defined ergodic Markov chain. The states of the chain are not, as is customary, Ising spin configurations, but spanning subgraphs of the interaction graph of the system. It is shown that the expectations of simple operators on these configurations give numerical information about the partition function and related quantities.The performance guarantees for the algorithms are rigorously derived and rest on the fact that the Markov chain in question is rapidly mixing, i.e., converges to its equilibrium distribution in a polynomial number of steps. This is apparently the first time that rapid mixing has been demonstrated at all temperatures for a Markov chain related to the Ising model.
Year
DOI
Venue
1993
10.1137/0222066
SIAM J. Comput.
Keywords
Field
DocType
THE ISING MODEL, STATISTICAL PHYSICS, FERROMAGNETISM, SPIN-GLASSES, PARTITION FUNCTION, NUMBER-P-COMPLETENESS, APPROXIMATION ALGORITHMS, MARKOV CHAINS, RAPID MIXING, MONTE-CARLO SIMULATION
Approximation algorithm,Discrete mathematics,Monte Carlo method,Combinatorics,Markov chain Monte Carlo,Partition function (mathematics),Markov chain,Ising model,Time complexity,Square-lattice Ising model,Mathematics
Journal
Volume
Issue
ISSN
22
5
0097-5397
ISBN
Citations 
PageRank 
0-387-52826-1
98
14.74
References 
Authors
2
2
Name
Order
Citations
PageRank
JerrumMark119933.55
Alistair Sinclair21506308.40