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$
  • 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$ – Mohammad Al-Turkistany Oct 8 '10 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$ – Yaroslav Bulatov Oct 8 '10 at 6:36
  • $\begingroup$ What is the motivation for redefining "easy"? $\endgroup$ – Mohammad Al-Turkistany Oct 8 '10 at 6:45
  • $\begingroup$ Because I'm interested in practical applications, so only a finite number of significant digits is needed $\endgroup$ – Yaroslav Bulatov Oct 8 '10 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$ – Mohammad Al-Turkistany Oct 8 '10 at 7:14
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$
  • $\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$ – Yaroslav Bulatov Oct 8 '10 at 15:14
  • $\begingroup$ I have updated my answer to add these details. $\endgroup$ – Joe Fitzsimons Oct 8 '10 at 19:55
  • $\begingroup$ Interesting, thanks! This looks similar to the derivation of mean field Ising in Baxter $\endgroup$ – Yaroslav Bulatov Oct 8 '10 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$ – Joe Fitzsimons Oct 8 '10 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$ – Yaroslav Bulatov Oct 8 '10 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$
  • $\begingroup$ What's the algorithm for low genus? $\endgroup$ – Yaroslav Bulatov Oct 8 '10 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 '10 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$ – Yaroslav Bulatov Oct 8 '10 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.