Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA.
Phys Rev Lett. 2014 Nov 21;113(21):210501. doi: 10.1103/PhysRevLett.113.210501. Epub 2014 Nov 18.
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 λ.
格罗弗的量子搜索及其推广，量子振幅放大，为各种任务提供了比经典算法高出二次方的优势，但如果事先不知道初始状态中有多少比例 λ 由目标状态组成，就很难使用。相比之下，定点搜索算法只需要这个分数的可靠下限，但作为结果，失去了使 Grover 算法如此吸引人的非常二次方的优势。在这里，我们提供了第一个版本的振幅放大，它在不牺牲量子加速的情况下实现了定点行为。我们的结果包含了对失败概率的可调上限，并且对于给定数量的查询，保证在最广泛的 λ 范围内满足该上限。
