4
$\begingroup$

Suppose $Z_G(J,h)$ is a partition function of Ising model with coupling $J$ and magnetic field $h$ on graph $G$. What is the complexity of finding the gradient of Z at $\mathbf{0}$?

Specifically, if $n$ is the number of vertices, $E$ is a set of edges, $\mathcal{X}=\{1,-1\}^n$, the gradient is of the following function $$Z(J,h)=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right)$$

$\endgroup$
1
$\begingroup$

Not a full answer, but hopefully at least helpful. Computing the ground state of such an Ising Hamiltonian is NP-hard, as it contains Max-2-SAT, even if the couplings are restricted to $\pm J$. This is simply because if you take a 2-SAT instance, you can add the term $Jx_ix_j - Jx_ix_0 - J x_jx_0 = \mbox{daig}(-1,-1,-1,3)$ which is minimized iff $x_i \vee x_j$. Thus adding such terms to form a Hamiltonian will result in a spectrum where the ground state corresponds to the assignment of variables which maximizes the clauses satisfied as this corresponds to the maximum number of negative terms in the Hamiltonian. By adding an ancilla system it is then possible to create many such levels (via the tensor product of the two Hilbert spaces) with different energy levels. By tweaking the terms in the ancilla system, you can manipulate the absolute value of the energy levels corresponding to the ground state of the primary system and different excited states of the ancilla system. This would seem to indicate that the general problem is NP-hard. In the specific case of your question, you seem to fix J to be constant and positive which would seem to cause a problem with representing the negation of a variable in any of the clauses, and so this argument may not apply.

You may also be interested in cond-mat/0309240 for some results relating Ising lattices with various complexity classes.

Hope this is useful.

$\endgroup$
  • $\begingroup$ Note that I'm asking for restriction to J=0,h=0 which makes partition function and ground-state trivial $\endgroup$ – Yaroslav Bulatov Oct 7 '10 at 23:55
  • $\begingroup$ Yes. However, as I understand it you are interested in the gradient, rather than the partition function (which is trivial), and so the fact that there are hard instances close to this point should indicate that this is a hard problem. In other words, if you consider both $\sigma_z$ operators and their negation in the Hamiltonian, then there are graphs which embody every instance of Max-2-SAT. Since the partition function is trivially computable at 0, determining the gradient should be as hard as determining the partition function at a non-0 point. $\endgroup$ – Joe Fitzsimons Oct 8 '10 at 0:01
  • $\begingroup$ Z is easy to compute for J close to 0. Ground-state can be hard in such case, but is that relevant to computing Z'? That's not so clear to me $\endgroup$ – Yaroslav Bulatov Oct 8 '10 at 0:21
  • $\begingroup$ Well, this will presumably depend on the accuracy to which you want to calculate Z. As I say, I don't consider what I posted to be a complete answer, but I believe the hardness of finding certain states (ground states etc.) indicates that the gradient of the partition function will be hard to compute. $\endgroup$ – Joe Fitzsimons Oct 8 '10 at 0:37
1
$\begingroup$

Duh....I got a suggestion to use chain rule and just compute the derivative. The derivative factors when $J=0$, so this makes the problem trivial for all graphs when $J=0$ and $h$ is arbitrary.

$\endgroup$
  • $\begingroup$ Setting J=0 removes all correlation terms, so you can simply compute the partition function and its derivative from the single spin case, but in this case it is a stretch to call it the Ising model, as there are no Ising terms in the Hamiltonian. $\endgroup$ – Joe Fitzsimons Oct 8 '10 at 12:56

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.