Sampling Spin Configurations of an Ising System
- Dana Randall ,
- David Wilson
SODA '99 Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms |
Published by Association for Computing Machinery, Inc.
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.
Copyright © 1999 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org. The definitive version of this paper can be found at ACM's Digital Library -http://www.acm.org/dl/.