Polynomial degree vs. quantum query complexity

被引：59

作者：

Ambainis, A

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[2] Univ Waterloo, Inst Quantum Comp, Waterloo, ON N2L 3G1, Canada

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2006年 / 72卷 / 02期

关键词：

quantum lower bounds; quantum query complexity; polynomial degree of Boolean functions;

D O I：

10.1016/j.jcss.2005.06.006

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 Omega(M-1.321...). This is the first superlinear separation between polynomial degree and quantum query complexity. The lower bound is shown by a generalized version of the quantum adversary method. (c) 2005 Elsevier Inc. All rights reserved.

引用

页码：220 / 238

页数：19

共 37 条

[1]

AARONSON A, QUANTPH0307149

[2]

AARONSON A, 2004, P STOC 04, P465

[3] Quantum lower bounds for the collision and the element distinctness problems [J].