<p>Well, you seem to be missing cases with high symmetry. Basically, any case where there is only a polynomial number of energy eigenvalues and it is easy to compute the degeneracy of these levels and easy to find an eigenstate with each eigenvalue should make the partition function efficiently computable. </p>

<p>An example of this would be a maximally connected graph for arbitrary J and h.</p>

<hr>

<p><strong>Update</strong></p>

<p>Since Yaroslav asked in a comment, here is the reasoning:</p>

<p>The partition function for the Ising model is (taking $\beta=1$) $Z_G=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right)$.</p>

<p>Notice that the first sum is over all configurations. We can separate this into two separate sums as follows:</p>

<p>$Z_G=\sum_{y=0}^n \sum_{x \in H_y} \exp\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right)$
where $H_y$ is the set of strings of Hamming weight $y$.</p>

<p>Next, note that every $x \in H_y$ has the same energy, due to the permutation invariance of the maximally connected graph. So we can define 
$E_y = -\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right) = -J\left( \binom{y}{2}+\binom{n-y}{2} - y(n-y)\right)-h(n-2y)$. </p>

<p>This gives $Z_G=\sum_{y=0}^n |H_y| ~ e^{-E_y} = \sum_{y=0}^n \binom{n}{y} ~ e^{-E_y}$. </p>

<p>As the sum has only $n$ terms, and each term is efficiently computable, the entire partition function can be efficiently computed to a chosen precision for the maximally connected graph of $n$ vertices. </p>

<p>The approach outlined above makes use of the fact that there is only a polynomial number of distinct eigenvalues and that both the value and degeneracy of each level is known. This works in general, whenever these conditions are satisfied, since we can then express the partition function as $Z=\sum_{y=0}^{poly(n)} D_y ~ e^{-E_y}$, where $D_y$ is the degeneracy of level $E_y$. If both $E_y$ and $D_y$ are efficiently computable, then we can compute this sum directly in polynomial time. This is true of all Hamiltonians, not simply the Ising model.</p>

CC BY-SA 2.5
2010-10-08T15:14:14.877Z
What's the algorithm to compute it for fully connected graph? Does it also work for classes with slightly less symmetry, like edge-transitive, vertex-transitive, regular?
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-08T19:55:29.097Z
I have updated my answer to add these details.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-08T20:22:39.480Z
Interesting, thanks! This looks similar to the derivation of mean field Ising in Baxter
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-08T21:15:49.743Z
No problem. It's worth noting, though, that this far it is exact. Hope it is useful anyway. It should be fairly easy to come up with examples other than the one I gave which satisfy these properties (for example trees of low depth but high branching, graphs with many of the vertices in a low number of cliques etc.)
Joe Fitzsimons
CC BY-SA 2.5
2010-10-08T21:34:10.853Z
BTW, what Baxter calls "mean field Ising model" in his "Exactly solved models in statistical mechanics" is an Ising model on a fully connected graph
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-08T21:49:05.300Z
Ah, ok. I have to admit, I come from a physics background, so mean-field means something a little different to me.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-08T21:56:00.190Z
Specifically, I take it to mean approximating a regular lattice by replacing the Hamiltonian with on corresponding to the fully connected graph.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-08T12:14:15.823Z
2010-10-08T21:20:18.340Z
2010-10-08T21:20:18.340Z
Joe Fitzsimons
<p>Consider Ising model on graph $G$ with uniform coupling strength $J$ and magnetic field $h$. I say its partition function <a href="https://cstheory.stackexchange.com/questions/2011/complexity-of-linearized-ising-model-at-0">$Z$</a> is easy to compute if $Z$ can be deterministically computed to arbitrary finite precision in time polynomial in size of the graph. </p>

<p>Here's when $Z$ is known to be easy to compute, what cases am I missing?</p>

<p>Arbitrary $J$</p>

<ol>
<li>$G$ is planar, $h=0$</li>
<li>treewidth$(G)\le C$</li>
</ol>

<p>Arbitrary $G$</p>

