A Caltech Library Service

Discrete-Query Quantum Algorithm for NAND Trees

Childs, Andrew M. and Cleve, Richard and Jordan, Stephen P. and Yonge-Mallo, David (2009) Discrete-Query Quantum Algorithm for NAND Trees. Theory of Computing, 5 (Articl). pp. 119-123. ISSN 1557-2862.

PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


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^[1/2 + o(1)] queries in the conventional (discrete) quantum query model.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2009 Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo. Licensed under a Creative Commons Attribution License. Received: September 30, 2008; published: July 1, 2009. AMC received support from the U.S. NSF under grant no. PHY-0456720, from the U.S. ARO under grant no. W911NF-05-1-0294, from Canada’s MITACS and NSERC, and from the U.S. ARO/DTO. RC received support from Canada’s CIAR, MITACS, NSERC, and the U.S. ARO/DTO. SPJ received support from the U.S. ARO/DTO’s QuaCGR program. DY received support from Canada’s MITACS, NSERC, and the U.S. ARO/DTO.
Funding AgencyGrant Number
U. S. AROW911NF-05-1-0294
Canada's Mathematics of Information Technology and Complex Systems (MITACS)UNSPECIFIED
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Subject Keywords:Quantum computation; quantum query complexity; formula evaluation; quantum; walk; Hamiltonian simulation
Issue or Number:Articl
Classification Code:ACM Classification: F.1.2, F.2.2 ; AMS Classification: 68Q10, 81P68
Record Number:CaltechAUTHORS:20091021-093352923
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:16421
Deposited By: Jason Perez
Deposited On:26 Oct 2009 20:26
Last Modified:03 Oct 2019 01:11

Repository Staff Only: item control page