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], 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. 2010 Mathematics Subject Classification. 81P68, 05C81, 42C05, 94A11.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], 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. 2010 Mathematics Subject Classification. 81P68, 05C81, 42C05, 94A11.

arXiv:2306.12265Quantum Information ProcessingNov 25, 20240 citations

Quantum algorithms for orthogonal polynomial transforms

Anupam Prakash, Shree Hari Sureshbabu, Dylan Herman +1 more

A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states $\sum_k α_{k} \ket{k}$ coherently to a basis of normalized univariate polynomials orthogonal with respect to a probability measure $μ(x)$ . We provide new discrete and continuous QOPTs for polynomial families in the Askey scheme extending the results for the quantum Hermite transform (Jain et al., STOC'26). Our efficient QOPT algorithms require time $O(\text{polylog}(N, 1/ε))$ , where $N$ is the grid size and $ε$ is the error, for the discrete Charlier, Meixner and Krawtchouk transforms and for the integer-order Laguerre transform in the continuous setting. The efficient QOPTs are obtained by uncovering the links between Askey scheme polynomials and Gaussian quantum optical gates and developing a compilation framework for $SU(2)$ and $SU(1,1)$ optical gates on Cartesian grids extending the framework developed by Iyer et al. (arXiv:2602.15180). Further, we reduce the continuous Jacobi transform to the discrete Hahn transform and provide an $O\!\left(N\operatorname{polylog}((N+α+β+1)/ε)\right)$ -time Hahn transform, a quadratic speedup over the naive implementation. This is based on a more efficient compilation of the Clebsch--Gordan transform for coupling $\mathrm{SU}(2)$ representations with spins $(j_{1}, j_{2})$ . Finally, we develop a new framework for Laguerre transforms for all orders $ν>0$ by fast-forwarding the corresponding radial oscillator using a 3-term chirp decomposition and an efficient algorithm for the Quantum Hankel Transform on a logarithmic grid.A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states $\sum_k α_{k} \ket{k}$ coherently to a basis of normalized univariate polynomials orthogonal with respect to a probability measure $μ(x)$. We provide new discrete and continuous QOPTs for polynomial families in the Askey scheme extending the results for the quantum Hermite transform (Jain et al., STOC'26). Our efficient QOPT algorithms require time $O(\text{polylog}(N, 1/ε))$, where $N$ is the grid size and $ε$ is the error, for the discrete Charlier, Meixner and Krawtchouk transforms and for the integer-order Laguerre transform in the continuous setting. The efficient QOPTs are obtained by uncovering the links between Askey scheme polynomials and Gaussian quantum optical gates and developing a compilation framework for $SU(2)$ and $SU(1,1)$ optical gates on Cartesian grids extending the framework developed by Iyer et al. (arXiv:2602.15180). Further, we reduce the continuous Jacobi transform to the discrete Hahn transform and provide an $O\!\left(N\operatorname{polylog}((N+α+β+1)/ε)\right)$-time Hahn transform, a quadratic speedup over the naive implementation. This is based on a more efficient compilation of the Clebsch--Gordan transform for coupling $\mathrm{SU}(2)$ representations with spins $(j_{1}, j_{2})$. Finally, we develop a new framework for Laguerre transforms for all orders $ν>0$ by fast-forwarding the corresponding radial oscillator using a 3-term chirp decomposition and an efficient algorithm for the Quantum Hankel Transform on a logarithmic grid.

quant-pharXiv:2610.03581Oct 5, 20260 citations

ON QUANTUM PROBABILITY

Igor Evgenievich Pris

Философия наукиJan 1, 20223 citations

Quantum probability theory

Schleissinger, Sebastian

Mathematical surveys and monographsSep 22, 20250 citations

Quantum probability theory

Miklós Rédei, Stephen J. Summers

arXiv:quant-ph/0601158Studies in History and Philosophy of Science Part B Studies in History and Philosophy of Modern PhysicsJun 1, 2007110 citations

Krawtchouk-Griffiths systems I: matrix approach

Philip Feinsilver

We call Krawtchouk-Griffiths systems, or KG-systems, systems of multivariate polynomials orthogonal with respect to corresponding multinomial distributions.The original Krawtchouk polynomials are orthogonal with respect to a binomial distribution.Our approach is to work directly with matrices comprising the values of the polynomials at points of a discrete grid based on the possible counting values of the underlying multinomial distribution.The starting point for the construction of a KG-system is a generating matrix satisfying the K-condition, orthogonality with respect to the basic probability distribution associated to an individual step of the multinomial process.The variables of the polynomials corresponding to matrices may be interpreted as quantum observables in the real case, or quantum variables in the complex case.The structure of the recurrence relations for the orthogonal polynomials is presented with multiplication operators as the matrices corresponding to the quantum variables.An interesting feature is that the associated random walks correspond to the Lie algebra of the representation of symmetric tensor powers of matrices.We call Krawtchouk-Griffiths systems, or KG-systems, systems of multivariate polynomials orthogonal with respect to corresponding multinomial distributions.The original Krawtchouk polynomials are orthogonal with respect to a binomial distribution.Our approach is to work directly with matrices comprising the values of the polynomials at points of a discrete grid based on the possible counting values of the underlying multinomial distribution.The starting point for the construction of a KG-system is a generating matrix satisfying the K-condition, orthogonality with respect to the basic probability distribution associated to an individual step of the multinomial process.The variables of the polynomials corresponding to matrices may be interpreted as quantum observables in the real case, or quantum variables in the complex case.The structure of the recurrence relations for the orthogonal polynomials is presented with multiplication operators as the matrices corresponding to the quantum variables.An interesting feature is that the associated random walks correspond to the Lie algebra of the representation of symmetric tensor powers of matrices.

arXiv:1611.06991Communications on Stochastic AnalysisSep 1, 20164 citations

A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states

\sum_k α_{k} \ket{k}

coherently to a basis of normalized univariate polynomials orthogonal with respect to a probability measure

μ(x)

. We provide new discrete and continuous QOPTs for polynomial families in the Askey scheme extending the results for the quantum Hermite transform (Jain et al., STOC'26). Our efficient QOPT algorithms require time

O(\text{polylog}(N, 1/ε))

, where

N

is the grid size and

ε

is the error, for the discrete Charlier, Meixner and Krawtchouk transforms and for the integer-order Laguerre transform in the continuous setting. The efficient QOPTs are obtained by uncovering the links between Askey scheme polynomials and Gaussian quantum optical gates and developing a compilation framework for

SU(2)

and

SU(1,1)

optical gates on Cartesian grids extending the framework developed by Iyer et al. (arXiv:2602.15180). Further, we reduce the continuous Jacobi transform to the discrete Hahn transform and provide an

O\!\left(N\operatorname{polylog}((N+α+β+1)/ε)\right)

-time Hahn transform, a quadratic speedup over the naive implementation. This is based on a more efficient compilation of the Clebsch--Gordan transform for coupling

\mathrm{SU}(2)

representations with spins

(j_{1}, j_{2})

. Finally, we develop a new framework for Laguerre transforms for all orders

ν>0

by fast-forwarding the corresponding radial oscillator using a 3-term chirp decomposition and an efficient algorithm for the Quantum Hankel Transform on a logarithmic grid.