Periodicity of the Discrete-time Quantum Walk on a Finite Graph
Yusuke Higuchi, Norio Konno, Iwao Sato, Etsuo Segawa · Interdisciplinary Information Sciences · 2017
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.