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:
- Is there any rigorous proof that this model is correct?
- 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?
- 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:
- $x_{1,1}, x_{2,2}, x_{4,3}, x_{3,4}$
- $x_{4,1}, x_{3,2}, x_{1,3}, x_{2,4}$
- $x_{1,1}, x_{3,2}, x_{4,3}, x_{2,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:
- $x_{1,4}, x_{2,3}, x_{3,2}, x_{4,1}$
- $x_{1,4}, x_{2,2}, x_{3,1}, x_{4,3}$
- $x_{1,3}, x_{2,4}, x_{3,1}, x_{4,2}$
- $x_{1,1}, x_{2,4}, x_{3,3}, x_{4,2}$
- $x_{1,4}, x_{2,3}, x_{3,1}, x_{4,2}$
What am I missing?