The compressed oracle technique is captured by the multiplicative adversary method through the new multiplicative ladder adversary method, up to a factor of 6.
Polynomial degree vs. quantum query complexity
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The degree of a polynomial representing (or approximating) a function f is a lower bound for the number of quantum queries needed to compute f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. We exhibit a function with polynomial degree M and quantum query complexity \Omega(M^{1.321...}). This is the first superlinear separation between polynomial degree and quantum query complexity. The lower bound is shown by a new, more general version of quantum adversary method.
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.