Improved QUBO Formulation of the Graph Isomorphism Problem

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.