Fixed-Point Quantum Search with an Optimal Number of Queries
Fixed-Point Quantum Search with an Optimal Number of Queries
复制标题
DOI：
10.1103/physrevlett.113.210501
复制
发表时间：
2014-11-18
影响因子：
8.6
通讯作者：
Chuang, Isaac L.
中科院分区：
文献类型：
--
作者：
Yoder, Theodore J.;Low, Guang Hao;Chuang, Isaac L.
格罗弗的量子搜索及其推广，量子幅度放大，为一系列不同的任务提供了比经典算法更好的二次方优势，但在事先不知道初始态的多少波长由目标态组成的情况下，使用起来很棘手。相比之下，定点搜索算法只需要这个分数的可靠下限，但结果是失去了使Grover算法如此吸引人的非常二次优势。在这里，我们提供了第一个版本的幅度放大，它在不牺牲量子加速比的情况下实现了定点行为。我们的结果包含了一个关于失败概率的可调界限，并且对于给定数量的Oracle查询，保证在最大可能的lambda范围内满足该界限。
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 lambda 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 lambda.