Polynomial degree vs quantum query complexity
<|reference_start|>Polynomial degree vs quantum query complexity: 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.<|reference_end|>
@article{ambainis2003polynomial,
    title={Polynomial degree vs. quantum query complexity},
    author={Andris Ambainis},
    journal={Journal of Computer and System Sciences, 72(2): 220-238, 2006},
    year={2003},
    archivePrefix={arXiv},
    eprint={quant-ph/0305028},
    primaryClass={quant-ph cs.CC}
}