Volume 4 (2008) Article 8 pp. 169-190
A Quantum Algorithm for the Hamiltonian NAND Tree
by
Discrete-Query Quantum Algorithm for NAND Trees" by Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo, June 28, 2009
We give a quantum algorithm for the binary NAND tree problem in the Hamiltonian oracle model. The algorithm uses a continuous time quantum walk with a running time proportional to $\sqrt{N}$. We also show a lower bound of $\Omega (\sqrt{N})$ for the NAND tree problem in the Hamiltonian oracle model.