Sampling Spin Configurations of an Ising System
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.