# Using the extra power of the negative adversary method

The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that hindered the adversary method:

1. The property testing barrier: if all 0-instances are $\epsilon$-far from all 1-instances then the adversary method cannot prove a lower bound better than $\Omega(1/\epsilon)$.

2. The certificate complexity barrier: if $C_b(f)$ is the certificate complexity of $b$-instances then the adversary method cannot prove a lower bound better than $\sqrt{C_0(f)C_1(f)}$ where

In the original $ADV^\pm$ paper the authors construct an example function for which their method overcomes both barriers. However, I have not see examples of any natural problems where this has yielded new lower bounds.

Can you provide any references where the negative adversary method was used to achieve a lower bound that the original method could not attain?

The biggest interest for me, is in property testing. Currently there are very few lower bounds on property testing, in fact I only know two (CFMdW2010, ACL2011), that both use the polynomial method (the first by reduction from the collision problem which was originally lower bounded by polynomial method). We know that there are properties that require $\Theta(f(n))$ quantum queries to check, for any computable $f(n) \in O(n)$ (by combining the results in BNFR2002 and GKNR2009). Why is so hard to use the negative adversary method to prove $\Omega(f(n))$ lower bounds on them?

• In the property testing barrier, you probably mean $\Omega(1/\epsilon)$ rather than $\Omega(1/n)$. – Robin Kothari Jul 14 '11 at 15:39
• I know of an application of the negative adversary in cryptography by Brassard, Hoyer, Kalach, Kaplan, Laplante and Salvail (iacr.org/conferences/crypto2011/abstracts/385.htm) that will appear in CRYPTO'11. They used the composition theorem to prove a gap in Merkle games for a quantum adversary working against quantum parties interchanging a message. Sadly, the don't have a final version of the paper yet. So maybe you could wait for the proceedings or contact the authors. – Marcos Villagra Jul 15 '11 at 0:14
• the paper I mentioned in my comment above can be downloaded from arXiv (arxiv.org/abs/1108.2316). In particular, check lemma 1 and lemma 5 in the appendix. – Marcos Villagra Aug 12 '11 at 1:33

Element-distinctness has a lower bound of $\Omega(N^{2/3})$ and its certificate complexity is $\sqrt{N}$, so if one tries to prove it using the adversary method, he would need to use the adversary method with negative weights (which is optimal), or why not the Multiplicative adversary method.