@article {1254,
title = {Discrete-query quantum algorithm for NAND trees},
journal = {Theory of Computing},
volume = {5},
year = {2009},
month = {2009/07/01},
pages = {119 - 123},
abstract = { Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for
evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian
query model. In this note, we point out that their algorithm can be converted
into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional
quantum query model, for any fixed epsilon > 0.
},
doi = {10.4086/toc.2009.v005a005},
url = {http://arxiv.org/abs/quant-ph/0702160v1},
author = {Andrew M. Childs and Richard Cleve and Stephen P. Jordan and David Yeung}
}