Sampling Spin Configurations of an Ising System

Dana Randall and David Wilson

We present the first provably polynomial time sampling scheme for generating spin configurations of any ferromagnetic Ising system, one of the most widely studied models in statistical mechanics. The algorithm is based on the randomized approximation scheme of Jerrum and Sinclair which estimates the partition function of the Ising system using the so-called ``high temperature expansion'' representation. Their estimation algorithm did not give rise to an Ising sampling algorithm via self-reducibility because ferromagnetism was not preserved by the reductions. Recently Nayak, Schulman, and Vazirani gave a quantum algorithm for sampling Ising spin states based on the JS algorithm. We show that by using the JS algorithm and a third equivalent representation of the Ising partition function (the Fortuin-Kasteleyn ``random-cluster model''), self-reducibility yields a (classical) polynomial time algorithm for sampling Ising spin configurations.

DVI version
PostScript version

Scanned version in the ACM's Digital Library, copyright © 1999 by ACM, Inc.