**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.