Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer

Andris Ambainis; Andrew M. Childs; Ben W. Reichardt; Robert Špalek; Shengyu Zhang

doi:10.1109/FOCS.2007.4389507

Any AND-OR formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer

Andris Ambainis^*
, Andrew M. Childs
, Ben W. Reichardt
, Robert Špalek
, Shengyu Zhang

^*Corresponding author for this work

Department of Computer Science

University of Waterloo
California Institute of Technology
University of California at Berkeley

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

50 Citations (Scopus)

Abstract

For any AND-OR formula of size N, there exists a bounded-error N ^1/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(√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.

Original language	English
Title of host publication	Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Publisher	IEEE Computer Society
Pages	363-372
Number of pages	10
ISBN (Print)	0769530109, 9780769530109
DOIs	https://doi.org/10.1109/FOCS.2007.4389507
Publication status	Published - 2007
Event	48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States Duration: 20 Oct 2007 → 23 Oct 2007

Publication series

Name	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)	0272-5428

Conference

Conference	48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Country/Territory	United States
City	Providence, RI
Period	20/10/07 → 23/10/07

OECD Field of Science

1.2 Computer and Information Sciences

Access to Document

10.1109/FOCS.2007.4389507

Cite this

Ambainis, A., Childs, A. M., Reichardt, B. W., Špalek, R., & Zhang, S. (2007). Any AND-OR formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 (pp. 363-372). Article 4389507 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). IEEE Computer Society. https://doi.org/10.1109/FOCS.2007.4389507

@inproceedings{29a24c8e6c6849d79c6371ac9e5c098e,

title = "Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer",

abstract = "For any AND-OR formula of size N, there exists a bounded-error N 1/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(√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.",

author = "Andris Ambainis and Childs, \{Andrew M.\} and Reichardt, \{Ben W.\} and Robert {\v S}palek and Shengyu Zhang",

year = "2007",

doi = "10.1109/FOCS.2007.4389507",

language = "English",

isbn = "0769530109",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "363--372",

booktitle = "Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007",

address = "United States",

note = "48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 ; Conference date: 20-10-2007 Through 23-10-2007",

}

Ambainis, A, Childs, AM, Reichardt, BW, Špalek, R & Zhang, S 2007, Any AND-OR formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer. in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007., 4389507, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, IEEE Computer Society, pp. 363-372, 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, Providence, RI, United States, 20/10/07. https://doi.org/10.1109/FOCS.2007.4389507

Any AND-OR formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer. / Ambainis, Andris; Childs, Andrew M.; Reichardt, Ben W. et al.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. IEEE Computer Society, 2007. p. 363-372 4389507 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

TY - GEN

T1 - Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer

AU - Ambainis, Andris

AU - Childs, Andrew M.

AU - Reichardt, Ben W.

AU - Špalek, Robert

AU - Zhang, Shengyu

PY - 2007

Y1 - 2007

N2 - For any AND-OR formula of size N, there exists a bounded-error N 1/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(√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.

AB - For any AND-OR formula of size N, there exists a bounded-error N 1/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(√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.

UR - https://www.scopus.com/pages/publications/46749125783

U2 - 10.1109/FOCS.2007.4389507

DO - 10.1109/FOCS.2007.4389507

M3 - Conference paper

AN - SCOPUS:46749125783

SN - 0769530109

SN - 9780769530109

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 363

EP - 372

BT - Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007

PB - IEEE Computer Society

T2 - 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007

Y2 - 20 October 2007 through 23 October 2007

ER -

Ambainis A, Childs AM, Reichardt BW, Špalek R, Zhang S. Any AND-OR formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. IEEE Computer Society. 2007. p. 363-372. 4389507. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). doi: 10.1109/FOCS.2007.4389507