pdf icon
Volume 6 (2010) Article 1 pp. 1-25
A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search
Received: July 6, 2007
Revised: July 24, 2009
Published: January 12, 2010
Download article from ToC site:
[PDF (324K)] [PS (1218K)] [Source ZIP]
Misc.:
[About the Author] [HTML Bibliography] [BibTeX]
Keywords: quantum computing, quantum algorithms, quantum lower bounds
Categories: quantum computing, complexity theory, lower bounds
ACM Classification: F.1.2, F.2.2
AMS Classification: 81P68, 68Q17

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.