Volume 4 (2008) Article 8 pp. 169-190
A Quantum Algorithm for the Hamiltonian NAND Tree
by
Published: December 23, 2008
Discrete-Query Quantum Algorithm for NAND Trees" by Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo, June 28, 2009
[PDF (315K)]    [PS (477K)]    [PS.GZ (119K)]
[Source ZIP]
Keywords: quantum computing, NAND trees, and-or trees, game trees, quantum walk
ACM Classification: F.1.2, F.2.2
AMS Classification: 68Q10, 68Q17

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 $\sqrt{N}$. We also show a lower bound of $\Omega (\sqrt{N})$ for the NAND tree problem in the Hamiltonian oracle model.