# 3D Ising model is computationally intractable

106

views

0

I was not aware that the innocent-looking 3D Ising model,

\( H_{\text{Ising}} = -\frac{1}{2} \sum_{\langle i, j \rangle} J_{i,j} \, S_i^z \, S_j^z \) ,

with the distance-dependent coupling \( J_{i,j} \), has been proven to be computationally intractable!

See, e.g.,

Cipra, B. A. “The Ising model is NP-complete”. SIAM News, July 17, 2000.

It is amazing really, but very mysterious:

* How could we have so much complexity in such a “tiny” toy-Hamiltonian?

* How much “information” can be stored in an “Ising Cube”?

* The 3D Ising model is NP-complete: So just solve it and you be able to solve

#The Art of Mean-Field Theory

\( H_{\text{Ising}} = -\frac{1}{2} \sum_{\langle i, j \rangle} J_{i,j} \, S_i^z \, S_j^z \) ,

with the distance-dependent coupling \( J_{i,j} \), has been proven to be computationally intractable!

See, e.g.,

Cipra, B. A. “The Ising model is NP-complete”. SIAM News, July 17, 2000.

It is amazing really, but very mysterious:

* How could we have so much complexity in such a “tiny” toy-Hamiltonian?

* How much “information” can be stored in an “Ising Cube”?

* The 3D Ising model is NP-complete: So just solve it and you be able to solve

*all*other NP-hard problems!#The Art of Mean-Field Theory

https://arxiv.org/abs/1207.6891