{
  "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
}