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:1811.05302

The Fourier and Grover walks on the two-dimensional lattice and torus

Asano, Masahiro, Komatsu, Takashi, Norio Konno, Akihiro Narimatsu

Published Nov 13, 2018• 2 citations
arXivHTMLPDF

Abstract

In this paper, we consider discrete-time quantum walks with moving shift (MS) and flip-flop shift (FF) on two-dimensional lattice $\mathbb{Z}^2$ and torus $π_N^2=(\mathbb{Z}/N)^2$. Weak limit theorems for the Grover walks on $\mathbb{Z}^2$ with MS and FF were given by Watabe et al. and Higuchi et al., respectively. The existence of localization of the Grover walks on $\mathbb{Z}^2$ with MS and FF was shown by Inui et al. and Higuchi et al., respectively. Non-existence of localization of the Fourier walk with MS on $\mathbb{Z}^2$ was proved by Komatsu and Tate. Here our simple argument gave non-existence of localization of the Fourier walk with both MS and FF. Moreover we calculate eigenvalues and the corresponding eigenvectors of the $(k_1,k_2)$-space of the Fourier walks on $π_N^2$ with MS and FF for some special initial conditions. The probability distributions are also obtained. Finally, we compute amplitudes of the Grover and Fourier walks on $π_2^2$.

DOI
10.48550/arxiv.1811.05302

Related papers

Localization of two-dimensional quantum walks

Norio Inui, Yoshinao Konishi, Norio Konno

The Grover walk, which is related to Grover's search algorithm on a quantum computer, is one of the typical discrete time quantum walks. However, a localization of the two-dimensional Grover walk starting from a fixed point is strikingly different from other types of quantum walks. The present paper explains the reason why the walker who moves according to the degree-four Grover operator can remain at the starting point with a high probability. It is shown that the key factor for the localization is due to the degeneration of eigenvalues of the time evolution operator. In fact, the global time evolution of the quantum walk on a large lattice is mainly determined by the degree of degeneration. The dependence of the localization on the initial state is also considered by calculating the wave function analytically.

arXiv:quant-ph/0311118•Physical Review A•May 19, 2004•154 citations

Localization does not occur for the Fourier walk on the multi-dimensional lattice

Akihiro Narimatsu

The existence of localization for the Grover walk on the multi-dimensional lattice is known. This paper gives some conditions for the existence of localization for the space-homogeneous quantum walks. We also prove that localization does not occur for the Fourier walk on the multi-dimensional lattice.

arXiv:2007.07398•Quantum Information and Computation•Mar 22, 2021•1 citation

Walk/Zeta Correspondence for quantum and correlated random walks

Norio Konno, Tamura Shunya

In this paper, following the recent paper on Walk/Zeta Correspondence by the first author and his coworkers, we compute the zeta function for the three- and four-state quantum walk and correlated random walk, and the multi-state random walk on the one-dimensional torus by using the Fourier analysis. We deal with also the four-state quantum walk and correlated random walk on the two-dimensional torus. In addition, we introduce a new class of models determined by the generalized Grover matrix bridging the gap between the Grover matrix and the positive-support of the Grover matrix. Finally, we give a generalized version of the Konno-Sato theorem for the new class. As a corollary, we calculate the zeta function for the generalized Grover matrix on the d-dimensional torus.

arXiv:2109.07664•Sep 16, 2021•2 citations

Limit theorems and localization of three-state quantum walks on a line defined by generalized Grover coins

Amrita Mandal, Rohit Sarma Sarkar, Shantanav Chakraborty +1 more

In this article, we undertake a detailed study of the limiting behavior of a three-state discrete-time quantum walk on a one-dimensional lattice with generalized Grover coins. Two limit theorems are proved and consequently we show that the quantum walk exhibits localization at its initial position for a wide range of coin parameters. Finally, we discuss the effect of the coin parameters on the peak velocities of probability distributions of the underlying quantum walks.

