Complexity analysis of quantum walk based search algorithms

B. L. Douglas, J. B. Wang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

We present several families of graphs that allow both efficient quantum walk implementations and efficient quantum walk based search algorithms. For these graphs, we construct quantum circuits that explicitly implement the full quantum walk search algorithm, without reference to a 'black box' oracle. These circuits provide a practically implementable method to explore quantum walk based search algorithms with the aim of eventual real-world applications. We also provide a numerical anaylsis of a quantum walk based search along a twisted toroid family of graphs, which requires O(n log(n)) elementary 2-qubit quantum gate operations to find a marked node.

Original languageEnglish
Pages (from-to)1601-1605
Number of pages5
JournalJournal of Computational and Theoretical Nanoscience
Volume10
Issue number7
DOIs
Publication statusPublished - Jul 2013
Externally publishedYes

Keywords

  • quantum circuit
  • quantum search algorithm
  • quantum walk

Fingerprint

Dive into the research topics of 'Complexity analysis of quantum walk based search algorithms'. Together they form a unique fingerprint.

Cite this