  We show that the quantum dynamics of interacting and noninteracting quantum
particles are fundamentally different in the context of solving a particular
computational problem. Specifically, we consider the graph isomorphism problem,
in which one wishes to determine whether two graphs are isomorphic (related to
each other by a relabeling of the graph vertices), and focus on a class of
graphs with particularly high symmetry called strongly regular graphs (SRG's).
We study the Green's functions that characterize the dynamical evolution
single-particle and two-particle quantum walks on pairs of non-isomorphic SRG's
and show that interacting particles can distinguish non-isomorphic graphs that
noninteracting particles cannot. We obtain the following specific results: (1)
We prove that quantum walks of two noninteracting particles, Fermions or
Bosons, cannot distinguish certain pairs of non-isomorphic SRG's. (2) We
demonstrate numerically that two interacting Bosons are more powerful than
single particles and two noninteracting particles, in that quantum walks of
interacting bosons distinguish all non-isomorphic pairs of SRGs that we
examined. By utilizing high-throughput computing to perform over 500 million
direct comparisons between evolution operators, we checked all tabulated pairs
of non-isomorphic SRGs, including graphs with up to 64 vertices. (3) By
performing a short-time expansion of the evolution operator, we derive
distinguishing operators that provide analytic insight into the power of the
interacting two-particle quantum walk.
