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
T2 - 48th Annual Symposium on Foundations of Computer Science, FOCS 2007
Y2 - 20 October 2007 through 23 October 2007
ER -