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
- Eprint ID
- 16421
- Resolver ID
- CaltechAUTHORS:20091021-093352923
- PHY-0456720
- NSF
- W911NF-05-1-0294
- U. S. ARO
- Canada's Mathematics of Information Technology and Complex Systems (MITACS)
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- U. S. ARO/DTO
- Created
-
2009-10-26Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field