Quantum Computation and Information Seminar 

03/11/2011, 15:30 — 16:30 — Room P3.10, Mathematics Building
Tamas Kiss, Hungarian Academy of Sciences

Recurrence in quantum walks

The Polya number characterizes the recurrence of a random walk. We apply the generalization of this concept to quantum walks which is based on a specific measurement scheme. The Polya number of a quantum walk depends, in general, on the choice of the coin and the initial coin state, in contrast to classical random walks where the lattice dimension uniquely determines it. We analyze several examples to depict the variety of possible recurrence properties. For 2D square lattices the Grover walk exhibits localization and thus is recurrent, except for a particular initial state for which the walk is transient. We generalize the Grover walk to show that one can construct in arbitrary dimensions a quantum walk which is recurrent. This is in great contrast with classical walks which are recurrent only for the dimensions $d=1,2$. The 2D Fourier walk is recurrent except for a two-dimensional subspace of the initial states. In order to better understand the role of dimensionality in the recurrence properties, one can consider a triangular lattice. The three-state Grover walk on a two-dimensional triangular lattice does not lead to trapping (localization) or recurrence to the origin, in sharp contrast to the corresponding walk on the two-dimensional square lattice. In general, on a triangular lattice only a special subclass of coin operators can lead to recurrence, and there are no coins that would lead to localization. The definition for the Polya number can be extended to continuous-time quantum walks, as well. For the timing of the measurements, a Poisson process as well as regular timing are discussed. We examine various graphs, including the ring, the line, the higher-dimensional integer lattices, and a number of other graphs, and we calculate their Polya number. We find that the speed of decay for the probability at the origin is the key for recurrence.