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

Spectral and asymptotic properties of Grover walks on crystal lattice

Yusuke Higuchi, Norio Konno, Iwao Sato, Etsuo Segawa

Published Dec 31, 2013• 2 citations
arXivHTMLPDF

Abstract

We propose a twisted Szegedy walk for estimating the limit behavior of a discrete-time quantum walk on a crystal lattice, an infinite abelian covering graph, whose notion was introduced by [14]. First, we show that the spectrum of the twisted Szegedy walk on the quotient graph can be expressed by mapping the spectrum of a twisted random walk onto the unit circle. Secondly, we show that the spatial Fourier transform of the twisted Szegedy walk on a finite graph with appropriate parameters becomes the Grover walk on its infinite abelian covering graph. Finally, as an application, we show that if the Betti number of the quotient graph is strictly greater than one, then localization is ensured with some appropriated initial state. We also compute the limit density function for the Grover walk on $\mathbb{Z}^d$ with flip flop shift, which implies the coexistence of linear spreading and localization. We partially obtain the abstractive shape of the limit density function: the support is within the $d$-dimensional sphere of radius $1/\sqrt{d}$, and $2^d$ singular points reside on the sphere's surface.

DOI
10.48550/arxiv.1401.0154

Related papers

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

Asano, Masahiro, Komatsu, Takashi, Norio Konno +1 more

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$.

arXiv:1811.05302•Nov 13, 2018•1 citation

Spectral mapping theorem of an abstract quantum walk

Yusuke Higuchi, Etsuo Segawa, Akito Suzuki

Given two Hilbert spaces, $\mathcal{H}$ and $\mathcal{K}$, we introduce an abstract unitary operator $U$ on $\mathcal{H}$ and its discriminant $T$ on $\mathcal{K}$ induced by a coisometry from $\mathcal{H}$ to $\mathcal{K}$ and a unitary involution on $\mathcal{H}$. In a particular case, these operators $U$ and $T$ become the evolution operator of the Szegedy walk on a graph, possibly infinite, and the transition probability operator thereon. We show the spectral mapping theorem between $U$ and $T$ via the Joukowsky transform. Using this result, we have completely detemined the spectrum of the Grover walk on the Sierpiński lattice, which is pure point and has a Cantor-like structure.

arXiv:1506.06457•Jun 22, 2015•9 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

Limit theorems for the discrete-time quantum walk on a graph with joined half lines

Kota Chisaki, Norio Konno, Etsuo Segawa

We consider a discrete-time quantum walk W_{t,\kappa} at time t on a graph with joined half lines J_\kappa, which is composed of \kappa half lines with the same origin. Our analysis is based on a reduction of the walk on a half line. The idea plays an important role to analyze the walks on some class of graphs with symmetric initial states. In this paper, we introduce a quantum walk with an enlarged basis and show that W_{t,\kappa} can be reduced to the walk on a half line even if the initial state is asymmetric. For W_{t,\kappa}, we obtain two types of limit theorems. The first one is an asymptotic behavior of W_{t,\kappa} which corresponds to localization. For some conditions, we find that the asymptotic behavior oscillates. The second one is the weak convergence theorem for W_{t,\kappa}. On each half line, W_{t,\kappa} converges to a density function like the case of the one-dimensional lattice with a scaling order of t. The results contain the cases of quantum walks starting from the general initial state on a half line with the general coin and homogeneous trees with the Grover coin.

arXiv:1009.1306•Quantum Information and Computation•Mar 1, 2012•12 citations

Coined quantum walks on weighted graphs

Thomas G. Wong

Abstract We define a discrete-time, coined quantum walk on weighted graphs that is inspired by Szegedy’s quantum walk. Using this, we prove that many lackadaisical quantum walks, where each vertex has l integer self-loops, can be generalized to a quantum walk where each vertex has a single self-loop of real-valued weight l . We apply this real-valued lackadaisical quantum walk to two problems. First, we analyze it on the line or one-dimensional lattice, showing that it is exactly equivalent to a continuous deformation of the three-state Grover walk with faster ballistic dispersion. Second, we generalize Grover’s algorithm, or search on the complete graph, to have a weighted self-loop at each vertex, yielding an improved success probability when l < 3 + 2 2 ≈ 5.828 .

arXiv:1703.10134•Journal of Physics A Mathematical and Theoretical•Sep 13, 2017•36 citations

Quantum walks induced by Dirichlet random walks on infinite trees

