Periodicity of the Discrete-time Quantum Walk on a Finite Graph

• HIGUCHI Yusuke

  Mathematics Laboratories, College of Arts and Sciences, Showa University

• KONNO Norio

  Department of Applied Mathematics, Faculty of Engineering, Yokohama National University

• SATO Iwao

  Oyama National College of Technology

• SEGAWA Etsuo

  Graduate School of Information Sciences, Tohoku University

Abstract

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.

Journal

• Interdisciplinary Information Sciences

  Interdisciplinary Information Sciences 23 (1), 75-86, 2017

  The Editorial Committee of the Interdisciplinary Information Sciences

Keywords

• quantum walk
• periodicity
• evolution matrix
• cyclotomic polynomial
• random walk
• strongly regular graph

Details

• CRID: 1390282679413300096
• NII Article ID: 120006237463
• NII Article ID: 130005519657
• DOI: 10.4036/iis.2017.a.10
• ISSN: 13476157
• ISSN: 13409050
• HANDLE: 10097/00120634
• Web Site: https://tohoku.repo.nii.ac.jp/records/123221
• Web Site: https://www.jstage.jst.go.jp/article/iis/23/1/23_2017.A.10/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed