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

arXiv:0901.2244 · Communications on Pure and Applied Mathematics

Matrix‐valued Szegő polynomials and quantum random walks

Maŕıa José Cantero, L. Moral, F. Alberto Grünbaum, L. Velázquez

Published Dec 29, 2009• 105 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1002/cpa.20312

Related papers

Krawtchouk matrices from classical and quantum random walks

Philip Feinsilver, Jerzy Kocik

Krawtchouk's polynomials occur classically as orthogonal polynomials with respect to the binomial distribution. They may be also expressed in the form of matrices, that emerge as arrays of the values that the polynomials take. The algebraic properties of these matrices provide a very interesting and accessible example in the approach to probability theory known as quantum probability. First it is noted how the Krawtchouk matrices are connected to the classical symmetric Bernoulli random walk. And we show how to derive Krawtchouk matrices in the quantum probability context via tensor powers of the elementary Hadamard matrix. Then connections with the classical situation are shown by calculating expectation values in the quantum case.

arXiv:quant-ph/0702173•Contemporary mathematics - American Mathematical Society•Jan 1, 2001•24 citations

Localization of quantum walks via the CGMV method

Norio Konno, Etsuo Segawa

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.

arXiv:1008.5109•Quantum Information and Computation•May 1, 2011•28 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

ON ALGEBRAIC AND QUANTUM RANDOM WALKS

Demosthenes Ellinas

Algebraic random walks (ARW) and quantum mechanical random walks (QRW) are investigated and related. Based on minimal data provided by the underlying bialgebras of functions defined on e. g the real line R, the abelian finite group Z_N, and the canonical Heisenberg-Weyl algebra hw, and by introducing appropriate functionals on those algebras, examples of ARWs are constructed. These walks involve short and long range transition probabilities as in the case of R walk, bistochastic matrices as for the case of Z_N walk, or coherent state vectors as in the case of hw walk. The increase of classical entropy due to majorization order of those ARWs is shown, and further their corresponding evolution equations are obtained. Especially for the case of hw ARW, the diffusion limit of evolution equation leads to a quantum master equation for the density matrix of a boson system interacting with a bath of quantum oscillators prepared in squeezed vacuum state. A number of generalizations to other types of ARWs and some open problems are also stated. Next, QRWs are briefly presented together with some of their distinctive properties, such as their enhanced diffusion rates, and their behavior in respect to the relation of majorization to quantum entropy. Finally, the relation of ARWs to QRWs is investigated in terms of the theorem of unitary extension of completely positive trace preserving (CPTP) evolution maps by means of auxiliary vector spaces. It is applied to extend the CPTP step evolution map of a ARW for a quantum walker system into a unitary step evolution map for an associated QRW of a walker+quantum coin system. Examples and extensions are provided.

arXiv:quant-ph/0510128•Quantum Probability and Infinite Dimensional Analysis•Jan 1, 2005•7 citations

Quantum Random Walks on the integer lattice via generating functions

Andrew Bressler

We analyze several families of one and two-dimensional nearest neighbor Quantum Random Walks. Using a multivariate generating function analysis we give a simplified proof of a known phenomenon for two-chirality walks on the line, namely that the walk has linear speed rather than the diffusive behavior observed in classical random walks. We also demonstrate Airy phenomena between the regions of polynomial and exponential decay. For a three-chirality walk on the line we demonstrate similar behavior, with the addition of a bound state, in which the probability of finding the particle at the origin does not go to zero with time. For each of these walks on the line we obtain exact formulae for the leading asymptotic term of the wave function and the location probabilities. Analyzing two-dimensional walks we again find a region of polynomial decay which grows linearly with time. The limiting shape of the feasible region is, however, quite different. The limit region turns out to be an algebraic set, which we characterize as the rational image of a compact algebraic variety. We also compute the probability profile within the limit region, which is essentially a negative power of the Gaussian curvature of the same algebraic variety. We close with preliminary work concerning walks in higher dimensions.

•Jan 1, 2009•1 citation

Birth and death processes and quantum spin chains

