Volume 5 (2009) Article 5 pp. 119-123 [Note]
Discrete-Query Quantum Algorithm for NAND Trees
This is a comment on the article “A Quantum Algorithm for the Hamiltonian NAND Tree” by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, Theory of Computing 4 (2008) 169-190. That paper gave a quantum algorithm for evaluating nand trees with running time $O(\sqrt{N})$ in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using $N^{1/2 + o(1)}$ queries in the conventional (discrete) quantum query model.