17
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ In the property testing barrier, you probably mean $\Omega(1/\epsilon)$ rather than $\Omega(1/n)$. $\endgroup$ – Robin Kothari Jul 14 '11 at 15:39
  • 5
    $\begingroup$ 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. $\endgroup$ – Marcos Villagra Jul 15 '11 at 0:14
  • $\begingroup$ 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. $\endgroup$ – Marcos Villagra Aug 12 '11 at 1:33
2
$\begingroup$

Apparently, I cannot comment so this will be an answer, even if it only a partial answer.

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.

Otherwise, the polynomial method is sometimes easier to use that the adversary methods since it suffices to prove the existence of polynomial whereas for the adversary method, you need to explicitly have a good adversary matrix, and compute its operator norm.

$\endgroup$
  • $\begingroup$ This specifically does not answer the question. We can use the tightness of the negative adversary method to know that some adversary matrix MUST exist for problems like element-distinctness (or if we want property testing, collision problem). But that is not really using the negative adversary method, it using the polynomial method. I guess if the question is not clear enough, I should refine it. $\endgroup$ – Artem Kaznatcheev Aug 4 '11 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.