Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

Ambainis, A.; Childs, A. M.; Reichardt, B. W.; Špalek, R.; Zhang, S.

doi:10.1137/080712167

Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

Consider the problem of evaluating an AND-OR formula on an N-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of t…