Strengthening the adversary method with negative weights - Troy Lee

The quantum adversary method, along with the polynomial method, is one of the most successful techniques for proving lower bounds on quantum query complexity. The adversary method, originally developed by Ambainis, has recently received a lot of attention with several authors giving generalizations and alternative formulations. These include formulations in terms of weight schemes [Amb03,Zha05], eigenvalues of matrices [BSS03], and Kolmogorov complexity [LM04]. Using the duality theory of semidefinite programming, Spalek and Szegedy show that all of these formulations of the adversary method are in fact equivalent. We present a strengthening of the adversary method. This new method gives a lower bound on bounded-error quantum query complexity, is always at least as large as the adversary bound, and can sometimes be much larger: we show that for every m, there is a function f whose adversary bound is less than m and where the new bound is larger than m^{1.09}. We also show that this new bound does not face the ``certificate complexity'' barrier which limits the old adversary method. The new bound is obtained by allowing matrices with negative entries in the matrix formulation of the adversary method. Joint work with Peter Hoyer and Robert Spalek.