Revised: July 24, 2009
Published: January 12, 2010
Abstract: [Plain Text Version]
We present a new method for proving lower bounds on quantum query algorithms. The new method is an extension of the adversary method, by analyzing the eigenspace structure of the problem.
Using the new method, we prove a strong direct product theorem for quantum search. This result was previously proved by Klauck, Špalek, and de Wolf (FOCS’04) using the polynomials method. No proof using the adversary method was known before.