Matrix valued Szego polynomials and quantum random walks

2. Classical random walk on the integers, three looks at a classical subject

• For classical nearest-neighbour walks, tridiagonal transition matrices can be symmetrized, linking them to Jacobi matrices and orthogonal polynomials on the real line.The paper positions this spectral framework as the classical analogue for its quantum analysis.Source: §1 · p. 3

1. Introduction and contents of the paper

• Nearest-neighbour QRWs without internal degrees of freedom split into trivial walks, motivating a spin-1/2 internal degree of freedom for nontrivial local dynamics.The paper’s framework uses CMV matrices, whose unitarity and block-tridiagonal form match the nearest-neighbour setting; it applies to a large class of walks on the integers.Source: §1 · pp. 4–5
• The paper presents matrix-valued Laurent orthogonal polynomials associated with CMV matrices as a new tool for QRWs, whose use of scalar or matrix orthogonal polynomials had not been established.The approach is intended to handle distinct coins, beyond methods the paper describes as more standard.Source: §1 · pp. 5–6
• On the non-negative integers, a constant coin’s phases influence results, and its orthogonality measure generally has a discrete mass; on all integers, the measure has no mass point and phases play no role.The paper also uses these cases to compare walks on the non-negative integers and on the integers.Source: §1 · p. 6
• The paper applies its methods to large-time asymptotics and recurrence, where it finds marked differences between classical and quantum walks.It presents recurrence analysis as an example of the method’s benefits.Source: §1 · p. 6

2. Classical random walk on the integers, three looks at a classical subject

• Matrix-valued orthogonal polynomials yield the Karlin–McGregor formula for block transition-matrix powers, isolating time dependence in x^n and enabling large-time analysis.When the polynomials and orthogonality measure are available, the formula computes transitions using only the top j rows of the matrix.Source: §2 · p. 9
• The transition probability matrix changes from a scalar, doubly infinite tridiagonal matrix, with p on the i, i + 1 diagonal and q on the i + 1, i diagonal, to a semi-infinite block-tridiagonal matrix with 2 × 2 blocks.Source: §2 · pp. 9–10
• The appropriate matrix measure was already given by Karlin and McGregor, while the corresponding matrix-valued orthogonal polynomials and block tridiagonal matrix can be supplied.The paper notes that these corresponding objects are not given in the cited original paper.Source: §2 · p. 10
• The orthogonal polynomials in this example can be expressed using Chebyshev polynomials of the second kind, which satisfy U_{n+1}(x) + U_{n-1}(x) = 2xU_n(x).The supplied recurrence specifies U_{-1}(x) = 0 and U_0(x) = 1.Source: §2 · p. 10

Laurent polynomials

• Orthonormal Laurent polynomials provide a basis in which multiplication by z is represented by a CMV matrix, with recurrences determining the polynomials.The scalar construction starts from orthonormalizing an alternating sequence of positive and negative powers of z.Source: §3 · pp. 11, 16

CMV matrices

• CMV matrices are canonical five-diagonal representations of unitary operators and admit a tridiagonal factorization into two unitary block-diagonal factors.The section also states that no four-diagonal representation exists for every unitary operator.Source: §3 · pp. 12–13

Szegő polynomials

• Verblunsky parameters determine the Szegő-polynomial recurrence and bijectively characterize probability measures supported on an infinite subset of the unit circle.For measures with known Szegő polynomials, the parameters and corresponding CMV matrix can be obtained explicitly.Source: §3 · pp. 12–13

Spectral measure

• The support of the orthogonality measure matches the CMV spectrum, and its mass points are simple eigenvalues with masses determined by eigenvector norms.A point on the unit circle is a mass point exactly when its associated Laurent-polynomial vector is square-integrable.Source: §3 · p. 13

Matrix-valued extension

• The Carathéodory function recovers the measure, while its Taylor coefficients give the measure's moments; the construction extends to matrix-valued measures and block CMV matrices.For matrix-valued measures, the Szegő recurrences mix right and left polynomials.Source: §3 · pp. 14–17

Quantum random walks

• The aim is an explicit expression for entries of U^n, giving a Karlin–McGregor formula for quantum-walk transition amplitudes.The walks considered have spin-1/2 pure states and evolve through a unitary one-step transition matrix.Source: §4 · p. 17
• The requested formula targets the entries of the unitary's powers for walks on either the non-negative integers or all integers.The transition amplitudes are indexed by pairs of pure states.Source: §4 · p. 17
• For nearest-neighbor QRWs, a simple change of basis phases yields CMV form, whose Szegő polynomials and measures provide the functions needed for the formula.Reducing an arbitrary infinite unitary matrix to CMV form can be difficult.Source: §4 · p. 17

A very elementary example

