{
  "annotation_id": "5bb187e2-efee-440b-8a83-fd9488d3d821",
  "date_created": "2026-03-02T18:01:59.977000Z",
  "date_modified": "2026-03-02T18:01:59.977000Z",
  "file_hash": "f089d3c8fc52e506587ad3f052c4faeb87411d4be3dece23334586b17eea6455",
  "private": false,
  "record": {
    "abstract": "Grover\u0027s quantum search algorithm provides a way to speed up combinatorial\nsearch, but is not directly applicable to searching a physical database.\nNevertheless, Aaronson and Ambainis showed that a database of N items laid out\nin d spatial dimensions can be searched in time of order sqrt(N) for d\u003e2, and\nin time of order sqrt(N) poly(log N) for d=2. We consider an alternative search\nalgorithm based on a continuous time quantum walk on a graph. The case of the\ncomplete graph gives the continuous time search algorithm of Farhi and Gutmann,\nand other previously known results can be used to show that sqrt(N) speedup can\nalso be achieved on the hypercube. We show that full sqrt(N) speedup can be\nachieved on a d-dimensional periodic lattice for d\u003e4. In d=4, the quantum walk\nsearch algorithm takes time of order sqrt(N) poly(log N), and in d\u003c4, the\nalgorithm does not provide substantial speedup.",
    "arxiv_id": "quant-ph/0306054",
    "authors": [
      "Andrew M. Childs",
      "Jeffrey Goldstone"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1103/PhysRevA.70.022314",
    "journal_ref": "Phys. Rev. A 70, 022314 (2004)",
    "title": "Spatial search by quantum walk",
    "url": "https://arxiv.org/abs/quant-ph/0306054"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "72ca2006-c1a2-49ca-a3bf-3c5a2c8ba021",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}