{
  "annotation_id": "86c66477-8d52-4a74-b137-5efc412e1cf0",
  "date_created": "2026-03-02T18:01:38.150000Z",
  "date_modified": "2026-03-02T18:01:38.150000Z",
  "file_hash": "659ab06b2214a0191e3101d62e34bd400a313961797649dec4c92da9b371dba4",
  "private": false,
  "record": {
    "abstract": "We present several applications of quantum amplitude amplification to finding\nclaws and collisions in ordered or unordered functions. Our algorithms\ngeneralize those of Brassard, Hoyer, and Tapp, and imply an O(N^{3/4} log N)\nquantum upper bound for the element distinctness problem in the comparison\ncomplexity model (contrasting with Theta(N log N) classical complexity). We\nalso prove a lower bound of Omega(N^{1/2}) comparisons for this problem and\nderive bounds for a number of related problems.",
    "arxiv_id": "quant-ph/0007016",
    "authors": [
      "Harry Buhrman",
      "Christoph Durr",
      "Mark Heiligman",
      "Peter Hoyer",
      "Frederic Magniez",
      "Miklos Santha",
      "Ronald de Wolf"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1137/S0097539702402780",
    "journal_ref": "SIAM Journal on Computing, 34(6), 1324-1330, 2005",
    "title": "Quantum Algorithms for Element Distinctness",
    "url": "https://arxiv.org/abs/quant-ph/0007016"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "977df062-8213-4136-9bcc-cc7a9b94b615",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}