A lower bound on the quantum query complexity of read-once functions

Details A lower bound on the quantum query complexity of read-once functions A lower bound on the quantum query complexity of read-once functions

2002-01-03

arxiv.org/abs/quant-ph/0201007v1

Physics

Quantum Physics

12 pages, LaTeX

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A lower bound on the quantum query complexity of read-once functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A lower bound on the quantum query complexity of read-once functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A lower bound on the quantum query complexity of read-once functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521293