Using the graph isomorphism problem to probe differences between discrete- and continuous-time quantum random walks

Though continuous-time and discrete-time quantum walks appear superficially similar, recent studies have demonstrated potential differences in terms of algorithmic power. We investigate these disparities in the context of the graph isomorphism problem. It has been previously demonstrated that discrete-time walks of two non-interacting particles can distinguish certain difficult-to-distinguish graphs, while it has been proven that continuous-time walks of two non-interacting particles can never distinguish these graphs. We show the origins of this difference in distinguishing power, and find that, even for identical walks, subtle differences in the certificate construction algorithm can non-trivially impact the walk's distinguishing power.