Yusuke Higuchi, Etsuo Segawa

Abstract We consider the Grover walk on infinite trees from the viewpoint of spectral analysis. From the previous work, infinite regular trees provide localization. In this paper, we give the complete characterization of the eigenspace of this Grover walk, which involves localization of its behavior and recovers the previous work. Our result suggests that the Grover walk on infinite trees may be regarded as a limit of the quantum walk induced by the isotropic random walk with the Dirichlet boundary condition at the n -th depth rather than one with the Neumann boundary condition.

arXiv:1703.01334•Journal of Physics A Mathematical and Theoretical•Jan 19, 2018•17 citations
We propose a twisted Szegedy walk for estimating the limit behavior of a discrete-time quantum walk on a crystal lattice, an infinite abelian covering graph, whose notion was introduced by [14]. First, we show that the spectrum of the twisted Szegedy walk on the quotient graph can be expressed by mapping the spectrum of a twisted random walk onto the unit circle. Secondly, we show that the spatial Fourier transform of the twisted Szegedy walk on a finite graph with appropriate parameters becomes the Grover walk on its infinite abelian covering graph. Finally, as an application, we show that if the Betti number of the quotient graph is strictly greater than one, then localization is ensured with some appropriated initial state. We also compute the limit density function for the Grover walk on Zd\mathbb{Z}^dZd with flip flop shift, which implies the coexistence of linear spreading and localization. We partially obtain the abstractive shape of the limit density function: the support is within the ddd-dimensional sphere of radius 1/d1/\sqrt{d}1/d​, and 2d2^d2d singular points reside on the sphere's surface.
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​.
Given two Hilbert spaces, H\mathcal{H}H and K\mathcal{K}K, we introduce an abstract unitary operator UUU on H\mathcal{H}H and its discriminant TTT on K\mathcal{K}K induced by a coisometry from H\mathcal{H}H to K\mathcal{K}K and a unitary involution on H\mathcal{H}H. In a particular case, these operators UUU and TTT become the evolution operator of the Szegedy walk on a graph, possibly infinite, and the transition probability operator thereon. We show the spectral mapping theorem between UUU and TTT via the Joukowsky transform. Using this result, we have completely detemined the spectrum of the Grover walk on the Sierpiński lattice, which is pure point and has a Cantor-like structure.
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
We consider a discrete-time quantum walk W_{t,\kappa} at time t on a graph with joined half lines J_\kappa, which is composed of \kappa half lines with the same origin. Our analysis is based on a reduction of the walk on a half line. The idea plays an important role to analyze the walks on some class of graphs with symmetric initial states. In this paper, we introduce a quantum walk with an enlarged basis and show that W_{t,\kappa} can be reduced to the walk on a half line even if the initial state is asymmetric. For W_{t,\kappa}, we obtain two types of limit theorems. The first one is an asymptotic behavior of W_{t,\kappa} which corresponds to localization. For some conditions, we find that the asymptotic behavior oscillates. The second one is the weak convergence theorem for W_{t,\kappa}. On each half line, W_{t,\kappa} converges to a density function like the case of the one-dimensional lattice with a scaling order of t. The results contain the cases of quantum walks starting from the general initial state on a half line with the general coin and homogeneous trees with the Grover coin.
Abstract We define a discrete-time, coined quantum walk on weighted graphs that is inspired by Szegedy’s quantum walk. Using this, we prove that many lackadaisical quantum walks, where each vertex has l integer self-loops, can be generalized to a quantum walk where each vertex has a single self-loop of real-valued weight l . We apply this real-valued lackadaisical quantum walk to two problems. First, we analyze it on the line or one-dimensional lattice, showing that it is exactly equivalent to a continuous deformation of the three-state Grover walk with faster ballistic dispersion. Second, we generalize Grover’s algorithm, or search on the complete graph, to have a weighted self-loop at each vertex, yielding an improved success probability when l < 3 + 2 2 ≈ 5.828 .
Abstract We consider the Grover walk on infinite trees from the viewpoint of spectral analysis. From the previous work, infinite regular trees provide localization. In this paper, we give the complete characterization of the eigenspace of this Grover walk, which involves localization of its behavior and recovers the previous work. Our result suggests that the Grover walk on infinite trees may be regarded as a limit of the quantum walk induced by the isotropic random walk with the Dirichlet boundary condition at the n -th depth rather than one with the Neumann boundary condition.