  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].
