%0 Journal Article
%D 2007
%T Every NAND formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer
%A Andrew M. Childs
%A Ben W. Reichardt
%A Robert Spalek
%A Shengyu Zhang
%X 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.
%8 2007/03/02
%G eng
%U http://arxiv.org/abs/quant-ph/0703015v3