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

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

Norio Konno, Sarato Takahashi

Published Jan 28, 2020• 2 citations
arXivHTMLPDF

Abstract

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.
DOI
10.48550/arxiv.2001.10261

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

Stationary measures for the three-state Grover walk with one defect in one dimension

Takako Endo, Hikari Kawai, Norio Konno

We obtain stationary measures for the one-dimensional three-state Grover walk with one defect by solving the corresponding eigenvalue problem. We clarify a relation between stationary and limit measures of the walk.

arXiv:1608.07402•Aug 26, 2016•3 citations

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

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

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

Limit Theorems For the Grover Walk Without Memory

Clement Boateng Ampadu

We consider the Grover walk as a 4-state quantum walk without memory in one dimension. The walker in our 4-state quantum walk moves to the left or right. We compute the stationary distribution of the walk, in addition, we obtain the weak limit theorem

arXiv:1108.4149•Aug 20, 2011•4 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.
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.