title: Fixed-point quantum search with an optimal number of queries.
abstract: 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 λ.
authors.affiliation: Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA.
authors.forename: Theodore J
authors.initials: TJ
authors.lastname: Yoder
authors.affiliation: Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA.
authors.forename: Guang Hao
authors.initials: GH
authors.lastname: Low
authors.affiliation: Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA.
authors.forename: Isaac L
authors.initials: IL
authors.lastname: Chuang