Quantum walk-based search and symmetries in graphs

A. Mahasinghe, J. B. Wang*, J. K. Wijerathna

*Corresponding author for this work

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

In this paper we present a lemma, which helps us to establish a link between the distribution of success probabilities from quantum walk based search and the symmetries of the underlying graphs. With the aid of the lemma, we identified certain graph structures of which the quantum walk based search provides high success probabilities at the marked vertices. We also observed that many graph structures and their vertices can be classified according to their structural equivalence using the search probabilities provided by quantum walks, although this method cannot resolve all non-equivalent vertices for strongly regular graphs.

Original languageEnglish
Article number505301
Pages (from-to)1-15
Number of pages15
JournalJournal of Physics A: Mathematical and Theoretical
Volume47
Issue number50
DOIs
Publication statusPublished - 19 Dec 2014
Externally publishedYes

Keywords

  • graph symmetry
  • quantum search
  • quantum walk

Fingerprint Dive into the research topics of 'Quantum walk-based search and symmetries in graphs'. Together they form a unique fingerprint.

Cite this