Title :
Polynomial degree vs. quantum query complexity
Author :
Ambainis, Andris
Author_Institution :
Inst. of Math. & Comput. Sci., Latvia Univ., Riga, Latvia
Abstract :
The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of 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 (M1.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.
Keywords :
communication complexity; polynomial approximation; quantum computing; polynomial degree; polynomial representation; quantum adversary method; quantum algorithm; quantum query complexity; superlinear separation; Approximation methods; Boolean functions; Complexity theory; Computer errors; Computer science; Councils; Mathematics; Polynomials; Quantum computing; Search problems;
Conference_Titel :
Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on
Print_ISBN :
0-7695-2040-5
DOI :
10.1109/SFCS.2003.1238197