文章基本信息
- 标题：Discrete-Query Quantum Algorithm for NAND Trees
- 本地全文：下载
- 作者：Andrew M. Childs ; Richard Cleve ; Stephen P. Jordan 等
- 期刊名称：Theory of Computing
- 印刷版ISSN：1557-2862
- 电子版ISSN：1557-2862
- 出版年度：2009
- 卷号：5
- DOI：10.4086/toc.2009.v005a005
- 出版社：University of Chicago
- 摘要：
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. - 关键词：quantum computation; quantum query complexity; formula evaluation; quantum walk; Hamiltonian simulation
