# NP-completeness of non-planar Ising model versus polynomial time eigenvalue algorithms

From the papers by Barahona and Istrail I understand that a combinatorial approach is followed to prove the NP-completeness of non-planar Ising models. Basic idea is non-planarity here. On the other hand, we have polynomial time algorithms for calculating eigenvalues for matrices. This confuses me. Should not be solving an Ising model be equivalent to calculating the eigenvalue of the Hamiltonian matrix of that model? In that case why is it NP-complete? Is coming up with such a Hamiltonian matrix at the first hand is NP-complete? If it is so, it makes the whole project (coming up with such Hamiltonian and solving it) NP-complete.

-
The algorithm for matrix diagonalization is polynomial in the size of your Hilbert space. That Hilbert space, however, grows exponentially with the number of lattice sites you consider. – Lagerbaer May 16 '13 at 16:28
@Lagerbaer, the Hilbert space is relevant when we try to write the Hamiltonian. So, should I assume that writing the Hamiltonian matrix, not solving it, is NP-complete? – Omar Shehab May 16 '13 at 18:05
If you actually want to write out the Hamiltonian in full, that problem is even beyond NP-complete, because writing it down requires exponential amount of space. – Lagerbaer May 16 '13 at 18:21
@Lagerbaer, Now I am even more confused. What is exactly NP-complete here? – Omar Shehab May 16 '13 at 18:43
Given the Hamiltonian for the particular Ising model it is NP-hard to find the ground state. The Hamiltonian doesn't have to be in matrix format, which is pretty wasteful. It can be in a simple form like $H = \sum_{i,j} S_i S_j$ or something to that extend. – Lagerbaer May 16 '13 at 19:09

If I understand your question correctly it says this:

• Papers show that the non-planar Ising model (finding its ground state) is NP complete
• On the other hand, finding the eigenvalues of a matrix is polynomial.
• So how do these points reconcile?

The important point here is in the size of the input. If you want to use the matrix diagonalization as a subroutine for your solution to the Ising model, you have to feed it a matrix. The matrix is a square matrix of some size $M \times M$ where $M$ depends exponentially on the number of lattice sites. Suppose we have ising spins that can be either up or down. Then for $N$ lattice sites the Hilbert space has size $M = 2^N$.

This means that your naive algorithm for solving the Ising model on a lattice with $N$ sites will be polynomial in terms of $M$ but therefore exponential in $N$.

And what do I mean by a Hamiltonian that's not in matrix form? Well, take the Ising Hamiltonian $$H = -\sum_{\langle i,j \rangle} J_{ij} \sigma_i \sigma_j$$

First, since we're talking about Ising spins, the $\sigma$ are not the Pauli matrices! If you used the pauli matrices we'd be dealing with the Heisenberg model. But even then, it wouldn't be in "matrix form". By matrix form, I mean: Pick a basis for the full Hilbert space, then write down a matrix for $H$ in that Hilbert space. This matrix will be exponentially big, as I've explained above.

-
Which part of this argument breaks down for $d \neq 3$? I was under the impression that the Ising model is NP-complete only for $d=3$. – Siva May 16 '13 at 23:00
@Lagerbaer, I think I know what went wrong with my understanding. I was trained as a computer scientist and doing my PhD in quantum computation. I learnt about Ising models from papers on adiabatic quantum computation (not by studying condensed matter physics). Papers like this (www-users.math.umd.edu/~mohara/mainthesis.pdf.gz), obviously not wrong but too simplified for me, generally express the Ising Hamiltonians in terms of Pauli spin matrices. So, I was brain washed with a limited understanding. – Omar Shehab May 16 '13 at 23:03
@OmarShehab, that confuses me since for $d \geq 4$, mean field theory is "good enough" if I understand correctly. But that's probably in the thermodynamic limit and I guess finite N would still be a pain to solve exactly. :-? – Siva May 16 '13 at 23:08
Well, just because a Hilbert space is very large doesn't mean the ground state is necessarily hard to compute. The harmonic oscillator, for example, has an infinitely large Hilbert space but the ground state is very easy to obtain. This expresses the fact that while we all know that brute force methods don't work on NP problems, there might be "clever" algorithms that are faster, we just haven't found them. – Lagerbaer May 16 '13 at 23:12
In reply to the question why it breaks down at, for example, $d = 2$ would be that the Ising model in 1 and 2 dimensions has an exact solution that we already know: nyu.edu/classes/tuckerman/stat.mech/lectures/lecture_26/… – Lagerbaer May 16 '13 at 23:13