Quantum walk search on Johnson graphs

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


The Johnson graph J (n, k) is defined by n symbols, where vertices are kelement subsets of the symbols, and vertices are adjacent if they differ in exactly one symbol. In particular, J (n, 1) is the complete graph Kn, and J (n, 2) is the strongly regular triangular graph Tn, both of which are known to support fast spatial search by continuous-time quantum walk. In this paper, we prove that J (n, 3), which is the n-tetrahedral graph, also supports fast search. In the process, we show that a change of basis is needed for degenerate perturbation theory to accurately describe the dynamics. This method can also be applied to general Johnson graphs J (n, k) with fixed k.

Original languageEnglish (US)
Article number195303
JournalJournal of Physics A: Mathematical and Theoretical
Issue number19
StatePublished - Apr 12 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Modeling and Simulation
  • Mathematical Physics
  • Physics and Astronomy(all)


Dive into the research topics of 'Quantum walk search on Johnson graphs'. Together they form a unique fingerprint.

Cite this