A new quantum lower bound method, with an application to strong direct product theorem for quantum search

2005/08/26 by Andris Ambainis, Ambainis, Andris · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0508200

20 pages, v2 typos corrected

arxiv created 2005/09/07 · arxiv updated 2009/12/01

Abstract

We present a new method for proving lower bounds on quantum query algorithms. The new method is an extension of 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 proven by Klauck, Spalek and de Wolf (quant-ph/0402123) using polynomials method. No proof using adversary method was known before.

Cited by

• The Compressed Oracle is a Worthy (Multiplicative) Adversary

Related

• A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
• Tight Bounds on Quantum Searching
• The Multiplicative Quantum Adversary
• Quantum lower bounds by quantum arguments
• Applications of the Adversary Method in Quantum Query Algorithms