Localization and its consequences for quantum walk algorithms and quantum communication

The exponential speedup of quantum walks on certain graphs, relative to classical particles diffusing on the same graph, is a striking observation. It has suggested the possibility of new fast quantum algorithms. We point out here that quantum mechanics can also lead, through the phenomenon of localization, to exponential suppression of motion on these graphs (even in the absence of decoherence). In fact, for physical embodiments of graphs, this will be the generic behavior. It also has implications for proposals for using spin networks, including spin chains, as quantum communication channels.

Figure 1

The graph ${\mathcal{G}}_4$ [6].

Figure 2

Elements of the Hamiltonian $H∕\gamma$ for ${\mathcal{G}}_4$ when reduced to a walk on a line [6].

Figure 3

(Color online) Propagation within the left side of ${\mathcal{G}}_{1000}$ at times $t$ according to (top) the perfect Hamiltonian Eq. (3), and the disordered Hamiltonian Eq. (6) with disorder $\delta =\left(\text{middle}\right)$ 0.03 and (bottom) 0.06. The solid black lines correspond to $t=50$, the dotted red lines to $t=150$, the blue dash-dotted lines to $t=250$, and the green dashed lines to $t=350$.