The compressed oracle technique is captured by the multiplicative adversary method through the new multiplicative ladder adversary method, up to a factor of 6.
A new quantum lower bound method, with an application to strong direct product theorem for quantum search
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
quant-ph 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
The Compressed Oracle is a Worthy (Multiplicative) Adversary
The compressed oracle technique is captured by the multiplicative adversary method through the new multiplicative ladder adversary method, up to a factor of 6.