Coins make quantum walks faster

Andris Ambainis, Julia Kempe, Alexander Rivosh

Research output: Contribution to conferencePaper

Abstract

We show how to search N items arranged on a √N × √N grid in time O(√N log N), using a discrete time quantum walk. This result for the first time exhibits a significant difference between discrete time and continuous time walks without coin degrees of freedom, since it has been shown recently that such a continuous time walk needs time Ω(N) to perform the same task. Our result improves on a previous bound for quantum local search by Aaronson and Ambainis. We generalize our result to 3 and more dimensions where the walk yields the optimal performance of O(√N) and give several extensions of quantum walk search algorithms and generic expressions for its performance for general graphs. The coin-flip operation needs to be chosen judiciously: we show that another "natural" choice of coin gives a walk that takes Ω(N) steps. We also show that in 2 dimensions it is sufficient to have a two-dimensional coin-space to achieve the time O(√N log N).

Original languageEnglish (US)
Pages1099-1108
Number of pages10
StatePublished - 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC
Period1/23/051/25/05

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Coins make quantum walks faster'. Together they form a unique fingerprint.

  • Cite this

    Ambainis, A., Kempe, J., & Rivosh, A. (2005). Coins make quantum walks faster. 1099-1108. Paper presented at Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, United States.