Fixed-Point Quantum Search with an Optimal Number of Queries

作     者：Theodore J. Yoder Guang Hao Low Isaac L. Chuang 

作者机构：Massachusetts Institute of Technology Cambridge Massachusetts 02139 USA 

出 版 物：《Physical Review Letters》 (Phys Rev Lett)

年 卷 期：2014年第113卷第21期

页      面：210501-210501页

核心收录：

学科分类：07[理学] 0702[理学-物理学] 

基　　金：National Science Foundation, NSF, (1125846, 1111337) National Science Foundation, NSF 

主　　题：QUANTUM computing SEARCH algorithms POLYNOMIAL time algorithms UNITARY operators CHEBYSHEV systems 

摘      要：Grover’s quantum search and its generalization, quantum amplitude amplification, provide a quadratic advantage over classical algorithms for a diverse set of tasks but are tricky to use without knowing beforehand what fraction λ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction but, as a consequence, lose the very quadratic advantage that makes Grover’s algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of λ.