We present a new variant of the quantum adversary method, a method for proving lower bounds on the quantum query complexity of a function. Adversary methods work as follows: one defines a progress function based on the state of the algorithm, and shows that for a successful algorithm there is a large gap between the initial and final value known variants upper-bound the _difference_ of the progress function, whereas our new variant upper-bounds the _ratio_ and that is why we coin it the multiplicative adversary. Our new method is rooted in the quantum lower-bound method by Ambainis (2005, 2006), based on the analysis of eigenspaces of the density matrix. Ambainis's method is technically very complicated, it lacks intuition, and it only works for symmetric functions. Our method fits well into the unconditional strong direct product theorem for the multiplicative quantum adversary bound.
Index Terms:
quantum query lower bounds, quantum adversary method, multiplicative adversary, direct product theorems, combinatorial matrices
Citation:
Robert ?palek, "The Multiplicative Quantum Adversary," ccc, pp.237-248, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008