文章基本信息

标题：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