# Random bond Ising model and computational efficiency

+ 3 like - 0 dislike
19 views

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?

This post has been migrated from (A51.SE)

+ 2 like - 0 dislike

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: http://www.cs.brown.edu/people/sorin/pdfs/Ising-paper.pdf

This post has been migrated from (A51.SE)
answered Jan 27, 2012 by (80 points)
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. www.yaroslavvb.com/papers/barahona-on.pdf

This post has been migrated from (A51.SE)

 Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead. To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL. Please consult the FAQ for as to how to format your post. This is the answer box; if you want to write a comment instead, please use the 'add comment' button. Live preview (may slow down editor)   Preview Your name to display (optional): Email me at this address if my answer is selected or commented on: Privacy: Your email address will only be used for sending these notifications. Anti-spam verification: If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:p$\hbar$ysicsOverfl$\varnothing$wThen drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds). To avoid this verification in future, please log in or register.