DocumentCode :
2169638
Title :
Polynomial degree vs. quantum query complexity
Author :
Ambainis, Andris
Author_Institution :
Inst. of Math. & Comput. Sci., Latvia Univ., Riga, Latvia
fYear :
2003
fDate :
11-14 Oct. 2003
Firstpage :
230
Lastpage :
239
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on
ISSN :
0272-5428
Print_ISBN :
0-7695-2040-5
Type :
conf
DOI :
10.1109/SFCS.2003.1238197
Filename :
1238197
Link To Document :
بازگشت