pdf icon
Volume 4 (2008) Article 8 pp. 169-190
A Quantum Algorithm for the Hamiltonian NAND Tree
Received: June 6, 2008
Published: December 23, 2008
Comments and updates on this paper:
``Discrete-Query Quantum Algorithm for NAND Trees" by Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo, June 28, 2009
Download article from ToC site:
[PDF (315K)] [PS (477K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: quantum computing, NAND trees, and-or trees, game trees, quantum walk
Categories: quantum computing, quantum walk, NAND tree, game tree, commented on
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.