Quantum random walk polynomial and quantum random walk measure

Luigi Accardi, G. S. Watson

Adam Doliwa, Artur Siemaszko

Abstract We define quantization scheme for discrete-time random walks on the half-line consistent with Szegedy's quantization of finite Markov chains. Motivated by the Karlin and McGregor description of discrete-time random walks in terms of polynomials orthogonal with respect to a measure with support in the segment [-1,1], we represent the unitary evolution operator of the quantum walk in terms of orthogonal polynomials on the unit circle. We find the relation between transition probabilities of the random walk with the Verblunsky coefficients of the corresponding polynomials of the quantum walk. We show that the both polynomials systems and their measures are connected by the classical Szegö map. Our scheme can be applied to arbitrary Karlin and McGregor random walks and generalizes the so called Cantero--Grünbaum--Moral--Velázquez method. We illustrate our approach on example of random walks related to the Jacobi polynomials. Then we study quantization of random walks with constant transition probabilities where the corresponding polynomials on the unit circle have two-periodic real Verblunsky coefficients. We present geometric construction of the spectrum of such polynomials (in the general complex case) which generalizes the known construction for the Geronimus polynomials. In the Appendix we present the explicit form, in terms of Chebyshev polynomials of the second kind, of polynomials orthogonal on the unit circle and polynomials orthogonal on the real line with coefficients of arbitrary period. 2010 Mathematics Subject Classification. 81P68, 05C81, 42C05, 94A11.

Swarnadeep Majumder, Austen Couvertier

Maŕıa José Cantero, F. Alberto Grünbaum, Moral, L. +1 more

We consider quantum random walks (QRW) on the integers, a subject that has been considered in the last few years in the framework of quantum computation. We show how the theory of CMV matrices gives a natural tool to study these processes and to give results that are analogous to those that Karlin and McGregor developed to study (classical) birth-and-death processes using orthogonal polynomials on the real line. In perfect analogy with the classical case the study of QRWs on the set of non-negative integers can be handled using scalar valued (Laurent) polynomials and a scalar valued measure on the circle. In the case of classical or quantum random walks on the integers one needs to allow for matrix valued versions of these notions. We show how our tools yield results in the well known case of the Hadamard walk, but we go beyond this translation invariant model to analyze examples that are hard to analyze using other methods. More precisely we consider QRWs on the set of non- negative integers. The analysis of these cases leads to phenomena that are absent in the case of QRWs on the integers even if one restricts oneself to a constant coin. This is illustrated here by studying recurrence properties of the walk, but the same method can be used for other purposes. The presentation here aims at being selfcontained, but we re- frain from trying to give an introduction to quantum random walks, a subject well surveyed in the literature we quote. For two excellent reviews, see [1, 18]. See also the recent notes [19].

Yuliy M. Baryshnikov, Wil Brady, Andrew Bressler +1 more

Maŕıa José Cantero, L. Moral, F. Alberto Grünbaum +1 more

Abstract We consider quantum random walks (QRW) on the integers, a subject that has been considered in the last few years in the framework of quantum computation. We show how the theory of CMV matrices gives a natural tool to study these processes and to give results that are analogous to those that Karlin and McGregor developed to study (classical) birth‐and‐death processes using orthogonal polynomials on the real line. In perfect analogy with the classical case, the study of QRWs on the set of nonnegative integers can be handled using scalar‐valued (Laurent) polynomials and a scalar‐valued measure on the circle. In the case of classical or quantum random walks on the integers, one needs to allow for matrix‐valued versions of these notions. We show how our tools yield results in the well‐known case of the Hadamard walk, but we go beyond this translation‐invariant model to analyze examples that are hard to analyze using other methods. More precisely, we consider QRWs on the set of nonnegative integers. The analysis of these cases leads to phenomena that are absent in the case of QRWs on the integers even if one restricts oneself to a constant coin. This is illustrated here by studying recurrence properties of the walk, but the same method can be used for other purposes. The presentation here aims at being self‐contained, but we refrain from trying to give an introduction to quantum random walks, a subject well surveyed in the literature we quote. For two excellent reviews, see [1, 9]. See also the recent notes [20]. © 2009 Wiley Periodicals, Inc.