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

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)]    [PS.GZ (119K)]    [PS.ZIP (119K)]
[Source ZIP]
Misc.:
[About the Author(s)] [HTML Bibliography] [BibTeX]
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.

DOI: 10.4086/toc.2008.v004a008
© 2008 Edward Farhi, Jeffrey Goldstone, and Sam Gutmann
Creative Commons License Licensed under a Creative Commons License