A quantum walk induced by Hoffman graphs and its periodicity

Sho Kubota, Etsuo Segawa, Tetsuji Taniguchi, Yusuke Yoshie

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


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 languageEnglish
Pages (from-to)217-236
Number of pages20
JournalLinear Algebra and Its Applications
Publication statusPublished - 2019 Oct 15


  • 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


Dive into the research topics of 'A quantum walk induced by Hoffman graphs and its periodicity'. Together they form a unique fingerprint.

Cite this