A lower bound on the quantum query complexity of read-once functions
| dc.creator | Barnum, Howard | |
| dc.creator | Saks, Michael | |
| dc.date | 2002-01-03 | |
| dc.date.accessioned | 2026-07-07T06:03:29Z | |
| dc.date.available | 2026-07-07T06:03:29Z | |
| dc.description | We establish a lower bound of $Ω{(\sqrt{n})}$ on the bounded-error quantum query complexity of read-once Boolean functions, providing evidence for the conjecture that $Ω(\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. | |
| dc.description | 12 pages, LaTeX | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0201007 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0201007 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/89957 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | A lower bound on the quantum query complexity of read-once functions | |
| dc.type | text |