Partition-based discrete-time quantum walks

Norio Konno, Renato Portugal, Iwao Sato, Etsuo Segawa

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)


We introduce a family of discrete-time quantum walks, called two-partition model, based on two equivalence-class partitions of the computational basis, which establish the notion of local dynamics. This family encompasses most versions of unitary discrete-time quantum walks driven by two local operators studied in literature, such as the coined model, Szegedy’s model, and the 2-tessellable staggered model. We also analyze the connection of those models with the two-step coined model, which is driven by the square of the evolution operator of the standard discrete-time coined walk. We prove formally that the two-step coined model, an extension of Szegedy model for multigraphs, and the two-tessellable staggered model are unitarily equivalent. Then, selecting one specific model among those families is a matter of taste not generality.

Original languageEnglish
Article number100
JournalQuantum Information Processing
Issue number4
Publication statusPublished - 2018 Apr 1


  • Bipartite graph
  • Coined walk
  • Graph tessellation
  • Hypergraph walk
  • Intersection graph
  • Quantum walk
  • Staggered walk
  • Szegedy’s walk
  • Unitary equivalence

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Statistical and Nonlinear Physics
  • Theoretical Computer Science
  • Signal Processing
  • Modelling and Simulation
  • Electrical and Electronic Engineering


Dive into the research topics of 'Partition-based discrete-time quantum walks'. Together they form a unique fingerprint.

Cite this