Coins Make Quantum Walks Faster
| dc.creator | Ambainis, Andris | |
| dc.creator | Kempe, Julia | |
| dc.creator | Rivosh, Alexander | |
| dc.date | 2004-02-16 | |
| dc.date.accessioned | 2026-07-07T06:26:59Z | |
| dc.date.available | 2026-07-07T06:26:59Z | |
| dc.description | 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 $Ω(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 $Ω(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)$. | |
| dc.description | 25 pages, no figures | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0402107 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0402107 | |
| dc.identifier | Proc. 16th ACM-SIAM SODA, p. 1099-1108 (2005) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/97286 | |
| dc.subject | Quantum Physics | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Coins Make Quantum Walks Faster | |
| dc.type | text |