Periodicity of Bipartite Walks on Biregular Graphs with Conditional Spectra

Takako Endo, Takashi Komatsu, Norio Konno +1 more

Sho Kubota

Qiuting Chen

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.

Norio Konno, Iwao Sato, Etsuo Segawa

Recently, the staggered quantum walk (SQW) on a graph is discussed as a generalization of coined quantum walks on graphs and Szegedy walks. We present a formula for the time evolution matrix of a 2-tessellable SQW on a graph, and so directly give its spectra. Furthermore, we present a formula for the Szegedy matrix of a bipartite graph by the same method, and so give its spectra. As an application, we present a formula for the characteristic polynomial of the modified Szegedy matrix in the quantum search problem on a graph, and give its spectra.

Yusuke Yoshie

Yusuke Higuchi, Norio Konno, Iwao Sato +1 more

In this paper we discuss the periodicity of the evolution matrix of Szegedy walk, which is a special type of quantum walk induced by the classical simple random walk, on a finite graph. We completely characterize the periods of Szegedy walks for complete graphs, compete bipartite graphs and strongly regular graphs. In addition, we discuss the periods of Szegedy walk induced by a non-reversible random walk on a cycle.