I am trying to study QUBO formulations of the graph isomorphism problem. I tried implementing the QUBO matrices given by the algorithms described in here. For the two input graphs therein, I am getting the matrix $Q$ given by:
$Q = \begin{pmatrix} -1 & 1 & 1 & 0 & 0\\ 0 & -1 & 0 & 1 & 0\\ 0 & 0& -1& 1 & 0\\ 0 & 0& 0& -1& 0\\ 0 & 0& 0& 0& -1 \end{pmatrix}$
This turns out to be the same matrix as given in the paper. From here, I applied the following lines of code:
bqm = dimod.BinaryQuadraticModel.from_numpy_matrix(QUBO_Matrix)
qubo, offset = bqm.to_qubo()
sampler = LeapHybridSampler()
results = sampler.sample_qubo(qubo, label='Graph Isomorphism')
print(results)
______________________________________________
Output:
0 1 2 3 4 energy num_oc.
0 0 1 1 0 1 -3.0 1
['BINARY', 1 rows, 1 samples, 5 variables]
I think I am doing something fundamentally wrong here as the graphs are isomorphic and as per my understanding, these isomorphic graphs would return a ground state energy of 0 where I am getting a ground state energy of -3.
Even when I am taking non-isomorphic graphs i.e. one of the graphs from the paper and the other, a square graph, I am getting a ground state energy (by the same method) of -1.
I think I am missing something very fundamental here. I would really appreciate it if someone pointed me in the right direction. Thanks in advance!
