Theory of Computing
-------------------
Title : Discrete-Query Quantum Algorithm for NAND Trees
Authors : Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo
Volume : 5
Number : 5
Pages : 119-123
URL : https://theoryofcomputing.org/articles/v005a005
Abstract
--------
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.