  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\H{o} map. Our scheme can be applied to arbitrary Karlin and McGregor
random walks and generalizes the so called
Cantero-Gr\"{u}nbaum-Moral-Vel\'{a}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.
