Phase-modified CTQW unable to distinguish strongly regular graphs efficiently

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

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Various quantum walk-based algorithms have been developed, aiming to distinguish non-isomorphic graphs with polynomial scaling, within both the discrete-time quantum walk (DTQW) and continuous-time quantum walk (CTQW) frameworks. Whilst both the single-particle DTQW and CTQW have failed to distinguish non-isomorphic strongly regular graph families (prompting the move to multi-particle graph isomorphism (GI) algorithms), the single-particle DTQW has been successfully modified by the introduction of a phase factor to distinguish a wide range of graphs in polynomial time. In this paper, we prove that an analogous phase modification to the single particle CTQW does not have the same distinguishing power as its discrete-time counterpart, in particular it cannot distinguish strongly regular graphs with the same family parameters with the same efficiency.

Original languageEnglish
Article number265301
Pages (from-to)1-13
Number of pages13
JournalJournal of Physics A: Mathematical and Theoretical
Volume48
Issue number26
DOIs
Publication statusPublished - 3 Jul 2015
Externally publishedYes

Keywords

  • graph isomorphism
  • phase addition
  • quantum walk

Fingerprint Dive into the research topics of 'Phase-modified CTQW unable to distinguish strongly regular graphs efficiently'. Together they form a unique fingerprint.

  • Cite this