Theory of Computing
-------------------
Title : A Quantum Algorithm for the Hamiltonian NAND Tree
Authors : Edward Farhi, Jeffrey Goldstone, and Sam Gutmann
Volume : 4
Number : 8
Pages : 169-190
URL : https://theoryofcomputing.org/articles/v004a008
Abstract
--------
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.