Physically-motivated dynamical algorithms for the graph isomorphism problem

The graph isomorphism problem (GI) plays a central role in the theory of computational complexity and has importance in physics and chemistry as well. No polynomial-time algorithm for solving GI is known. We investigate quantum physics-based polynomial- time algorithms for solving the graph isomorphism problem in which the graph structure is reflected in the behavior of a dynamical system. The method is to construct graph invariants based on the two-particle Green's function on the graph. The algorithm has been tested on strongly regular graphs - graphs that are known to be very difficult to distinguish by conventional means - up N=35, where N is the number of vertices. The GF for non-interacting fermions successfully distinguishes all pairs of non-isomorphic graphs for N $<$ 35 while that for hard-core bosons works for all graphs tested.