This paper explains the periodicity of the Grover walk on finite graphs. We characterize the graphs to induce 2, 3, 4, 5-periodic Grover walk and obtain a necessary condition of the graphs to induce an odd-periodic Grover walk.
Recently, a research on quantum walks has been developed in various areas.In this paper we focus on the periodicity of the Grover walk which is one of the quantum walks on the discrete graphs.Then we find some special graphs to induce a periodic Grover walk: At some time k, the quantum state φ k returns its initial quantum state φ 0 .Our purpose is to characterize graphs which induce a k-periodic Grover walk for a fixed integer k.We do it for k = 2, 3, 4, 5 and gain a necessary condition for odd k.
Quantum walks determined by the coin operator on graphs have been intensively studied. The typical examples of coin operator are the Grover and Fourier matrices. The periodicity of the Grover walk is well investigated. However, the corresponding result on the Fourier walk is not known. In this paper, we present a necessary condition for the Fourier walk on regular graphs to have the finite period. As an application of our result, we show that the Fourier walks do not have any finite period for some classes of regular graphs such as complete graphs, cycle graphs with selfloops, and hypercubes.
Abstract In this paper we study a class of discrete quantum walks, known as bipartite walks. These include the well-known Grover’s walks. A discrete quantum walk is given by the powers of a unitary matrix U indexed by arcs or edges of the underlying graph. The walk is periodic if U k = I for some positive integer k. Kubota has given a characterization of periodicity of Grover’s walk when the walk is defined on a regular bipartite graph with at most five eigenvalues. We extend Kubota’s results—if a biregular graph G has eigenvalues whose squares are algebraic integers with degree at most two, we characterize periodicity of the bipartite walk over G in terms of its spectrum. We apply periodicity results of bipartite walks to get a characterization of periodicity of Grover’s walk on regular graphs.
The unitary Cayley graph has vertex set $\{0,1, \hdots ,n-1\}$, where two vertices u and v are adjacent if gcd(u−v,n)=1. In this paper, we study periodicity and perfect state transfer of Grover walks on the unitary Cayley graphs. We characterize all periodic unitary Cayley graphs. We prove that periodicity is a necessary condition for occurrence of perfect state transfer on a vertex-transitive graph. Also, we provide a necessary and sufficient condition for the occurrence of perfect state transfer on circulant graphs. Using these, we prove that only four graphs in the class of unitary Cayley graphs exhibit perfect state transfer. Also, we provide a spectral characterization of the periodicity of Grover walks on integral regular graphs.
Quantum walks, the quantum counterpart of classical random walks, are extensively studied for their applications in mathematics, quantum physics, and quantum information science. This study explores the periods and absolute zeta functions of Grover walks on cycle graphs. Specifically, we investigate Grover walks with an odd number of states and determine their periods for cycles with any number of vertices greater than or equal to two. In addition, we compute the absolute zeta functions of M-type Grover walks with finite periods. These results advance the understanding of the properties of Grover walks and their connection to absolute zeta functions.
Spectral characterization of the uniform theta graph Θ(t,2) and classification of 6-periodic Grover walks
We characterize the uniform theta graph Θ(t,2) by the spectrum of its normalized adjacency matrix, or equivalently, by the spectrum of its normalized Laplacian matrix. We also investigate the periodicity of Grover walks on nonregular graphs, which is closely related to the eigenvalues of the normalized adjacency matrix and those of the time evolution matrix of the Grover walk. We show that the Dutch windmill graph Dn(t) is 2n-periodic and that the uniform theta graph Θ(t,n) is (2n+2)-periodic. Furthermore, we completely determine the connected 6-periodic graphs and prove that they are precisely D3(t) with t≥2 and Θ(t,2) with t≥1.