A quantum walk induced by Hoffman graphs and its periodicity

In order to define the discrete-time quantum walks, we divide the vertex set of a graph by two partitions and give a time evolution operator by a product of two local unitary operators on each partition. In this paper, we make such partitions from a Hoffman graph, which gives generalization of line graphs, and study a staggered walk. We first show that the square of the time evolution operator of the Grover walk is unitarily equivalent to that of the staggered walk on the generalized line graph induced from a Hoffman graph. Furthermore, we focus on the periodicity of quantum walks and show that the staggered walk on the generalized line graph is periodic whenever the Grover walk on the original graph is periodic by using the unitary equivalence. This work is the first trial to develop the relation between quantum walks and Hoffman graphs. (C) 2019 Elsevier Inc. All rights reserved.