Numerical investigations of quantum walks with hard-core bosons and the graph isomorphism problem*

Gamble et al. investigated quantum walks of two hard-core bosons on a class of highly symmetric graphs called strongly regular graphs (SRGs) and showed that these walks will distinguish nonisomorphic graphs from the same family. However, J. Smith (arXiv:1004.0206) has shown that pairs of nonisomorphic graphs exist that cannot be distinguished by such quantum walks. Here we construct explicit counterexample graph pairs for 2 and 3-particle interacting and non-interacting walks. We also describe an algorithm that, given $k$ particles, generates two graphs indistinguishable by a $k$-boson quantum walk. We find that these indistinguishable graph pairs generated by our algorithm scale in size quadratically with the number of particles. It follows that distinguishing graphs via simulating quantum walks with classical computers will likely require exponential time in the size of the graph, while leaving open the possibility that a quantum computer could distinguish the graphs in polynomial time.