TY - JOUR
T1 - Discrete-query quantum algorithm for NAND trees
JF - Theory of Computing
Y1 - 2009
A1 - Andrew M. Childs
A1 - Richard Cleve
A1 - Stephen P. Jordan
A1 - David Yeung
AB - 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.
VL - 5
U4 - 119 - 123
UR - http://arxiv.org/abs/quant-ph/0702160v1
CP - 1
J1 - Theory of Comput.
U5 - 10.4086/toc.2009.v005a005
ER -