Discrete-query quantum algorithm for NAND trees

TitleDiscrete-query quantum algorithm for NAND trees
Publication TypeJournal Article
Year of Publication2009
AuthorsChilds, AM, Cleve, R, Jordan, SP, Yeung, D
JournalTheory of Computing
Volume5
Issue1
Pages119 - 123
Date Published2009/07/01
Abstract

Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for
evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian
query model. In this note, we point out that their algorithm can be converted
into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional
quantum query model, for any fixed epsilon > 0.
URLhttp://arxiv.org/abs/quant-ph/0702160v1
DOI10.4086/toc.2009.v005a005
Short TitleTheory of Comput.