Abstract:
In this paper we provide a practically efficient QUBO formulation for the Graph
Isomorphism Problem that is suitable for quantum annealers, such as those produced
by D-Wave. After proving correctness of our new method, based on exploiting vertex
degree classes, we do some experimental work on a D-Wave 2X computer. We observe
that for all \hard" graphs of 6 vertices, we save around 50% to 95% of the number of
required qubits over the standard QUBO formulation that was given earlier by Calude
et al [13]. We also provide some theoretical analysis showing that for two random
graphs with the same degree sequence our new method substantially improves in qubit
savings as the number of vertices increases beyond 6.