Source-linked AI summary
Fixed-point quantum search with an optimal number of queries
Theodore J. Yoder, Guang Hao Low, Isaac L. Chuang
TL;DR
Grover search offers a quadratic speedup, but its iteration count depends on the unknown target-state fraction and can overcook the state. The paper constructs fixed-point amplitude amplification with tunable bounded error, while retaining optimal query scaling and avoiding overcooking.
Problem
Grover’s search can overcook the state when the number of marked items is unknown, while existing fixed-point algorithms lose the quadratic speedup.
Method
The authors use the polynomial method to tune phases in generalized Grover reflections, constructing sequences with adjustable error δ and fixed-point behavior.
Results
The fixed-point search cannot be overcooked and achieves optimal time scaling, providing a quadratic advantage over classical unordered search.
Takeaways & Limitations
The algorithm can serve as a subroutine for amplitude amplification tasks without estimating the correct iteration count or remaking the initial state.
Takeaways & Limitations
The π/3-algorithm special case at δ = 0 has classical query scaling, so the stated optimality does not extend to that case.
Abstract
from arXiv · showhide
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 $λ$.