Decoherence-enhanced performance of quantum walks applied to graph isomorphism testing
M. Bruderer, Martin Bodo Plenio · Physical Review A · 2016
Computational advantages gained by quantum algorithms rely largely on the coherence of quantum devices and are generally compromised by decoherence. As an exception, we present a quantum algorithm for graph isomorphism testing whose performance is optimal when operating in the partially coherent regime, as opposed to the extremes of fully coherent or classical regimes. The algorithm builds on continuous-time quantum stochastic walks (QSWs) on graphs and the algorithmic performance is quantified by the distinguishing power between nonisomorphic graphs. The QSW explores the entire graph and acquires information about the underlying structure, which is extracted by monitoring stochastic jumps across an auxiliary edge. The resulting counting statistics of stochastic jumps is used to identify the spectrum of the dynamical generator of the QSW, serving as a novel graph invariant, based on which nonisomorphic graphs are distinguished. We provide specific examples of nonisomorphic graphs that are only distinguishable by QSWs in the presence of decoherence.