A quantum algorithm for the Ising model
by
Ashwin Nayak
University of Waterloo and Perimeter Institute
Coauthors: Leonard Schulman (Caltech) and Umesh Vazirani (UC Berkeley)

The Ising model has been widely studied as a model for magnetisation in the area of statistical physics. Computational solutions to problems centred around the Ising model are based on sampling from the Gibbs distribution for the model. We demonstrate how one can sample from this distribution efficiently on a quantum computer. Our algorithm follows an approach that is radically different from an efficient classical solution that was discovered subsequently. In particular, our algorithm illustrates how a seemingly hard-to-sample-from distribution (for instance, using standard Markov chain techniques) can be transformed to an efficiently sampleable distribution via a quantum Fourier transform. The algorithm is polynomially more efficient than the best known classical algorithm in certain regimes, and may generalise to the Potts model as well.

Date received: May 2, 2004