© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal 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• 1 citation

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

On the support of the Grover walk on higher-dimensional lattices

Norio Konno, Sarato Takahashi

This paper presents the minimum supports of states for stationary measures of the Grover walk on the d-dimensional lattice by solving the corresponding eigenvalue problem. The numbers of the minimum supports for moving and flip-flop shifts are 2^d (d ge 1) and 4 (d ge 2), respectively.

arXiv:2001.10261•Jan 28, 2020•2 citations

Spectral and asymptotic properties of Grover walks on crystal lattice

Yusuke Higuchi, Norio Konno, Iwao Sato +1 more

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.

arXiv:1401.0154•Dec 31, 2013•2 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

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•153 citations

Walk/Zeta Correspondence for quantum and correlated random walks

Norio Konno, Shunya Tamura

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•1 citation

Stationary measures of three-state quantum walks on the one-dimensional lattice

Hikari Kawai, Komatsu, Takashi, Norio Konno

In this paper, we consider stationary measures of discrete-time three-state quantum walks including the Fourier and Grover walks in the one-dimensional lattice. We give non-uniform stationary measures by solving the corresponding eigenvalue problem. Our new method is based on a reduced matrix, which is different from the generating function approach in our previous work. As a corollary, the Fourier walk on the cycle has a stationary measure with a periodicity.

arXiv:1702.01523•Feb 6, 2017•7 citations

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

.

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.

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.