文章基本信息
- 标题：A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search
- 本地全文：下载
- 作者：Andris Ambainis
- 期刊名称：Theory of Computing
- 印刷版ISSN：1557-2862
- 电子版ISSN：1557-2862
- 出版年度：2010
- 卷号：6
- 出版社：University of Chicago
- 摘要：
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.
- 关键词：quantum computing, quantum algorithms, quantum lower bounds
