A Quantum Algorithm for the Hamiltonian NAND Tree
Edward Farhi, Jared V. Goldstone, Sam Gutmann · arXiv (Cornell University) · 2007
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 run time proportional to sqrt N. We also show a lower bound of sqrt N for the NAND tree problem in the Hamiltonian oracle model.