2014/09/30 by Theodore J. Yoder, Guang Hao Low, Isaac L. Chuang · 2 citations
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1103/physrevlett.113.210501
published as Phys. Rev. Lett. 113, 210501 (2014) · 4 pages plus references, 2 figures
arxiv created 2014/11/24 · arxiv updated 2014/11/26
Grover's quantum search and its generalization, quantum amplitude amplification, provide 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 λ.