We study discrete-time quantum walks on a half line by means of spectral analysis. Cantero et al. showed that the CMV matrix, which gives a recurrence relation for the orthogonal Laurent polynomials on the unit circle, expresses the dynamics of the quantum walk. Using the CGMV method introduced by them, the name is taken from their initials, we obtain the spectral measure for the quantum walk. As a corollary, we give another proof for localization of the quantum walk on homogeneous trees shown by Chisaki et al.
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] [ - 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.
Given random walk on a graph, the corresponding discrete-time quantum walk can be constructed using the method proposed by Szegedy. On the other hand, given a partition of the set of states of a Markov chain, one can study the corresponding aggregated process. We extend the aggregation technique to the level of quantum Markov chains. We provide conditions under which application of these two operations - Szegedy's quantization and aggregation - give the same result. These consist of the strong lumpability of the underlying Markov chain supplemented by nonlinear relations, generalizing Kolmogorov's cycle condition, that account for the coefficients of both the original and the aggregated transition matrices. In particular, we show that the conditions are satisfied in the case of the random walk on graphs equipped with equitable partitions. We present several examples, which include the classical/quantum walks on Platonic solids. We discuss also relation of discrete-time classical/quantum walks on N-dimensional hypercube and the Ehrenfests urn model with N particles. We apply our technique for of discrete-time walks on Cayley graphs of free groups. We also compare our results with those obtained using Cantero-Moral-Velazquez uniformization of unitary matrices.