dorsal/arxiv
View SchemaA lower bound on the quantum query complexity of read-once functions
| Authors | Howard Barnum, Michael Saks |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0201007 |
| URL | https://arxiv.org/abs/quant-ph/0201007 |
Abstract
We establish a lower bound of $\Omega{(\sqrt{n})}$ on the bounded-error quantum query complexity of read-once Boolean functions, providing evidence for the conjecture that $\Omega(\sqrt{D(f)})$ is a lower bound for all Boolean functions. Our technique extends a result of Ambainis, based on the idea that successful computation of a function requires ``decoherence'' of initially coherently superposed inputs in the query register, having different values of the function. The number of queries is bounded by comparing the required total amount of decoherence of a judiciously selected set of input-output pairs to an upper bound on the amount achievable in a single query step. We use an extension of this result to general weights on input pairs, and general superpositions of inputs.
{
"annotation_id": "24546b8e-b267-4348-b860-515fc0ef4d90",
"date_created": "2026-03-02T18:01:48.830000Z",
"date_modified": "2026-03-02T18:01:48.830000Z",
"file_hash": "a84f2f3835f2eabb1fbdafcea2e2c5650b004cda489cd6a1468974837813e4fd",
"private": false,
"record": {
"abstract": "We establish a lower bound of $\\Omega{(\\sqrt{n})}$ on the bounded-error\nquantum query complexity of read-once Boolean functions, providing evidence for\nthe conjecture that $\\Omega(\\sqrt{D(f)})$ is a lower bound for all Boolean\nfunctions. Our technique extends a result of Ambainis, based on the idea that\nsuccessful computation of a function requires ``decoherence\u0027\u0027 of initially\ncoherently superposed inputs in the query register, having different values of\nthe function. The number of queries is bounded by comparing the required total\namount of decoherence of a judiciously selected set of input-output pairs to an\nupper bound on the amount achievable in a single query step. We use an\nextension of this result to general weights on input pairs, and general\nsuperpositions of inputs.",
"arxiv_id": "quant-ph/0201007",
"authors": [
"Howard Barnum",
"Michael Saks"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "A lower bound on the quantum query complexity of read-once functions",
"url": "https://arxiv.org/abs/quant-ph/0201007"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b140a164-8adc-41a0-9bf6-21832ca86fdd",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}