  In the Graph Isomorphism problem two N-vertex graphs G and G' are given and
the task is to determine whether there exists a permutation of the vertices of
G that preserves adjacency and transforms G into G'. If yes, then G and G' are
said to be isomorphic; otherwise they are non-isomorphic. The GI problem is an
important problem in computer science and is thought to be of comparable
difficulty to integer factorization. In this paper we present a quantum
algorithm that solves arbitrary instances of GI and can also determine all
automorphisms of a given graph. We show how the GI problem can be converted to
a combinatorial optimization problem that can be solved using adiabatic quantum
evolution. We numerically simulate the algorithm's quantum dynamics and show
that it correctly: (i) distinguishes non-isomorphic graphs; (ii) recognizes
isomorphic graphs; and (iii) finds all automorphisms of a given graph G. We
then discuss the GI quantum algorithm's experimental implementation, and close
by showing how it can be leveraged to give a quantum algorithm that solves
arbitrary instances of the NP-Complete Sub-Graph Isomorphism problem.
