Noninteracting multiparticle quantum random walks applied to the graph isomorphism problem for strongly regular graphs

Abstract

We investigate the quantum dynamics of particles on graphs (``quantum random walks''), with the aim of developing quantum algorithms for determining if two graphs are isomorphic (related to each other by a relabeling of vertices). We focus on quantum random walks of multiple noninteracting particles on strongly regular graphs (SRGs), a class of graphs with high symmetry that is known to have pairs of graphs that are hard to distinguish. Previous work has already demonstrated analytically that two-particle noninteracting quantum walks cannot distinguish nonisomorphic SRGs of the same family. Here, we demonstrate numerically that three-particle noninteracting quantum walks have significant, but not universal, distinguishing power for pairs of SRGs, proving a fundamental difference between the distinguishing power of two-particle and three-particle noninteracting walks. We show analytically why this distinguishing power is possible, whereas it is forbidden for two-particle noninteracting walks. Based on sampling of SRGs with up to 64 vertices, we find no difference in the distinguishing power of bosonic and fermionic walks. In addition, we find that the four-fermion noninteracting walk has greater distinguishing power than the three-particle walk on SRGs, showing that increasing the particle number increases the distinguishing power. However, we also show analytically that no noninteracting walk with a fixed number of particles can distinguish all SRGs, thus demonstrating a potential fundamental difference in the distinguishing power of interacting versus noninteracting walks.