Any AND-OR formula of size can be evaluated in time on a quantum computer

被引：39

作者：

Ambainis, Andris ^{[1
,2
]}

Childs, Andrew M. ^{[2
,3
]}

Reichardt, Ben W. ^{[3
]}

Spalek, Robert ^{[4
]}

Zhang, Shengyu ^{[3
]}

机构：

[1] Latvian State Univ, Dept Comp Sci, Riga, Latvia

[2] Univ Waterloo, Dept Cominator & Optimizat, Inst Quntum Comp, Waterloo, ON N2L 3G1, Canada

[3] CALTECH, Inst Quantum Informat, Pasadena, CA 91125 USA

[4] Univ Calif Berkeley, Berkeley, CA 94720 USA

来源：

48TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2007年

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1109/FOCS.2007.57

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1) -time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(root N) queries, which is optimal. It follows that the (2 - o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.

引用

页码：363 / +

页数：2

共 21 条

[1] Polynomial degree vs. quantum query complexity [J].

Ambainis, A .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2006, 72 (02) :220-238

[2]

AMBAINIS A, 2007, QUANTPH07043628

[3]

[Anonymous], [No title captured], DOI [10.1145/237814.237866, DOI 10.1145/237814.237866]

[4] A lower bound on the quantum query complexity of read-once functions [J].

Barnum, H ;

Saks, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2004, 69 (02) :244-258

[5] Quantum lower bounds by polynomials [J].

Beals, R ;

Buhrman, H ;

Cleve, R ;

Mosca, M ;

De Wolf, R .

JOURNAL OF THE ACM, 2001, 48 (04) :778-797

[6] SIZE-DEPTH TRADEOFFS FOR BOOLEAN-FORMULAS [J].

BONET, ML ;

BUSS, SR .

INFORMATION PROCESSING LETTERS, 1994, 49 (03) :151-155

[7]

BSHOUTY NH, 1991, PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, P334, DOI 10.1109/SFCS.1991.185387

[8]

Buhrman H., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P63, DOI 10.1145/276698.276713

[9]

CHILDS A, 2007, QUANTPH0703015

[10]

CHILDS AM, 2007, QUANTPH0702160

← 1 2 3 →