{
  "annotation_id": "b3c29dff-79c5-4e41-8ed2-360ca661f30d",
  "date_created": "2026-03-02T18:01:48.286000Z",
  "date_modified": "2026-03-02T18:01:48.286000Z",
  "file_hash": "37fbf6f0344d779dab96a3421e852105acbb224a53b825dbcda16f84d704d630",
  "private": false,
  "record": {
    "abstract": "The collision problem is to decide whether a function X:{1,..,n}-\u003e{1,..,n} is\none-to-one or two-to-one, given that one of these is the case. We show a lower\nbound of Theta(n^{1/5}) on the number of queries needed by a quantum computer\nto solve this problem with bounded error probability. The best known upper\nbound is O(n^{1/3}), but obtaining any lower bound better than Theta(1) was an\nopen problem since 1997. Our proof uses the polynomial method augmented by some\nnew ideas. We also give a lower bound of Theta(n^{1/7}) for the problem of\ndeciding whether two sets are equal or disjoint on a constant fraction of\nelements. Finally we give implications of these results for quantum complexity\ntheory.",
    "arxiv_id": "quant-ph/0111102",
    "authors": [
      "Scott Aaronson"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "Quantum Lower Bound for the Collision Problem",
    "url": "https://arxiv.org/abs/quant-ph/0111102"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "dcd20827-c31f-4eb9-9c77-9e60f0d1ef9f",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}