6
$\begingroup$

Consider Ising model on graph $G$ with uniform coupling strength $J$ and magnetic field $h$. I say its partition function $Z$ 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

$\endgroup$
5
  • 2
    $\begingroup$ 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, SIAM J. COMPUT., Vol. 39, No. 7, pp. 3336–3402 $\endgroup$ Oct 8, 2010 at 6:12
  • $\begingroup$ 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." $\endgroup$ Oct 8, 2010 at 6:36
  • $\begingroup$ What is the motivation for redefining "easy"? $\endgroup$ Oct 8, 2010 at 6:45
  • $\begingroup$ Because I'm interested in practical applications, so only a finite number of significant digits is needed $\endgroup$ Oct 8, 2010 at 6:49
  • 1
    $\begingroup$ Jerrum, Valiant, and Vazirani proved a dichotomy theorem: From Wikipedia: "Every #P-complete problem either has an FPRAS, or is essentially impossible to approximate" . 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" $\endgroup$ Oct 8, 2010 at 7:14

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ Oct 8, 2010 at 15:14
  • $\begingroup$ I have updated my answer to add these details. $\endgroup$ Oct 8, 2010 at 19:55
  • $\begingroup$ Interesting, thanks! This looks similar to the derivation of mean field Ising in Baxter $\endgroup$ Oct 8, 2010 at 20:22
  • $\begingroup$ 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.) $\endgroup$ Oct 8, 2010 at 21:15
  • $\begingroup$ 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 $\endgroup$ Oct 8, 2010 at 21:34
2
$\begingroup$

It can also be computed for h=0 and low genus (i.e., "almost planar"). I believe the complexity is exponential in the genus.

$\endgroup$
3
  • $\begingroup$ What's the algorithm for low genus? $\endgroup$ Oct 8, 2010 at 16:43
  • $\begingroup$ I believe (but this is all based on memory, and I don't know the refs) that it still reduces to a calculation of determinants, as in the planar case. However, one has to sum over different spin structures. A quick web search gives this paper arxiv.org/PS_cache/cond-mat/pdf/0306/0306396v1.pdf as one that mentions the sum over determinants (see eq 5), giving a complexity scaling as 4^g, though I am pretty sure that that paper isn't the original reference. $\endgroup$
    – matt hastings
    Oct 8, 2010 at 18:54
  • $\begingroup$ Interesting! I haven't seen this extension in CS literature. Notably, recent papers on Ising partition for planar graphs also rely on Kasteleyn's method $\endgroup$ Oct 8, 2010 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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