Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Contemporary mathematics - American Mathematical Society

Quantum walks and CMV matrices

F. Alberto Grünbaum

Published Jan 1, 2012• 0 citations
Publisher

Abstract

I give a very brief account of my encounter with the topics alluded to in the title. The basic idea is that by using CMV matrices one can associate a quantum walk (QW) on the non-negative integers to any probability measure on the unit circle. This development has been a joint effort with my friends M. J. Cantero, L. Velazquez and L. Moral. It is clear that this would not have happened if it were not for the enthusiasm and motivation provided by my friend Paco Marcellan. Certain aspects of this work have been described in a joint paper with Luis Velazquez, which the reader may want to consult. I include here a few points that were not discussed there.

DOI
10.1090/conm/578/11485

Related papers

The Quantum Walk of F. Riesz

F. Alberto Grünbaum, L. Velázquez

We exhibit a way to associate a quantum walk (QW) on the non-negative integers to any probability measure on the unit circle. This forces us to consider one step transitions that are not traditionally allowed. We illustrate this in the case of a very interesting measure, originally proposed by F. Riesz for a different purpose.

arXiv:1111.6630•Cambridge University Press eBooks•Nov 15, 2012•8 citations

Matrix‐valued Szegő polynomials and quantum random walks

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.

arXiv:0901.2244•Communications on Pure and Applied Mathematics•Dec 29, 2009•105 citations

Spectral analysis of discrete-time quantum walks in the quarter plane

Clement Boateng Ampadu

Using the Cantero-Grunbaum-Moral-Velazquez (CGMV) method, we obtain the spectral measure for the quantum walk.

arXiv:1109.3507•Sep 15, 2011•1 citation

Limit distribution of a quantum walk driven by a CMV matrix

Takuya Machida

Quantum walks with CMV matrices, five-diagonal unitary matrices, started to be studied in 2003 [1]. The spectral analysis for CMV matrices told us that the quantum walks could localize in distribution depending on the Verblunsky parameters of the matrices. In this paper, we work on a quantum walk whose system is manipulated by a CMV matrix with homogeneous Vervlunsky parameters, and present long-time limit distributions. One can understand from the theory that the quantum walk does not localize and how it approximately distributes after the long-time evolution has been executed on the walk.

•Mar 17, 2019•0 citations

On aggregation-quantization permutability problem for discrete-time Markov chains

Adam Doliwa, Artur Siemaszko, Adam Zalewski

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.

quant-pharXiv:2603.14269•Mar 17, 2026•0 citations

Spectral quantization of discrete random walks on half-line and orthogonal polynomials on the unit circle

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

arXiv:2306.12265•Quantum Information Processing•Nov 25, 2024•1 citation
I give a very brief account of my encounter with the topics alluded to in the title. The basic idea is that by using CMV matrices one can associate a quantum walk (QW) on the non-negative integers to any probability measure on the unit circle. This development has been a joint effort with my friends M. J. Cantero, L. Velazquez and L. Moral. It is clear that this would not have happened if it were not for the enthusiasm and motivation provided by my friend Paco Marcellan. Certain aspects of this work have been described in a joint paper with Luis Velazquez, which the reader may want to consult. I include here a few points that were not discussed there.
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.
Quantum walks with CMV matrices, five-diagonal unitary matrices, started to be studied in 2003 [1]. The spectral analysis for CMV matrices told us that the quantum walks could localize in distribution depending on the Verblunsky parameters of the matrices. In this paper, we work on a quantum walk whose system is manipulated by a CMV matrix with homogeneous Vervlunsky parameters, and present long-time limit distributions. One can understand from the theory that the quantum walk does not localize and how it approximately distributes after the long-time evolution has been executed on the walk.
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 NNN-dimensional hypercube and the Ehrenfests urn model with NNN 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.
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][−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.