dorsal/arxiv
View SchemaThe Quantum Complexity of Set Membership
| Authors | Jaikumar Radhakrishnan, Pranab Sen, S. Venkatesh |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0007021 |
| URL | https://arxiv.org/abs/quant-ph/0007021 |
Abstract
We study the quantum complexity of the static set membership problem: given a subset S (|S| \leq n) of a universe of size m (m \gg n), store it as a table of bits so that queries of the form `Is x \in S?' can be answered. The goal is to use a small table and yet answer queries using few bitprobes. This problem was considered recently by Buhrman, Miltersen, Radhakrishnan and Venkatesh, where lower and upper bounds were shown for this problem in the classical deterministic and randomized models. In this paper, we formulate this problem in the "quantum bitprobe model" and show tradeoff results between space and time.In this model, the storage scheme is classical but the query scheme is quantum.We show, roughly speaking, that similar lower bounds hold in the quantum model as in the classical model, which imply that the classical upper bounds are more or less tight even in the quantum case. Our lower bounds are proved using linear algebraic techniques.
{
"annotation_id": "f6b457cc-2ba6-4301-9cc6-5ef8bc207fb4",
"date_created": "2026-03-02T18:01:38.571000Z",
"date_modified": "2026-03-02T18:01:38.571000Z",
"file_hash": "9359a57b1b44fe90c1573fee93c7a64ea9164f542aa67c354fad74971175ce7f",
"private": false,
"record": {
"abstract": "We study the quantum complexity of the static set membership problem: given a\nsubset S (|S| \\leq n) of a universe of size m (m \\gg n), store it as a table of\nbits so that queries of the form `Is x \\in S?\u0027 can be answered. The goal is to\nuse a small table and yet answer queries using few bitprobes. This problem was\nconsidered recently by Buhrman, Miltersen, Radhakrishnan and Venkatesh, where\nlower and upper bounds were shown for this problem in the classical\ndeterministic and randomized models. In this paper, we formulate this problem\nin the \"quantum bitprobe model\" and show tradeoff results between space and\ntime.In this model, the storage scheme is classical but the query scheme is\nquantum.We show, roughly speaking, that similar lower bounds hold in the\nquantum model as in the classical model, which imply that the classical upper\nbounds are more or less tight even in the quantum case. Our lower bounds are\nproved using linear algebraic techniques.",
"arxiv_id": "quant-ph/0007021",
"authors": [
"Jaikumar Radhakrishnan",
"Pranab Sen",
"S. Venkatesh"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "The Quantum Complexity of Set Membership",
"url": "https://arxiv.org/abs/quant-ph/0007021"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "452ad21d-4a1e-40a2-94a2-9985669c437e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}