Quantum Random Walks and the Graph Isomorphism Problem*

We investigate the quantum dynamics of particles on graphs (``quantum walk''), with the aim of developing quantum algorithms for determining whether or not two graphs are isomorphic. We investigate such walks on strongly regular graphs (SRGs), a class of graphs with high symmetry. We explore the effects of particle number and interaction range on a walk's ability to distinguish non-isomorphic graphs. We numerically find that both non-interacting three-boson and three-fermion continuous time walks have the same distinguishing power on a dataset of 70,712 pairs of SRGs, each distinguishing over 99.6\% of the pairs. We also find that increasing to four non-interacting particles further increases distinguishing power on this dataset. While increasing particle number increases distinguishing power, we prove that any walk of a fixed number of non-interacting particles cannot distinguish all SRGs. We numerically find that increasing particle number and increasing interaction range both result in increased distinguishing power of non-SRGs that are designed to be indistinguishable to the hard-core two-boson walk.