• On the half-line, spin-up states move right, spin-down states away from the origin move left, and a spin-down state at the origin reverses and stays there for one step.On the following step, that state moves to site 1.Source: §5 · p. 17
• An integral involving the Laurent-polynomial components gives the amplitude for moving between pure states in any positive or negative number of time steps.For this elementary walk, the integral evaluates to either 0 or 1 and gives the stated amplitudes.Source: §5 · p. 18
• The example uses the simplest CMV matrix, with null Verblunsky parameters and orthonormal Laurent polynomials for Lebesgue measure on the unit circle.The polynomials satisfy the identity Ux(z) = zx(z).Source: §5 · p. 18

6. Another example

• The up-spin states move one site right and the down-spin states one site left, so the two evolutions can be treated separately.The walk can also be folded by relabelling the integer sites, converting each doubly infinite matrix into a semi-infinite one.Source: §6 · pp. 19–20
• After folding, the integer-line transition matrix becomes the semi-infinite matrix from the preceding example.The down-spin evolution requires its own folding.Source: §6 · p. 20
• The initial transition matrix is a doubly infinite CMV matrix with null Verblunsky parameters.This example illustrates a simple instance of the CMV structure used for more general walks.Source: §6 · p. 20

7. A more general case: QRWs with distinct coins

• The walk allows spin-up states to move right and remain up or move left and flip, while spin-down states move right and flip or move left and remain down.Unlike the preceding example, the up- and down-spin states do not decouple.Source: §7 · pp. 20, 23
• The original transition matrix is exactly CMV only when every coin has positive diagonal entries.A simple change of basis phases can then put the evolution into CMV form.Source: §7 · p. 22
• Reordering the states and changing basis phases transforms the evolution into a 2 × 2-block CMV matrix.The corresponding coins are assumed nontrivial; if a coin is trivial, the walk splits into simpler independent evolutions in the pure-state basis.Source: §7 · pp. 22–23
• Arbitrary nontrivial coins on the integer line can be represented by doubly infinite CMV matrices or 2 × 2-block CMV matrices, with vanishing odd Verblunsky parameters.The resulting structure supports a Karlin–McGregor formula in terms of matrix-valued Szegő polynomials.Source: §7 · p. 23
• The associated orthonormal Laurent polynomials yield a Karlin–McGregor formula whose matrix entries are transition amplitudes after n steps.The formula connects the unitary evolution to the polynomials and their orthogonality measure.Source: §7 · pp. 23–24

8. QRWs with a constant coin

• The split into two half-line walks provides the reduction used to obtain a Karlin–McGregor formula for the integer-line walk.The formula follows once the associated scalar Laurent polynomials and measures are obtained.Source: §8 · p. 26
• A constant-coin walk on the integers splits into two constant-coin walks on the non-negative integers in a basis of mixed states.The split is not initially apparent in the pure-state basis.Source: §8 · p. 27
• The block CMV matrix for an integer-line constant coin depends only on the moduli of its entries, so the coin phases do not essentially affect this walk.Unitarity determines the other entry moduli once one is specified.Source: §8 · p. 27
• The Hadamard walk is a canonical example of an unbiased integer-line walk with a constant coin.An unbiased walk has equiprobable allowed transitions.Source: §8 · pp. 24, 27

9. QRWs with a constant coin on the non-negative integers

• The constant-coin walk on the non-negative integers has a Karlin–McGregor formula based on its associated measure and orthonormal Laurent polynomials.The formula also applies to arbitrary distinct coins on the non-negative integers.Source: §9 · p. 28
• The even Verblunsky parameters can carry arbitrary phases from the coin, unlike those in the integer-line reduction.The paper therefore expects a stronger phase influence for constant coins on the non-negative integers.Source: §9 · p. 28
• Only a appears in the integral for the transition formula; ϑ and the individual coin phases contribute only a factor outside it.This separates the integral’s parameter dependence from those phase factors.Source: §9 · p. 29
• The measure has a continuous weight on two symmetric arcs and generally also a Dirac mass outside those arcs.The mass point is absent exactly when a is imaginary, which occurs when the coin is symmetric.Source: §9 · pp. 29–30
• Coin phases affect the half-line walk: the weight’s form and the Dirac mass’s location and size depend on the phase of a.The weight’s location depends only on |a|.Source: §9 · p. 30

• The matrix ingredients of the KMcG formula are given in terms of scalar objects for the constant-coin walk.Source: §10 · p. 30
• For a constant coin on the integers, the matrix measure consists exclusively of a continuous matrix weight because the mass point disappears.Source: §10 · p. 30
• The scalar formulas use θ in [η, π − η] ∪ [η − π, −η], with sin η = |a| and η in [0, π/2).Source: §10 · p. 30

