ECCC-Report TR02-002https://eccc.weizmann.ac.il/report/2002/002Comments and Revisions published for TR02-002en-usTue, 08 Jan 2002 14:57:36 +0200
Paper TR02-002
| A lower bound on the quantum query complexity of read-once functions |
Howard Barnum,
Michael Saks
https://eccc.weizmann.ac.il/report/2002/002We 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.
Tue, 08 Jan 2002 14:57:36 +0200https://eccc.weizmann.ac.il/report/2002/002