<ol>
<li>$|J|$ small relative to girth($G$)</li>
<li>$|J|$ small relative to the branching factor of self-avoiding walks on $G$</li>
</ol>

<p>I suspect it's easy to compute for all $J$ with minor-excluded $G$ and for all $G$ with $J&gt;0$ because FPRAS exist for these cases. Also it seems $G$ with $|J|\ll |h|$ should be easy because of correlation decay, although I haven't seen either FPDAS or FPRAS in this case</p>

CC BY-SA 2.5
2010-10-08T06:12:45.803Z
There is a dichotomy theorem: every partition function is either computable in polynomial time or #P-complete, GOLDBERG , GROHE, JERRUM, AND
 THURLEY,
[COMPLEXITY DICHOTOMY FOR PARTITION FUNCTIONS
WITH MIXED SIGNS](http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000039000007003336000001&idtype=cvips&gifs=yes&ref=no), SIAM J. COMPUT., 
Vol. 39, No. 7, pp. 3336–3402
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-08T06:36:53.297Z
Interesting, they give an explicit characterization of tractable partition functions, but then say that it offers no insight. BTW, their definition of "tractable" is more restrictive than my definition of "easy". Z can be intractable even though it can be computed in polynomial time to arbitrary finite precision, so I would still consider it "easy."
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-08T06:45:30.327Z
What is the motivation for redefining "easy"?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-08T06:49:09.067Z
Because I'm interested in practical applications, so only a finite number of significant digits is needed
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-08T07:14:40.210Z
Jerrum, Valiant, and Vazirani proved a dichotomy theorem:  From Wikipedia: 
["Every #P-complete problem either has an FPRAS, or is essentially impossible to approximate"](http://en.wikipedia.org/wiki/Sharp-P-complete)
. I suggest looking for FPRAS. Here is a quote from Wikipedia: "Many #P-complete problems have a fully-polynomial-time randomized approximation scheme, or FPRAS, which, informally, will produce with high probability an approximation to an arbitrary degree of accuracy, in time that is polynomial with respect to both the size of the problem and the degree of accuracy required"
Mohammad Al-Turkistany
<cc.complexity-theory><counting-complexity><physics><statistical-physics>
When is Ising partition function easy to compute?
Yaroslav Bulatov
# When is Ising partition function easy to compute?

(Asked by: username_0 on 2010-10-08)

Consider Ising model on graph $G$ with uniform coupling strength $J$ and magnetic field $h$. I say its partition function [$Z$](https://cstheory.stackexchange.com/questions/2011/complexity-of-linearized-ising-model-at-0) is easy to compute if $Z$ can be deterministically computed to arbitrary finite precision in time polynomial in size of the graph.

Here's when $Z$ is known to be easy to compute, what cases am I missing?

Arbitrary $J$

1. $G$ is planar, $h=0$
2. treewidth$(G)\le C$

Arbitrary $G$

1. $|J|$ small relative to girth($G$)
2. $|J|$ small relative to the branching factor of self-avoiding walks on $G$

I suspect it's easy to compute for all $J$ with minor-excluded $G$ and for all $G$ with $J>0$ because FPRAS exist for these cases. Also it seems $G$ with $|J|\ll |h|$ should be easy because of correlation decay, although I haven't seen either FPDAS or FPRAS in this case

**Tags:** cc.complexity-theory, counting-complexity, physics, statistical-physics

> **Comments:**
> **username_1**: There is a dichotomy theorem: every partition function is either computable in polynomial time or #P-complete, GOLDBERG , GROHE, JERRUM, AND  THURLEY, [COMPLEXITY DICHOTOMY FOR PARTITION FUNCTIONS WITH MIXED SIGNS](http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000039000007003336000001&idtype=cvips&gifs=yes&ref=no), SIAM J. COMPUT.,  Vol. 39, No. 7, pp. 3336–3402  
> **username_0**: Interesting, they give an explicit characterization of tractable partition functions, but then say that it offers no insight. BTW, their definition of "tractable" is more restrictive than my definition of "easy". Z can be intractable even though it can be computed in polynomial time to arbitrary finite precision, so I would still consider it "easy."  
> **username_1**: What is the motivation for redefining "easy"?  
> **username_0**: Because I'm interested in practical applications, so only a finite number of significant digits is needed  
> **username_1**: Jerrum, Valiant, and Vazirani proved a dichotomy theorem:  From Wikipedia:  ["Every #P-complete problem either has an FPRAS, or is essentially impossible to approximate"](http://en.wikipedia.org/wiki/Sharp-P-complete) . I suggest looking for FPRAS. Here is a quote from Wikipedia: "Many #P-complete problems have a fully-polynomial-time randomized approximation scheme, or FPRAS, which, informally, will produce with high probability an approximation to an arbitrary degree of accuracy, in time that is polynomial with respect to both the size of the problem and the degree of accuracy required"  

---

## 1 answers

### Answer by username_2 on 2010-10-08. Score: 6 | Accepted answer

Well, you seem to be missing cases with high symmetry. Basically, any case where there is only a polynomial number of energy eigenvalues and it is easy to compute the degeneracy of these levels and easy to find an eigenstate with each eigenvalue should make the partition function efficiently computable.

An example of this would be a maximally connected graph for arbitrary J and h.

---

**Update**

Since Yaroslav asked in a comment, here is the reasoning:

The partition function for the Ising model is (taking $\beta=1$) $Z\_G=\sum\_{x\in \mathcal{X}} \exp\left(J \sum\_{(i,j)\in E} x\_i x\_j + h \sum\_i x\_i\right)$.

Notice that the first sum is over all configurations. We can separate this into two separate sums as follows:

$Z\_G=\sum\_{y=0}^n \sum\_{x \in H\_y} \exp\left(J \sum\_{(i,j)\in E} x\_i x\_j + h \sum\_i x\_i\right)$
where $H\_y$ is the set of strings of Hamming weight $y$.

Next, note that every $x \in H\_y$ has the same energy, due to the permutation invariance of the maximally connected graph. So we can define
$E\_y = -\left(J \sum\_{(i,j)\in E} x\_i x\_j + h \sum\_i x\_i\right) = -J\left( \binom{y}{2}+\binom{n-y}{2} - y(n-y)\right)-h(n-2y)$.

This gives $Z\_G=\sum\_{y=0}^n |H\_y| ~ e^{-E\_y} = \sum\_{y=0}^n \binom{n}{y} ~ e^{-E\_y}$.

As the sum has only $n$ terms, and each term is efficiently computable, the entire partition function can be efficiently computed to a chosen precision for the maximally connected graph of $n$ vertices.

The approach outlined above makes use of the fact that there is only a polynomial number of distinct eigenvalues and that both the value and degeneracy of each level is known. This works in general, whenever these conditions are satisfied, since we can then express the partition function as $Z=\sum\_{y=0}^{poly(n)} D\_y ~ e^{-E\_y}$, where $D\_y$ is the degeneracy of level $E\_y$. If both $E\_y$ and $D\_y$ are efficiently computable, then we can compute this sum directly in polynomial time. This is true of all Hamiltonians, not simply the Ising model.

> **Comments:**
> **username_0**: What's the algorithm to compute it for fully connected graph? Does it also work for classes with slightly less symmetry, like edge-transitive, vertex-transitive, regular?  
> **username_2**: I have updated my answer to add these details.  
> **username_0**: Interesting, thanks! This looks similar to the derivation of mean field Ising in Baxter  
> **username_2**: No problem. It's worth noting, though, that this far it is exact. Hope it is useful anyway. It should be fairly easy to come up with examples other than the one I gave which satisfy these properties (for example trees of low depth but high branching, graphs with many of the vertices in a low number of cliques etc.)  
> **username_0**: BTW, what Baxter calls "mean field Ising model" in his "Exactly solved models in statistical mechanics" is an Ising model on a fully connected graph  
> **username_2**: Ah, ok. I have to admit, I come from a physics background, so mean-field means something a little different to me.  
> **username_2**: Specifically, I take it to mean approximating a regular lattice by replacing the Hamiltonian with on corresponding to the fully connected graph.  

---

