What should be the lowest energy of this graph isomorphism QUBO?
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:
QUBO_Matrix =[[-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.]]
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!