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 Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #cs.CC #quant-ph

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

20 pages, v2 typos corrected

openalex publication_date 2005/08/26 · arxiv created 2005/09/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Quantum Complexity Theory
• Optimal lower bounds for quantum automata and random access codes

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