loading...
Polynomial Degree vs. Quantum Query Complexity
Cambridge, Massachusettes October 11-October 14
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.123819744th Annual IEEE Symposium on Foundat ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Andris Ambainis, "Polynomial Degree vs. Quantum Query Complexity," Foundations of Computer Science, Annual IEEE Symposium on, pp. 230, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2003.1238197,
author = {Andris Ambainis},
title = {Polynomial Degree vs. Quantum Query Complexity},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2003},
issn = {0272-5428},
pages = {230},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238197},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - Polynomial Degree vs. Quantum Query Complexity
SN - 0272-5428
SP
EP
A1 - Andris Ambainis,
PY - 2003
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Andris Ambainis, University of Latvia

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.

Citation:
Andris Ambainis, "Polynomial Degree vs. Quantum Query Complexity," focs, pp.230, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.