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

Discrete-Query Quantum Algorithm for NAND Trees

Received: September 30, 2008

Published: July 1, 2009

Published: July 1, 2009

**Keywords:**quantum computation, quantum query complexity, formula evaluation, quantum walk, Hamiltonian simulation

**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(\sqrt{N})$ in the Hamiltonian query model. In this note, we point
out that their algorithm can be converted into an algorithm using
$N^{1/2 + o(1)}$ queries in the conventional (discrete) quantum query
model.