Volume 5 (2009) Article 5 pp. 119-123 [NOTE]

Discrete-Query Quantum Algorithm for NAND Trees

by Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo

Received: September 30, 2008
Published: July 1, 2009

Download article from ToC site:
[PDF (158K)]    [PS (409K)]    [PS.GZ (127K)]    [PS.ZIP (127K)]
[Source ZIP]
Misc.:
[About the Author(s)] [HTML Bibliography] [BibTeX]
Keywords: quantum computation, quantum query complexity, formula evaluation, quantum walk, Hamiltonian simulation
Categories: note, quantum, quantum walk, query complexity, formulas, Boolean formulas
ACM Classification: F.1.2, F.2.2
AMS Classification: 68Q10, 81P68

Abstract: [Plain Text Version]

This is a comment on the article “A Quantum Algorithm for the Hamiltonian NAND Tree” by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, Theory of Computing 4 (2008) 169--190. That paper gave a quantum algorithm for evaluating nand trees with running time O(√N) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using N½ + o(1) queries in the conventional (discrete) quantum query model.

DOI: 10.4086/toc.2009.v005a005
© 2009 Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo
Creative Commons License Licensed under a Creative Commons Attribution License