Decoherence-enhanced performance of quantum walks applied to graph isomorphism testing

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.

Figure 1

The proposed algorithm for graph isomorphism testing: A quantum stochastic walk (QSW) on the graph relaxes to the steady state. The number of jumps $N$ per time interval across an auxiliary edge is monitored, yielding the counting statistics $p\left(N\right)$. The distribution $p\left(N\right)$ is used to determine the complex spectrum $\sigma$ of the generator of the QSW. Graphs are compared by their spectra, where different spectra indicate nonisomorphism.

Figure 2

Pairs of nonisomorphic graphs demonstrate the higher DIP of the $\omega$ spectrum. The pairs in (a) and (b) are cospectral with respect to traditional matrix representations, but the corresponding $\omega$ spectra in (d) and (e) are clearly distinct for intermediate coherence $\omega =1/2$. The eigenvalues of the individual graphs (marked by filled red circles and open blue circles) are distributed symmetrically about the real axis (dashed line). The pair of graphs in (c) is $L$-cospectral but distinguishable by the $\omega$ spectrum even in the classical regime $\omega =0$.

Figure 3

(a) The distance $\delta$ between $\omega$ spectra depending on the coherence $\omega$ for the pairs of graphs in Fig. 2. For pairs (a) and (b), the distance $\delta$ is peaked for intermediate coherence $\omega$, whereas $\delta =0$ in the classical and fully coherent limits. For the $L$-cospectral pair (c), the distance $\delta$ (rescaled) is always nonzero, even in the classical limit $\omega =0$. (b) Pairs of graphs categorized into classes according to distinguishability with respect to different spectra. The class of pairs distinguishable by $\omega$ spectra includes the classes defined by $A$ and $L$ spectra and additional pairs not contained in these classes.