## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 217-236 |

Number of pages | 20 |

Journal | Linear Algebra and Its Applications |

Volume | 579 |

DOIs | |

Publication status | Published - 2019 Oct 15 |

## Keywords

- Grover walk
- Hoffman graph
- Intersection graph
- Line graph
- Periodicity
- Staggered walk

## ASJC Scopus subject areas

- Algebra and Number Theory
- Numerical Analysis
- Geometry and Topology
- Discrete Mathematics and Combinatorics