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 (14)

• Quantum-enhanced machine learning
• Experimental quantum speed-up in reinforcement learning agents
• 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
• A framework for optimal quantum spatial search using alternating phase-walks
• Fixed-point quantum continuous search algorithm with optimal query complexity
• Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
• Quantum algorithm for solving generalized eigenvalue problems with application to the Schrödinger equation
• Quantum Search with Prior Knowledge
• Grover's algorithm for image edge detection
• Reasoning about Recursive Quantum Programs
• Quantum spatial best-arm identification via quantum walks