Symmetric quantum walks on Hamming graphs
and their limit distributions · 2025
Read Symmetric quantum walks on Hamming graphs by and their limit distributions (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-26243.txt.
Introduction
Robert Griffiths and Shuhei Mano study symmetric quantum walks on Hamming graphs, networks whose vertices are strings and whose edges reflect distance between them. In their walk models, transition behavior depends on that vertex distance. The familiar quantum walk on the hypercube appears as a special case.
The unitary operator's eigenvalues turn out to be zeros of certain self-reciprocal polynomials. Using the association scheme structure, the authors build a spectral representation of the walk's wave vector. They extend the Grover coin to reflections within invariant subspaces of the Terwilliger algebra. Limit distributions for several of these walks are worked out, describing where the walker ends up after many steps.
Catalog record
| CREATOR | and their limit distributions |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-26243
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Symmetric quantum walks on Hamming graphs and their limit distributions Abstract Abstract. We study a class of symmetric quantum walks on Hamming graphs, where the distance between vertices specifies the transition probability. A special model is the simple quantum walk on the hypercube, which has been discussed in the literature. Eigenvalues of the unitary operator of the quantum walks are zeros of certain self-reciprocal polynomials. We obtain a spectral representation of the wave vector, where our systematic treatment relies on the coin space isomorphic to the state space and the commutative association scheme. The limit distributions of several quantum walks are obtained. Key Words and Phrases. association scheme, hypercube, random walk, self-reciprocal polynomial, spectral representation 2020 Mathematics Subject Classification Numbers. 05E30, 33C45, 60B15, 60K40 1 Introduction Random walks on graphs are a typical research topic for finite-state Markov chains. In particular, random walks on cycles and on the hypercube are classical topics, which can be viewed as random walks with the elements of a finite group as their state space. See [ 6 ] and references therein. A simple random walk on the hypercube is a finite Markov chain defined on a state space where each vertex on the hypercube is binary-valued, with transitions occurring only between adjacent vertices. If the dimension of the hypercube is d , the state space can be viewed as a d -digit binary number, with transitions occurring only between numbers that differ by only one digit. In this study, we first discuss more general random walks on finite sets. There are two directions of extension related to this study: one extends the transition probability, allowing transitions to occur between vertices that are not necessarily adjacent. Such random walks are sometimes called long-range random walks. There are several studies on such random walks; see [ 5 ] and references there in. The other extends the state space, defined on a state space where each vertex on the hypercube is n -valued. Here, two states that differ at only one vertex are called adjacent. A graph in which adjacency is represented by edges is called a Hamming graph. One motivation for considering such random walks is an interest in group representations and orthogonal polynomials. The transition probability of a simple random walk on the hypercube is invariant under the action of the hyperoctahedral group, and therefore its spectral representation is given by Krawtchouk polynomials, associated with zonal spherical functions (Section 3, [ 6 ] ). Hora [ 10 ] established that the spectral representation of the transition probability of a class of random walks on the Hamming graph has Krawtchouk polynomial eigenfunctions. Quantum walks are motivated by search algorithms in quantum computing. While not Markov chains, they are models that incorporate randomness in the quantum mechanical sense. The first such model was a coined quantum walk on a finite graph introduced by Aharonov et al. [ 1 ] . They discussed quantum walks on cycles, and quantum walks on various finite graphs have been explored in the literature. However, quantum walks are harder to analyze than random walks, and explicit results are restricted to a limited number of models. As far as the authors are aware, there are only results [ 9 ] and [ 13 ] for the quantum walk associated with the simple random walk on the hypercube. Furthermore, the former involves explicit matrix calculations, while the latter relies on results from a birth-death process. It seems difficult to extend these methods to more general quantum walks. In this paper, we discuss a class of symmetric quantum walks on Hamming graphs, where the distance between vertices specifies the transition probability by using the commutative association scheme. Section 2 introduces random walks on the hypercube and Hamming graphs, on which the class of quantum walks considered in this paper is based. While these results are known, describing them using the commutative association scheme prepares the stage for the next section. Section 3 describes the class of quantum walks considered in this paper. We prepare a coin space isomorphic to the state space and introduce the evolution operator. We then give the Fourier transform. Section 4 discusses the zeros of self-reciprocal polynomials. We show that these zeros are aligned on the unit circle in the complex plane, and provide an explicit form for special cases. These zeros are eigenvalues of the evolution operator. Section 5 presents the main result of this paper: the spectral representation of the wave vector using the Krawtchouk polynomials. When each vertex is binary, i.e., the hypercube, a particularly explicit form is obtained. In Section 6 , as an application of the spectral representation of the wave vector obtained in Section 5 , we give limiting distributions for various quantum walks. We also reproduce known results for quantum walks associated with simple random walks on the hypercube as special cases. 2 The class of random walks We begin with a quick review of the Hamming graph and some related notions. See [ 2 ] , Chapter III and [ 3 ] , Chapter 2 for details. Let a state space X=\{0,1,\ldots,n-1\}^{d} where d,n\geq 2 . Set \partial(x,y)=|\{i:x_{i}\neq y_{j}\}| for x=(x_{i}) , y=(y_{i}) \in X . The distance \partial induces a relation X\times X by (x,y)\in R_{i} \Leftrightarrow \partial(x,y)=i , i\in\{0,1,\ldots,d\} . An undirected graph (X,R_{1}) with vertices X and edges R_{1} is called a Hamming graph H(d,n) (or the hypercube if n=2 ). The adjacency matrix A_{i} is defined by (A_{i})_{x,y}=\left\{\begin{array}[]{ccc}1&\text{if}&(x,y)\in R_{i},\\ 0&\text{if}&(x,y)\notin R_{i}.\end{array}\right. Let \mathcal{A} be the vector subspace of the matrices M_{X}(\mathbb{C}) spanned by A_{0} , A_{1},\ldots,A_{d} . If \mathcal{A} is commutative with the matrix product, it is called the Bose–Mesner algebra. Set \kappa_{i}=|\{y\in X:\partial(x,y)=i\}| (the right-hand being side independent of x\in X ), where \kappa_{1} is the degree of each vertex. Commutative A_{0} , A_{1},\ldots,A_{d} are simultaneously diagonalized by primitive idempotents E_{0} , E_{1},\ldots,E_{d} in \mathcal{A} . Here E_{0} denotes the matrix whose entries are all 1/n^{d} . The base change determines the coefficients p_{i}(j) and q_{i}(j) A_{i}=\sum_{i=0}^{d}p_{i}(j)E_{j},\quad n^{d}E_{i}=\sum_{j=0}^{d}q_{i}(j)A_{j}. In terms of the Krawtchouk polynomials K_{i}(j)=\sum_{l=0}^{i}(-1)^{l}(n-1)^{i-l}\begin{pmatrix}j\\ l\end{pmatrix}\begin{pmatrix}d-j\\ i-l\end{pmatrix}, (1) we have ( [ 2 ] , Section III.2) p_{i}(j)=q_{i}(j)=K_{i}(j),\quad\kappa_{i}=K_{i}(0)=(n-1)^{i}\begin{pmatrix}d\\ i\end{pmatrix}. The generating function for the Krawtchouk polynomials is \sum_{l=0}^{d}K_{l}(j)s^{l}=(1+(n-1)s)^{d-j}(1-s)^{j}. (2) Orthogonality is with respect to the Binomial distribution: \sum_{l=0}^{d}K_{i}(l)K_{j}(l)\left(\begin{array}[]{c}d\\ l\end{array}\right)\left(1-\frac{1}{n}\right)^{l}\left(\frac{1}{n}\right)^{d-l}=\delta_{i,j}(n-1)^{i}\begin{pmatrix}d\\ i\end{pmatrix}. Another version of Krawtchouk polynomials with different normalization found in literature is Q_{i}(j;1-1/n,d)={}_{2}F_{1}(-i,-j;-d;n/(n-1))=\frac{K_{i}(j)}{\kappa_{i}}, which are the zonal spherical functions of the permutation group S_{n}\wr S_{d} on X . They satisfy Q_{i}(j;1-1/n,d)=Q_{j}(i;1-1/n,d) . See [ 7 ] and [ 11 ] , Section 1.10. Hora [ 10 ] discussed random walks on the Hamming graph H(d,n) with transition probability matrix P . He assumed a spatial symmetry of P that it is constant on each orbit R_{i} : Assumption 1 . \partial(x,y)=\partial(x^{\prime},y^{\prime}) \Rightarrow (P)_{x,y}=(P)_{x^{\prime},y^{\prime}} or equivalently that P belongs to Bose–Mesner algebra \mathcal{A} . The transition probability takes the form of P=\sum_{i=0}^{d}\frac{w_{i}}{\kappa_{i}}A_{i},\quad\text{where}\quad w_{i}\geq 0,~\sum_{i=0}^{d}w_{i}=1,\quad\kappa_{i}=|\{y\in X:\partial(x,y)=i\}|. (3) Let P_{t}(h) , t\in\mathbb{N}:=\{0,1,\ldots\} denote the t -step transition probability (P^{t})_{x,y} for (x,y)\in R_{h} . Hora [ 10 ] established a spectral representation P_{t}(h)=\frac{1}{n^{d}}\sum_{i=0}^{d}\rho_{i}^{t}K_{i}(h),\quad h\in\{0,1,\ldots,d\} (4) with eigenvalues \rho_{i}=\sum_{j=0}^{d}\frac{w_{j}}{\kappa_{j}}K_{j}(i)=\sum_{j=0}^{d}\frac{w_{j}}{\kappa_{i}}K_{i}(j),\quad i\in\{0,1,\ldots,d\}. (5) We note that \rho_{0}=1 and -\frac{1}{n-1}\leq\rho_{i}\leq 1,\quad i\in\{1,\ldots,d\}. (6) If a random walk is irreducible and aperiodic -1 is not an eigenvalue.