Two-particle quantum walks applied to the graph isomorphism problem

We show that an algorithm based on the dynamics of interacting quantum particles is more powerful than the corresponding algorithm for non-interacting particles. Specifically, our algorithm attempts to determine whether two graphs are isomorphic. We focus on strongly regular graphs (SRGs), a class of graphs with particularly high symmetry. By studying the dynamical evolution of two-particle quantum walks on pairs of non-isomorphic SRG's, we show that interacting particles can distinguish non-isomorphic graphs that noninteracting particles cannot. First, we prove that quantum walks of two noninteracting particles cannot distinguish pairs of non-isomorphic SRG's. Next, we demonstrate numerically that two interacting bosons are more powerful, in that their quantum walks distinguish all non-isomorphic pairs of SRGs we tried, including those with up to 64 vertices. Finally, we find a set of operators that determine these evolutions.