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