arXiv:2204.05625•Physical Review A•Oct 4, 2022•8 citations

Limit distributions of two-dimensional quantum walks

恭平 渡部, Naoki Kobayashi, Makoto Katori +1 more

One-parameter family of discrete-time quantum-walk models on the square lattice, which includes the Grover-walk model as a special case, is analytically studied. Convergence in the long-time limit $t\ensuremath{\rightarrow}\ensuremath{\infty}$ of all joint moments of two components of walker's pseudovelocity, ${X}_{t}/t$ and ${Y}_{t}/t$, is proved and the probability density of limit distribution is derived. Dependence of the two-dimensional limit density function on the parameter of quantum coin and initial four-component qudit of quantum walker is determined. Symmetry of limit distribution on a plane and localization around the origin are completely controlled. Comparison with numerical results of direct computer simulations is also shown.

arXiv:0802.2749•Physical Review A•Jun 19, 2008•92 citations

Exact localization of Grover quantum walks on crystal lattices: transfer currents, a universal bound, and uniform-spanning-tree degree laws

Jacob Goodchild

Exact results for the localization ("trapping") of discrete-time Grover quantum walks on crystal lattices. A finite fraction of a Grover walker stays at its starting point forever, because the walk operator has flat eigenvalues. This paper computes the long-time return probability p̄ exactly for many lattices. Main results:• For the flip-flop Grover walk, the +1 and −1 flat-band projectors are I − Y and I − Y^Q, where Y and Y^Q are the Kirchhoff transfer-current matrices of the Laplacian and signless Laplacian. This reduces trapping to lattice Green functions. It gives closed forms in terms of Watson integrals (simple cubic, BCC, FCC), complete elliptic integrals (triangular, kagome, checkerboard, star, line graphs) and elementary functions of the bond anisotropy.• A universal lower bound p̄ ≥ (d−2)² / [2d(d−1)] for edge-transitive lattices of vertex degree d, attained exactly on the honeycomb, diamond and Laves graph lattices.• Exact trapping for lazy (Szegedy) walks on the square, triangular, honeycomb and diamond lattices as functions of the laziness.• For the moving-shift walk on Z^d, trapping is governed by A_d = ∫₀^∞ erfc(√s)^d ds, with elementary closed forms for d ≤ 5.• The degree of a vertex in the uniform spanning tree is exactly 1 + Binomial(z−1, 1/(z−1)) on 2-arc-transitive lattices, with closed-form degree distributions for several other lattices. All closed forms were identified by integer-relation (PSLQ) searches at 25–80 digits and checked by Brillouin-zone diagonalization and direct simulation of the walks. AI-use disclosure: this research, including choosing the problems, discovering the formulas, running all computations, and writing the manuscript, was carried out with extensive use of an AI system (Claude Code, by Anthropic) under the author's direction. It has not been peer reviewed. The author takes full responsibility for the content. Code: https://github.com/JacobGoodchild/findformula

