{
  "annotation_id": "4328d883-b1ab-4bbb-86ae-dfa669df9b67",
  "date_created": "2026-03-02T18:02:03.198000Z",
  "date_modified": "2026-03-02T18:02:03.198000Z",
  "file_hash": "9d043f548e354a3464bc729e79cf62e2efad47310eac01cc36e5fb6486ee0d0b",
  "private": false,
  "record": {
    "abstract": "We use quantum walks to construct a new quantum algorithm for element\ndistinctness and its generalization. For element distinctness (the problem of\nfinding two equal items among N given items), we get an O(N^{2/3}) query\nquantum algorithm. This improves the previous O(N^{3/4}) query quantum\nalgorithm of Buhrman et.al. (quant-ph/0007016) and matches the lower bound by\nShi (quant-ph/0112086). The algorithm also solves the generalization of element\ndistinctness in which we have to find k equal items among N items. For this\nproblem, we get an O(N^{k/(k+1)}) query quantum algorithm.",
    "arxiv_id": "quant-ph/0311001",
    "authors": [
      "Andris Ambainis"
    ],
    "categories": [
      "quant-ph",
      "cs.DS"
    ],
    "journal_ref": "SIAM Journal on Computing, 37(1):210-239, 2007",
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "title": "Quantum walk algorithm for element distinctness",
    "url": "https://arxiv.org/abs/quant-ph/0311001"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "4ba5269e-6013-456e-a1ce-879596696018",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}