F. Alberto Grünbaum, Luc Vinet, Alexei S. Zhedanov

This paper underscores the intimate connection between the quantum walks generated by certain semi-infinite spin chain Hamiltonians and classical birth and death processes. It is observed that transition amplitudes between single excitation states of the spin chains have an expression in terms of orthogonal polynomials which is analogous to the Karlin-McGregor representation formula of the transition probability functions for classes of birth and death processes. As an application, we present a characterization of spin systems for which the probability to return to the point of origin at some time is 1 or almost 1.

arXiv:1205.4689•Journal of Mathematical Physics•Jun 1, 2013•14 citations
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.
Krawtchouk's polynomials occur classically as orthogonal polynomials with respect to the binomial distribution. They may be also expressed in the form of matrices, that emerge as arrays of the values that the polynomials take. The algebraic properties of these matrices provide a very interesting and accessible example in the approach to probability theory known as quantum probability. First it is noted how the Krawtchouk matrices are connected to the classical symmetric Bernoulli random walk. And we show how to derive Krawtchouk matrices in the quantum probability context via tensor powers of the elementary Hadamard matrix. Then connections with the classical situation are shown by calculating expectation values in the quantum case.
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][−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.
Algebraic random walks (ARW) and quantum mechanical random walks (QRW) are investigated and related. Based on minimal data provided by the underlying bialgebras of functions defined on e. g the real line R, the abelian finite group Z_N, and the canonical Heisenberg-Weyl algebra hw, and by introducing appropriate functionals on those algebras, examples of ARWs are constructed. These walks involve short and long range transition probabilities as in the case of R walk, bistochastic matrices as for the case of Z_N walk, or coherent state vectors as in the case of hw walk. The increase of classical entropy due to majorization order of those ARWs is shown, and further their corresponding evolution equations are obtained. Especially for the case of hw ARW, the diffusion limit of evolution equation leads to a quantum master equation for the density matrix of a boson system interacting with a bath of quantum oscillators prepared in squeezed vacuum state. A number of generalizations to other types of ARWs and some open problems are also stated. Next, QRWs are briefly presented together with some of their distinctive properties, such as their enhanced diffusion rates, and their behavior in respect to the relation of majorization to quantum entropy. Finally, the relation of ARWs to QRWs is investigated in terms of the theorem of unitary extension of completely positive trace preserving (CPTP) evolution maps by means of auxiliary vector spaces. It is applied to extend the CPTP step evolution map of a ARW for a quantum walker system into a unitary step evolution map for an associated QRW of a walker+quantum coin system. Examples and extensions are provided.
We analyze several families of one and two-dimensional nearest neighbor Quantum Random Walks. Using a multivariate generating function analysis we give a simplified proof of a known phenomenon for two-chirality walks on the line, namely that the walk has linear speed rather than the diffusive behavior observed in classical random walks. We also demonstrate Airy phenomena between the regions of polynomial and exponential decay. For a three-chirality walk on the line we demonstrate similar behavior, with the addition of a bound state, in which the probability of finding the particle at the origin does not go to zero with time. For each of these walks on the line we obtain exact formulae for the leading asymptotic term of the wave function and the location probabilities. Analyzing two-dimensional walks we again find a region of polynomial decay which grows linearly with time. The limiting shape of the feasible region is, however, quite different. The limit region turns out to be an algebraic set, which we characterize as the rational image of a compact algebraic variety. We also compute the probability profile within the limit region, which is essentially a negative power of the Gaussian curvature of the same algebraic variety. We close with preliminary work concerning walks in higher dimensions.
This paper underscores the intimate connection between the quantum walks generated by certain semi-infinite spin chain Hamiltonians and classical birth and death processes. It is observed that transition amplitudes between single excitation states of the spin chains have an expression in terms of orthogonal polynomials which is analogous to the Karlin-McGregor representation formula of the transition probability functions for classes of birth and death processes. As an application, we present a characterization of spin systems for which the probability to return to the point of origin at some time is 1 or almost 1.