2004/02/16 by Andris Ambainis, Julia Kempe, Alexander Rivosh · 2 citations
Physics and Astronomy · Computer Science · #quant-ph #cs.DS
published as Proc. 16th ACM-SIAM SODA, p. 1099-1108 (2005) · 25 pages, no figures
arxiv created 2004/02/16 · arxiv updated 2009/12/01
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 furthermore 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 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).