Abstract:
We present and compare various methods to construct efficient QUBO formulations for the Graph Isomorphism Problem - one of a very few problems in NP that is neither known to be solvable in polynomial time nor NP-complete - and two related Subgraph Isomorphism Problems that are NP-hard. Experimental results on two QUBO formulations of the Graph Isomorphism Problem suggest that our direct formulation is more practical than the others with respect to running on the D-Wave architecture.