The Multiplicative Quantum Adversary

Details The Multiplicative Quantum Adversary The Multiplicative Quantum Adversary

2007-03-26

arxiv.org/abs/quant-ph/0703237v3

Physics

Quantum Physics

15 pages, v2: removed an incorrect claim, v3: cleaned up, commented better, added stronger bound for OR

Scientific paper

We present a new variant of the quantum adversary method. All adversary methods give lower bounds on the quantum query complexity of a function by bounding the change of a progress function caused by one query. All previous variants upper-bound the_difference_ of the progress function, whereas our new variant upper-bounds the_ratio_ and that is why we coin it the multiplicative adversary. The new method generalizes to all functions the new quantum lower-bound method by Ambainis [Amb05, ASW06] based on the analysis of eigenspaces of the density matrix. We prove a strong direct product theorem for all functions that have a multiplicative adversary lower bound.

Affiliated with

Also associated with

No associations

Rating

The Multiplicative Quantum Adversary 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 The Multiplicative Quantum Adversary, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Multiplicative Quantum Adversary will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-68923