Sampling Spin Configurations of an Ising System - Randall, Dana; Wilson, David (SODA '99 Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, 1999)
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.