{
  "annotation_id": "3ea75290-95e3-436e-9455-1eb5689a385a",
  "date_created": "2026-03-02T18:02:03.134000Z",
  "date_modified": "2026-03-02T18:02:03.134000Z",
  "file_hash": "3374196fe1f2d170a93ca2babb19ad53ca48fd24e3d246dbc7ce1238bab2cdcd",
  "private": false,
  "record": {
    "abstract": "Quantum search is a technique for searching N possibilities in only\nO(sqrt(N)) steps. It has been applied in the design of quantum algorithms for\nseveral structured problems. Many of these algorithms require significant\namount of quantum hardware. In this paper we observe that if an algorithm\nrequires O(P) hardware, it should be considered significant if and only if it\nproduces a speedup of at least O(sqrt(P)) over a simple quantum search\nalgorithm. This is because a speedup of $O(sqrt(P)) $ can be trivially obtained\nby dividing the search space into $O(P)$ separate parts and handing the problem\nto independent processors that do a quantum search. We argue that the known\nalgorithms for collision and element distinctness fail to be non-trivial in\nthis sense.",
    "arxiv_id": "quant-ph/0309123",
    "authors": [
      "Lov Grover",
      "Terry Rudolph"
    ],
    "categories": [
      "quant-ph"
    ],
    "journal_ref": "Quantum Information \u0026 Computation, 4, 201 (2004)",
    "title": "How significant are the known collision and element distinctness quantum   algorithms?",
    "url": "https://arxiv.org/abs/quant-ph/0309123"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "57aa3fdc-cdc7-4165-9839-1d2c4b0d92cf",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}