Physics – Quantum Physics
Scientific paper
2004-02-16
Proc. 16th ACM-SIAM SODA, p. 1099-1108 (2005)
Physics
Quantum Physics
25 pages, no figures
Scientific paper
We show how to search N items arranged on a $\sqrt{N}\times\sqrt{N}$ grid in time $O(\sqrt 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 $\Omega(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(\sqrt{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 $\Omega(N)$ steps. We also show that in 2 dimensions it is sufficient to have a two-dimensional coin-space to achieve the time $O(\sqrt{N} \log N)$.
Ambainis Andris
Kempe Julia
Rivosh Alexander
No associations
LandOfFree
Coins Make Quantum Walks Faster does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Coins Make Quantum Walks Faster, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coins Make Quantum Walks Faster will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-238002