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

^*Šī darba korespondējošais autors

Datorikas nodaļa

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

Zinātniskās darbības rezultāts: Nodaļa grāmatā/enciklopēdijā/konferences krājumā › Konferences zinātniskais raksts › Pētniecība › koleģiāli recenzēts

51 Atsauces (Scopus)

Kopsavilkums

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.

Oriģinālvaloda	Angļu
Publikācijas avota nosaukums	Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Izdevējs	IEEE Computer Society
Lapas	363-372
Lapu skaits	10
ISBN (Drukātā versija)	0769530109, 9780769530109
DOIs	https://doi.org/10.1109/FOCS.2007.4389507
Publikācijas statuss	Publicēts - 2007
Pasākums	48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, Amerikas Savienotās Valstis Ilgums: 20 okt. 2007 → 23 okt. 2007

Publikāciju sērijas

Nosaukums	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Drukātā versija)	0272-5428

Konference

Konference	48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Valsts/Teritorija	Amerikas Savienotās Valstis
Pilsēta	Providence, RI
Periods	20/10/07 → 23/10/07

OECD Zinātnes nozare

1.2 Datorzinātne un informātika

Piekļuve Dokumentiem

10.1109/FOCS.2007.4389507

Citi faili un saites

Saite uz publikāciju Scopus

Citēt šo

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. (gadā) Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 (lpp. 363-372). Zinātniskais raksts 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. (kur) 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, lpp. 363-372, 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, Providence, RI, Amerikas Savienotās Valstis, 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. u.c.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. IEEE Computer Society, 2007. lpp. 363-372 4389507 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Zinātniskās darbības rezultāts: Nodaļa grāmatā/enciklopēdijā/konferences krājumā › Konferences zinātniskais raksts › Pētniecība › koleģiāli recenzēts

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. (gadā) Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. IEEE Computer Society. 2007. lpp. 363-372. 4389507. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). doi: 10.1109/FOCS.2007.4389507