Quantum lower bounds by polynomials

被引:112
作者
Beals, R [1 ]
Buhrman, H [1 ]
Cleve, R [1 ]
Mosca, M [1 ]
de Wolf, R [1 ]
机构
[1] Univ Arizona, Dept Math, Tucson, AZ 85721 USA
来源
39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 1998年
关键词
D O I
10.1109/SFCS.1998.743485
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0, 1}(N) in the black-box model. We show that, in the black-box model. the exponential quantum speed-up obtained for partial functions (i.e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T-6) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
引用
收藏
页码:352 / 361
页数:2
相关论文
empty
未找到相关数据