Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 1, 2009 | Published
Journal Article Open

Discrete-Query Quantum Algorithm for NAND Trees

Abstract

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.

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.

Attached Files

Published - Childs2009p6067Theory_Comput.pdf

Files

Childs2009p6067Theory_Comput.pdf
Files (162.2 kB)
Name Size Download all
md5:73cb93353f8773c1bc843b51a776c8cd
162.2 kB Preview Download

Additional details

Created:
August 21, 2023
Modified:
October 19, 2023