QUBO formulations for the graph isomorphism problem and related problems

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.