dorsal/arxiv
View SchemaCoins Make Quantum Walks Faster
| Authors | Andris Ambainis, Julia Kempe, Alexander Rivosh |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0402107 |
| URL | https://arxiv.org/abs/quant-ph/0402107 |
| Journal | Proc. 16th ACM-SIAM SODA, p. 1099-1108 (2005) |
Abstract
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)$.
{
"annotation_id": "0857760c-19b9-443d-ad0e-516057df2e56",
"date_created": "2026-03-02T18:02:06.454000Z",
"date_modified": "2026-03-02T18:02:06.454000Z",
"file_hash": "bc39838676ea0c67b8ae5a0a762bb6a2c1437539f958e6f6732acc6f06d54f44",
"private": false,
"record": {
"abstract": "We show how to search N items arranged on a $\\sqrt{N}\\times\\sqrt{N}$ grid in\ntime $O(\\sqrt N \\log N)$, using a discrete time quantum walk. This result for\nthe first time exhibits a significant difference between discrete time and\ncontinuous time walks without coin degrees of freedom, since it has been shown\nrecently that such a continuous time walk needs time $\\Omega(N)$ to perform the\nsame task. Our result furthermore improves on a previous bound for quantum\nlocal search by Aaronson and Ambainis. We generalize our result to 3 and more\ndimensions where the walk yields the optimal performance of $O(\\sqrt{N})$ and\ngive several extensions of quantum walk search algorithms for general graphs.\nThe coin-flip operation needs to be chosen judiciously: we show that another\n``natural\u0027\u0027 choice of coin gives a walk that takes $\\Omega(N)$ steps. We also\nshow that in 2 dimensions it is sufficient to have a two-dimensional coin-space\nto achieve the time $O(\\sqrt{N} \\log N)$.",
"arxiv_id": "quant-ph/0402107",
"authors": [
"Andris Ambainis",
"Julia Kempe",
"Alexander Rivosh"
],
"categories": [
"quant-ph",
"cs.DS"
],
"journal_ref": "Proc. 16th ACM-SIAM SODA, p. 1099-1108 (2005)",
"title": "Coins Make Quantum Walks Faster",
"url": "https://arxiv.org/abs/quant-ph/0402107"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4006a17b-d65a-40c1-8bad-78c7d1a0d167",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}