• For the equiprobable coin (44), the integer walk has a weight symmetric with respect to the real line, while the non-negative-integer walk has no forbidden site-0 pure-spin transitions for n ≥ 2.Source: §11 · pp. 32, 36
• The non-negative-integer Hadamard measure has a mass point that breaks the full measure's symmetry, unlike its symmetric weight; its Laurent polynomials have real coefficients.Source: §11 · pp. 32–33
• For the Hadamard walk on the integers, same-site pure-spin transitions are forbidden for odd n except n = 1; for even n, probabilities are |cm|2/4 when n = 4m or 4m + 2.Source: §11 · p. 34
• For the Hadamard coin on the non-negative integers, site-0 transition amplitudes match the integer case for even n, while some odd-n transitions remain forbidden.Source: §11 · p. 35
• The absence of forbidden transitions for coin (44) follows from d2 < dn < d1 for n ≥ 3, with |ĉn| decreasing and ĉn alternating in sign for n ≥ 1.Source: §11 · p. 36

• For walks with nontrivial distinct coins, the measure's moments and associated orthonormal Laurent polynomials give n-step amplitudes through the KMcG formula.The authors present these general results to indicate how the method could be used for asymptotic questions, without comparing them with detailed results in the literature.Source: §12 · p. 36
• For a system initially in the spin-up 0-state, the return probability converges to 1/2, although the return amplitude µ_n itself does not converge.Source: §12 · p. 37
• The transition matrix U^n converges weakly to zero exactly when the nth moment tends to zero.Source: §12 · p. 38
• A phase-adjusted U^n has a nonzero weak limit exactly when the phase-adjusted nth moment converges to a nonzero limit and successive phase ratios converge.Source: §12 · p. 38
• Unbiased walks on the integers and the Hadamard walk on the non-negative integers converge weakly to zero, whereas coin (44) on the non-negative integers has a nonvanishing limit after multiplication by i^-n.Source: §12 · p. 39
• For a non-negative-integer walk with a nonzero phase-adjusted weak limit, the measure has a mass point at the limiting phase, and the limit is an orthogonal projection onto its eigenspace.Source: §12 · p. 39

13. Recurrence properties of QRWs

• A state is recurrent exactly when the series of its n-step return probabilities diverges, under the paper’s quantum definition of return.This criterion makes the probability of returning in a given number of steps meaningful despite the effect of measurement on the walk.Source: §13 · p. 43
• Unlike the classical origin criterion, quantum recurrence depends on the Carathéodory function’s behavior over the whole unit circle.The classical criterion depends only on the moments’ generating function at z = 1.Source: §13 · p. 45
• For local states, transience corresponds to an associated Laurent polynomial canceling the Carathéodory function’s non-integrable singularities.On the non-negative integers, all local states are transient if and only if the spin-up state at the origin is transient.Source: §13 · p. 46
• With the Hadamard coin on the non-negative integers, every spin state at site 0 is recurrent, while suitable states mixing sites 0 and 1 can be transient.The associated Laurent polynomial for a transient state must vanish at both singularities.Source: §13 · pp. 46–47
• For the alternate equiprobable coin, the spin-up state at the origin is recurrent, yet transient states also exist at the origin.Its Carathéodory function has one non-integrable singularity, unlike the Hadamard coin’s two.Source: §13 · p. 47
• For a non-symmetric, non-diagonal constant coin on the non-negative integers, the origin has a one-dimensional transient subspace, unlike the symmetric-coin case where every state there is recurrent.The non-symmetric case has one non-removable singularity; the symmetric case has two non-integrable singularities.Source: §13 · p. 48
• On the integers, superpositions confined to two contiguous sites are recurrent, whereas transient states can involve non-contiguous sites.These properties extend beyond the Hadamard walk to non-trivial, non-diagonal constant coins; recurrence properties for two consecutive sites and transient states on non-contiguous sites are identified as new.Source: §13 · pp. 48–49

14. Conclusions

• The paper proposes a QRW analysis inspired by a third classical random-walk method and uses orthonormal Laurent polynomials for asymptotics and Carathéodory functions for recurrence.The approach reproduces known results and provides new ones and methods of analysis.Source: §14 · p. 50
• The method can handle non-translation-invariant walks and richer one-step transition structures, although the examples studied have simpler structure.The authors identify CMV matrices with all Verblunsky parameters non-zero as a future direction.Source: §14 · p. 50
• Quantum recurrence can be more varied than the classical recurrent-or-transient dichotomy for irreducible walks, and remains an area for further investigation.The approach can also be adapted to arbitrary numbers of spin degrees of freedom and regular networks in various dimensions.Source: §14 · p. 50

15. Appendix

• The appendix calculates the measure and orthonormal Laurent polynomials for Verblunsky parameters a, 0, a, 0, …, with |a| < 1.It derives the measure through the Carathéodory function.Source: §15 · pp. 51–52
• The continuous weight is supported on two symmetric arcs centered at ±i, each with angular amplitude 2η.The appendix defines η by sin η = |a|.Source: §15 · p. 53
• A possible mass point lies outside the weight’s support, and it disappears when Rea = 0.Its location is e^(iβ), where sin β = −Ima and the sign of cos β matches the sign of Rea.Source: §15 · pp. 53–54