{
  "annotation_id": "7c3734d2-5416-4196-88f2-3ba35d9a7c6b",
  "date_created": "2026-03-02T18:01:42.189000Z",
  "date_modified": "2026-03-02T18:01:42.189000Z",
  "file_hash": "ef6993d454eb69e6afbdac72aec502ef83b043d10ca91d4fde09d56af80a73b8",
  "private": false,
  "record": {
    "abstract": "We introduce a new model for studying quantum data structure problems -- the\n\"quantum cell probe model\". We prove a lower bound for the static predecessor\nproblem in the address-only version of this model where we allow quantum\nparallelism only over the `address lines\u0027 of the queries. The address-only\nquantum cell probe model subsumes the classical cell probe model, and many\nquantum query algorithms like Grover\u0027s algorithm fall into this framework. Our\nlower bound improves the previous known lower bound for the predecessor problem\nin the classical cell probe model with randomised query schemes, and matches\nthe classical deterministic upper bound of Beame and Fich. Beame and Fich have\nalso proved a matching lower bound for the predecessor problem, but only in the\nclassical deterministic setting. Our lower bound has the advantage that it\nholds for the more general quantum model, and also, its proof is substantially\nsimpler than that of Beame and Fich. We prove our lower bound by obtaining a\nround elimination lemma for quantum communication complexity. A similar lemma\nwas proved by Miltersen, Nisan, Safra and Wigderson for classical communication\ncomplexity, but it was not strong enough to prove a lower bound matching the\nupper bound of Beame and Fich. Our quantum round elimination lemma also allows\nus to prove rounds versus communication tradeoffs for some quantum\ncommunication complexity problems like the \"greater-than\" problem. We also\nstudy the \"static membership\" problem in the quantum cell probe model.\nGeneralising a result of Yao, we show that if the storage scheme is implicit,\nthat is it can only store members of the subset and `pointers\u0027, then any\nquantum query scheme must make $\\Omega(\\log n)$ probes.",
    "arxiv_id": "quant-ph/0104100",
    "authors": [
      "Pranab Sen",
      "S. Venkatesh"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "Lower bounds in the quantum cell probe model",
    "url": "https://arxiv.org/abs/quant-ph/0104100"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "10f4355d-0ae7-41bd-9888-02e08d755834",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}