



@article {1255,
	title = {Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a  quantum computer
},
	year = {2007},
	month = {2007/03/02},
	abstract = {  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 {\textquoteleft}{\textquoteleft}approximately balanced,{\textquoteright}{\textquoteright} 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.
},
	url = {http://arxiv.org/abs/quant-ph/0703015v3},
	author = {Andrew M. Childs and Ben W. Reichardt and Robert Spalek and Shengyu Zhang}
}
