Algebraic Graph Theory-Martin Štefaňák

Title: Recurrence of unitary and stochastic quantum walks

Abstract: Recurrence means a return of the dynamical system to its initial state. Classical result of Polya [1] from 1920’s shows that a random walk on a line and a 2D grid returns to the origin with certainty, while it is transient on higher-dimensional lattices. For quantum walks, detection of recurrence requires partial measurement after each step, yielding a conditional quantum dynamic. We review the method to study quantum recurrence based on generating functions [2], focusing on the quantum walk on a line. Combination of measurement induced effects and faster spreading implies that a quantum walk on a line can escape to infinity without ever returning to the origin. Finally, we present a recent extension of the study of recurrence to quantum stochastic walks [3], which interpolates between quantum and classical walk dynamics [4]. Surprisingly, we find that introducing classical randomness can reduce the recurrence probability --- despite the fact that the classical random walk returns with certainty --- and we identify the conditions under which this intriguing phenomenon occurs.