Volume 4 (2008) Article 8 pp. 169-190

A Quantum Algorithm for the Hamiltonian NAND Tree

by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann

Received: June 6, 2008
Published: December 23, 2008
DOI: 10.4086/toc.2008.v004a008

Download article from ToC site:
[PS (469K)]    [PS.GZ (118K)]    [PS.ZIP (118K)]
[PDF (305K)]    [DVI (157K)]    [ZIP (117K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: quantum computing, NAND trees, and-or trees, game trees, quantum walk
Categories: quantum, quantum walk, NAND tree, game tree
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 √N. We also show a lower bound of Ω(√N) for the NAND tree problem in the Hamiltonian oracle model.