Every NAND formula on N variables can be evaluated in time O(N^{1/2+eps})
Andrew M. Childs, Ben W. Reichardt, Robert Špalek, Shengyu Zhang · arXiv (Cornell University) · 2007
For every NAND formula on N variables, there is a bounded-error O(N^{1/2+eps})-time quantum algorithm that evaluates this formula on a black-box input, for eps>0 an arbitrarily small constant. It follows that the (2-eps)-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.