Physics – Quantum Physics
Scientific paper
2005-09-09
Physics
Quantum Physics
10 pages, v2: simplified the proof and added an application, v3: fixed a proof
Scientific paper
The quantum adversary method is a versatile method for proving lower bounds on quantum algorithms. It yields tight bounds for many computational problems, is robust in having many equivalent formulations, and has natural connections to classical lower bounds. A further nice property of the adversary method is that it behaves very well with respect to composition of functions. We generalize the adversary method to include costs--each bit of the input can be given an arbitrary positive cost representing the difficulty of querying that bit. We use this generalization to exactly capture the adversary bound of a composite function in terms of the adversary bounds of its component functions. Our results generalize and unify previously known composition properties of adversary methods, and yield as a simple corollary the Omega(sqrt{n}) bound of Barnum and Saks on the quantum query complexity of read-once functions.
Hoyer Peter
Lee Taegweon
Spalek Robert
No associations
LandOfFree
Tight adversary bounds for composite 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 Tight adversary bounds for composite functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight adversary bounds for composite functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-464943