Proof of an Ising model representation of graph isomorphism problem

Question

I am going to through Ising formulations of many NP problems by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two gaphs, $G_1$ and $G_2$, the Ising Hamiltonian, $H$ is,

$$ H = A \sum_v \left(1 - \sum_i x_{v,i}\right)^2 + A \sum_i \left(1 - \sum_v x_{v,i}\right)^2 \\ + B\sum_{ij\not\in E_1}\sum_{uv \in E_2} x_{u,i} x_{v,j} + B \sum_{ij \in E_1}\sum_{uv \not\in E_2} x_{u,i} x_{v,j} $$

Here, $|G_1|=|G_2|$ and the binary variable $x_{v,i}$ is $1$ when if vertex $v$ in $G_2$ is mapped to vertex $i$ of $G_1$. For an isomorphic pair, $H = 0$.

My questions:

1. Is there any rigorous proof that this model is correct?
2. I understand that the classical computational complexity of the graph isomorphism problem is not known but it is conjectured to be NP-intermediate. On the other hand the classical computational complexity of the Ising model is well understood. So, if the graph isomorphism problem can be reduced to an Ising model in polynomial time, shouldn't be it's complexity same as the Ising model problem?
3. When I code it up using Mathematica (assuming $A = B = 1$) for the following two isomorphic graph pairs, I am getting false positives.

The graphs are:

and .

For this pair of graphs, I get the following configurations which are correct isomorphisms and for them $H=0$. They are:

1. $x_{1,1}, x_{2,2}, x_{4,3}, x_{3,4}$
2. $x_{4,1}, x_{3,2}, x_{1,3}, x_{2,4}$
3. $x_{1,1}, x_{3,2}, x_{4,3}, x_{2,4}$
4. $x_{4,1}, x_{2,2}, x_{1,3}, x_{3,4}$

But when I evaluate the Ising formulation with all possible inputs using Mathematica, I get five more false positives along with these four. They are:

1. $x_{1,4}, x_{2,3}, x_{3,2}, x_{4,1}$
2. $x_{1,4}, x_{2,2}, x_{3,1}, x_{4,3}$
3. $x_{1,3}, x_{2,4}, x_{3,1}, x_{4,2}$
4. $x_{1,1}, x_{2,4}, x_{3,3}, x_{4,2}$
5. $x_{1,4}, x_{2,3}, x_{3,1}, x_{4,2}$

What am I missing?

Answer 1

The counterexamples you give are not correct. I suspect your bug is this: when doing the sums over edges in (or not in) $E_1$ and $E_2$, you need to consider both orderings of each pair.

Consider your first false positive. One of the mismatched edges corresponds to (the lack of) $(2,4)$ in $G_1$, which maps to $(3,1)$ in $G_2$ (which is present). This makes the third term in the sum non-zero: consider $(i,j)$=$(2,4)$ and $(u,v)$=$(3,1)$; $x_{3,2}x_{1,4}$ is non-zero. If you only consider the edge pairs $(u,v)$ where $u<v$, you miss counting these non-zero terms and get the incorrect zero result.