Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If you want to find the ground state of the 2d random bond Ising model (no field), a computationally efficient algorithm exists to do it for you (based on minimum weight perfect matching). What about the thermal state for some finite temperature, T? Is there an efficient (i.e. time scales polynomially with system size) way to sample states of different spin configurations from this distribution?

share|cite|improve this question
Does this help? – wsc Jan 26 '13 at 18:35
up vote 2 down vote accepted

The divide between tractable and intractable was shown by Sorin Istrail to be between planar and non-planar graphs. Since 2D surfaces can have non-planar graphs imbedded in them I think (correct me if I'm wrong) planar RBIMs are what you want to look at.

That said, Istrail showed that for {-J,0,J} couplings the ground state as well as the partition function can be efficiently calculated. I'm not sure of the exact details, but the calculation of the partition function can be mapped to the calculation of the determinant which is efficient. The specifics are available as references in the paper below.

Istrail's Paper:

share|cite|improve this answer
The basic result, i.e.: that obtaining the random-bond-Ising GS for non-planar lattices is NP-complete, was proved by Barahona in 1982. – Javier Rodriguez Laguna Jan 31 '12 at 18:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.