Received: June 6, 2008
Published: December 23, 2008
DOI: 10.4086/toc.2008.v004a008
Abstract: [Plain Text Version]
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 √N. We also show a lower bound of Ω(√N) for the NAND tree problem in the Hamiltonian oracle model.