•Sep 28, 2026•0 citations
In this paper, we consider discrete-time quantum walks with moving shift (MS) and flip-flop shift (FF) on two-dimensional lattice Z2\mathbb{Z}^2Z2 and torus πN2=(Z/N)2π_N^2=(\mathbb{Z}/N)^2πN2​=(Z/N)2. Weak limit theorems for the Grover walks on Z2\mathbb{Z}^2Z2 with MS and FF were given by Watabe et al. and Higuchi et al., respectively. The existence of localization of the Grover walks on Z2\mathbb{Z}^2Z2 with MS and FF was shown by Inui et al. and Higuchi et al., respectively. Non-existence of localization of the Fourier walk with MS on Z2\mathbb{Z}^2Z2 was proved by Komatsu and Tate. Here our simple argument gave non-existence of localization of the Fourier walk with both MS and FF. Moreover we calculate eigenvalues and the corresponding eigenvectors of the (k1,k2)(k_1,k_2)(k1​,k2​)-space of the Fourier walks on πN2π_N^2πN2​ with MS and FF for some special initial conditions. The probability distributions are also obtained. Finally, we compute amplitudes of the Grover and Fourier walks on π22π_2^2π22​.
The Grover walk, which is related to Grover's search algorithm on a quantum computer, is one of the typical discrete time quantum walks. However, a localization of the two-dimensional Grover walk starting from a fixed point is strikingly different from other types of quantum walks. The present paper explains the reason why the walker who moves according to the degree-four Grover operator can remain at the starting point with a high probability. It is shown that the key factor for the localization is due to the degeneration of eigenvalues of the time evolution operator. In fact, the global time evolution of the quantum walk on a large lattice is mainly determined by the degree of degeneration. The dependence of the localization on the initial state is also considered by calculating the wave function analytically.
In this paper, following the recent paper on Walk/Zeta Correspondence by the first author and his coworkers, we compute the zeta function for the three- and four-state quantum walk and correlated random walk, and the multi-state random walk on the one-dimensional torus by using the Fourier analysis. We deal with also the four-state quantum walk and correlated random walk on the two-dimensional torus. In addition, we introduce a new class of models determined by the generalized Grover matrix bridging the gap between the Grover matrix and the positive-support of the Grover matrix. Finally, we give a generalized version of the Konno-Sato theorem for the new class. As a corollary, we calculate the zeta function for the generalized Grover matrix on the d-dimensional torus.
One-parameter family of discrete-time quantum-walk models on the square lattice, which includes the Grover-walk model as a special case, is analytically studied. Convergence in the long-time limit $t\ensuremath{\rightarrow}\ensuremath{\infty}$ of all joint moments of two components of walker's pseudovelocity, Xt/t{X}_{t}/tXt​/t and Yt/t{Y}_{t}/tYt​/t, is proved and the probability density of limit distribution is derived. Dependence of the two-dimensional limit density function on the parameter of quantum coin and initial four-component qudit of quantum walker is determined. Symmetry of limit distribution on a plane and localization around the origin are completely controlled. Comparison with numerical results of direct computer simulations is also shown.
Exact results for the localization ("trapping") of discrete-time Grover quantum walks on crystal lattices. A finite fraction of a Grover walker stays at its starting point forever, because the walk operator has flat eigenvalues. This paper computes the long-time return probability p̄ exactly for many lattices. Main results:• For the flip-flop Grover walk, the +1 and −1 flat-band projectors are I − Y and I − Y^Q, where Y and Y^Q are the Kirchhoff transfer-current matrices of the Laplacian and signless Laplacian. This reduces trapping to lattice Green functions. It gives closed forms in terms of Watson integrals (simple cubic, BCC, FCC), complete elliptic integrals (triangular, kagome, checkerboard, star, line graphs) and elementary functions of the bond anisotropy.• A universal lower bound p̄ ≥ (d−2)² / [2d(d−1)] for edge-transitive lattices of vertex degree d, attained exactly on the honeycomb, diamond and Laves graph lattices.• Exact trapping for lazy (Szegedy) walks on the square, triangular, honeycomb and diamond lattices as functions of the laziness.• For the moving-shift walk on Z^d, trapping is governed by A_d = ∫₀^∞ erfc(√s)^d ds, with elementary closed forms for d ≤ 5.• The degree of a vertex in the uniform spanning tree is exactly 1 + Binomial(z−1, 1/(z−1)) on 2-arc-transitive lattices, with closed-form degree distributions for several other lattices. All closed forms were identified by integer-relation (PSLQ) searches at 25–80 digits and checked by Brillouin-zone diagonalization and direct simulation of the walks. AI-use disclosure: this research, including choosing the problems, discovering the formulas, running all computations, and writing the manuscript, was carried out with extensive use of an AI system (Claude Code, by Anthropic) under the author's direction. It has not been peer reviewed. The author takes full responsibility for the content. Code: https://github.com/JacobGoodchild/findformula