<p>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.</p>

CC BY-SA 2.5
2010-10-08T12:56:44.080Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-08T01:20:34.430Z
2010-10-08T01:29:25.257Z
2010-10-08T01:29:25.257Z
Yaroslav Bulatov
<p>Not a full answer, but hopefully at least helpful. Computing the ground state of such an Ising Hamiltonian is NP-hard, as it contains <a href="http://en.wikipedia.org/wiki/2-satisfiability#Maximum-2-satisfiability" rel="nofollow">Max-2-SAT</a>, 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.</p>

<p>You may also be interested in <a href="http://arxiv.org/abs/cond-mat/0309240" rel="nofollow">cond-mat/0309240</a> for some results relating Ising lattices with various complexity classes. </p>

<p>Hope this is useful.</p>

CC BY-SA 2.5
2010-10-07T23:55:51.167Z
Note that I'm asking for restriction to J=0,h=0 which makes partition function and ground-state trivial
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-08T00:01:43.427Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-08T00:21:04.623Z
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
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-08T00:37:12.213Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-07T23:31:57.473Z
2010-10-07T23:31:57.473Z
Joe Fitzsimons
<p>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}$?</p>

<p>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)$$</p>

<cc.complexity-theory><counting-complexity><physics><statistical-physics>
Complexity of linearized Ising model at 0
Yaroslav Bulatov
# Complexity of linearized Ising model at 0

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

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)$$

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


---

## 2 answers

### Answer by username_0 on 2010-10-08. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_1**: 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.  

---

### Answer by username_1 on 2010-10-07. Score: 1

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](http://en.wikipedia.org/wiki/2-satisfiability#Maximum-2-satisfiability), 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](http://arxiv.org/abs/cond-mat/0309240) for some results relating Ising lattices with various complexity classes.

Hope this is useful.

> **Comments:**
> **username_0**: Note that I'm asking for restriction to J=0,h=0 which makes partition function and ground-state trivial  
> **username_1**: 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.  
> **username_0**: 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  
> **username_1**: 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.  

---

