Strengthening the quantum adversary method with negative weights

The adversary method, originally developed by Ambainis, is one of the most successful techniques for proving lower bounds on quantum query complexity. It has been generalized and extended by several authors, giving formulations in terms of weight schemes, spectral norm of matrices, and Kolmogorov complexity. Spalek and Szegedy show that all of these formulations are in fact equivalent. We present a strengthening of the adversary method. Our new bound, which we call $\\MADV$, is always at least as large as the old adversary method $\\ADV$, and we show an example of a function for which $\\MADV(f)=\\Omega(\\ADV(f)^{1.09})$. The bound $\\MADV$ arises by allowing matrices with negative entries in the spectral norm formulation of the adversary method. We show that $\\MADV$ possesses all of the nice features of the $\\ADV$ bound: $\\MADV(f) is a lower bound on the bounded-error quantum query complexity of $f$, its square is a lower bound on the formula size of $f$, and $\\MADV$ behaves well with respect to function composition. On the other hand, $\\MADV$ is not bound by some of the limitations which the old adversary method faces, namely the ``certificate complexity barrier \'\' and the ``Hamming distance barrier\'\'. The certificate complexity barrier states that $\\ADV(f) < (C_0(f)C_1(f))^(1/2)$ for a total function $f$, where $C_0(f),C_1(f)$ are the zero and one certificate complexities of $f$, respectively. We give an example of a function $f$ where $\\MADV(f)=\\Omega(C_0(f)C_1(f)^{0.545}). The Hamming distance barrier states that if every zero-instance of a partial Boolean function $f$ has relative Hamming distance at least $\ \epsilon$ from every one-instance, then $\\ADV(f)\\le 1/\\eps$. We show that this bound also does not apply in this strict sense to $\ \MADV$, although we do not know of an asymptotic separation. This opens up the possibility that the $\\MADV$ method can get better bounds where the $\\ADV$ has gotten stuck, for example triangle finding, the collision problem, or element distinctness. Although in form the $\\MADV$ bound is very similar to the $\\ADV$ bound, our proof that $\\MADV$ is a lower bound on quantum query complexity departs from previous adversary proofs. The basic adversary principle is that if an algorithm $A$ {\\em computes} a function $f$, then in particular the algorithm is able to distinguish between inputs $x$ and $y$ which take on different function values. The adversary method actually lower bounds this, potentially easier, distinguishing problem. In our proof we use a stronger property provided by the fact that the algorithm computes a function. Namely we crucially use the existence of projectors which give the right answer with high probability.