All Quantum Adversary Methods are Equivalent

Details All Quantum Adversary Methods are Equivalent All Quantum Adversary Methods are Equivalent

2004-09-17

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

Theory of Computing, 2(1):1-18, 2006

Physics

Quantum Physics

18 pages, ICALP 2005, LNCS 3580, v2: polished and fixed one proof, v3: generalized the adversary bound to non-Boolean function

Scientific paper

The quantum adversary method is one of the most versatile lower-bound methods for quantum algorithms. We show that all known variants of this method are equivalent: spectral adversary (Barnum, Saks, and Szegedy, 2003), weighted adversary (Ambainis, 2003), strong weighted adversary (Zhang, 2005), and the Kolmogorov complexity adversary (Laplante and Magniez, 2004). We also pa few new equivalent formulations of the method. This shows that there is essentially _one_ quantum adversary method. From our approach, all known limitations of these versions of the quantum adversary method easily follow.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-304934