00984nas a2200145 4500008004100000245009600041210006900137260001500206520048900221100002300710700002300733700001900756700001900775856004400794 2007 eng d00aEvery NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
0 aEvery NAND formula of size N can be evaluated in time N 12o1 on c2007/03/023 a For every NAND formula of size N, there is a bounded-error N^{1/2+o(1)}-time
quantum algorithm, based on a coined quantum walk, that evaluates this formula
on a black-box input. Balanced, or ``approximately balanced,'' NAND formulas
can be evaluated in O(sqrt{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.
1 aChilds, Andrew, M.1 aReichardt, Ben, W.1 aSpalek, Robert1 aZhang, Shengyu uhttp://arxiv.org/abs/quant-ph/0703015v3