Fixed-point quantum search with an optimal number of queries

Abstract

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 $\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$.

4 pages plus references, 2 figures

References in corpus (1)

• Quantum error correction of systematic errors using a quantum search framework

Cited by in corpus (5)

• Quantum-enhanced machine learning
• Hamiltonian Simulation by Uniform Spectral Amplification
• Geometric Algebra and Information Geometry for Quantum Computational Software
• Fixed-Point Adiabatic Quantum Search
• Site-by-site quantum state preparation algorithm for preparing vacua of fermionic lattice field theories