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

arXiv comment4 pages plus references, 2 figures

References in corpus (10)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Strengths and Weaknesses of Quantum Computing
• Tight bounds on quantum searching
• A different kind of quantum search
• On Arbitrary Phases in Quantum Amplitude Amplification
• Phase matching in quantum searching
• Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla
• Quantum error correction of systematic errors using a quantum search framework
• Quantum rejection sampling
• Nested composite NOT gates for quantum computation

Cited by in corpus (115)

• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum-enhanced machine learning
• Experimental quantum speed-up in reinforcement learning agents
• The methodology of resonant equiangular composite quantum gates
• Quantum Algorithms for Simulating the Lattice Schwinger Model
• Noisy intermediate-scale quantum computers
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Hamiltonian Simulation with Optimal Sample Complexity
• Minimizing estimation runtime on noisy quantum computers
• Time-Space Complexity of Quantum Search Algorithms in Symmetric Cryptanalysis
• Deterministic Grover search with a restricted oracle
• Depth optimization of quantum search algorithms beyond Grover's algorithm
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Exponential quantum speedup in simulating coupled classical oscillators
• Quantum enhancements for deep reinforcement learning in large spaces
• Efficient quantum computation of molecular forces and other energy gradients
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Finding spin-glass ground states using quantum walks
• Probabilistic Nonunitary Gate in Imaginary Time Evolution
• Hamiltonian Simulation by Uniform Spectral Amplification
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Finding Angles for Quantum Signal Processing with Machine Precision
• Geometric Algebra and Information Geometry for Quantum Computational Software
• Sampling on NISQ Devices: "Who's the Fairest One of All?"
• Fast Black-Box Quantum State Preparation
• Amplitude Estimation from Quantum Signal Processing
• Fixed-Point Adiabatic Quantum Search
• Quantum algorithm for Neighborhood Preserving Embedding
• Repeat-Until-Success circuits with fixed-point oblivious amplitude amplification
• Dynamic Grover Search: Applications in Recommendation systems and Optimization problems
• Generalized Grover's algorithm for multiple phase inversion states
• Threshold-Based Quantum Optimization
• Steering Quantum Dynamics via Bang-Bang Control: Implementing optimal fixed point quantum search algorithm
• Bootstrap Embedding on a Quantum Computer
• Faster quantum mixing for slowly evolving sequences of Markov chains
• Perturbation theory with quantum signal processing
• Deterministic quantum search with adjustable parameters: implementations and applications
• State Preparation Boosters for Early Fault-Tolerant Quantum Computation
• Analog quantum algorithms for the mixing of Markov chains
• Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
• Quantum spectral clustering algorithm for unsupervised learning
• Quantum Amplitude Amplification Operators
• Environment-assisted analog quantum search
• Deterministic spatial search using alternating quantum walks
• Quantum Computing by Cooling
• A Query-based Quantum Eigensolver
• Fair Sampling Error Analysis on NISQ Devices
• A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles
• Complementarity between Success Probability and Coherence in Grover Search Algorithm
• Site-by-site quantum state preparation algorithm for preparing vacua of fermionic lattice field theories
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Quantum-accessible reinforcement learning beyond strictly epochal environments
• Quantum Speedup of the Dispersion and Codebook Design Problems
• Performance analysis of a hybrid agent for quantum-accessible reinforcement learning
• Quantum Computation of Eigenvalues within Target Intervals
• Weakly measured while loops: peeking at quantum states
• Generalized Quantum PageRank Algorithm with Arbitrary Phase Rotations
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• Black-Box Quantum State Preparation with Inverse Coefficients
• Quantum algorithm for estimating volumes of convex bodies
• Hybrid divide-and-conquer approach for tree search algorithms
• Improved amplitude amplification strategies for the quantum simulation of classical transport problems
• Circuit Design for Clique Problem and Its Implementation on Quantum Computer
• Automatic Post-selection by Ancillae Thermalisation
• Sparse random Hamiltonians are quantumly easy
• Amplitude Amplification for Optimization via Subdivided Phase Oracle
• Quantum mean estimation for lattice field theory
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Characterization, synthesis, and optimization of quantum circuits over multiple-control $\text{Z}$-rotation gates: A systematic study
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
• Optimization of probabilistic quantum search algorithm with a priori information
• Noise-tolerant quantum speedups in quantum annealing without fine tuning
• Quantum Dynamic Programming
• A framework for optimal quantum spatial search using alternating phase-walks
• Robust quantum minimum finding with an application to hypothesis selection
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
• On Quantum Circuits for Discrete Graphical Models
• Modular quantum signal processing in many variables
• Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
• Complementary-multiphase quantum search for all numbers of target items
• Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States
• Fixed-point quantum continuous search algorithm with optimal query complexity
• Applying Grover's algorithm to AES: quantum resource estimates
• Quantum eigenvalue processing
• Design for implementation of discrete-time quantum walk with circulant matrix on graph by optical polarizing elements
• Near-deterministic quantum search algorithm without phase design
• Sample-based Hamiltonian and Lindbladian simulation: Non-asymptotic analysis of sample complexity
• QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
• Quantum and Randomised Algorithms for Non-linearity Estimation
• Parallel Quantum Signal Processing Via Polynomial Factorization
• No fixed-point guarantee of Nash equilibrium in quantum games
• Robust Quantum Circuit for Clique Problem with Intermediate Qudits
• Quantum Algorithm for Online Convex Optimization
• Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma
• Performance of Grover's search algorithm with diagonalizable collective noises
• Quantum Search with Prior Knowledge
• Quantum algorithm for unstructured search of ranked targets
• Quantum algorithm for solving generalized eigenvalue problems with application to the Schrödinger equation
• Quantum Speedup for Nonreversible Markov Chains
• Efficient Quantum Algorithms related to Autocorrelation Spectrum
• Quantum spatial best-arm identification via quantum walks
• Exact quantum search based on analytical multiphase matching for known number of target items and the experimental demonstration on IBM Q
• Grover's algorithm for image edge detection
• Quantum Heaviside Eigen Solver
• Reasoning about Recursive Quantum Programs
• Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$
• Explicit decoders using fixed-point amplitude amplification based on QSVT
• Quantum Speedups for Multiproposal MCMC
• Leveraging Unknown Structure in Quantum Query Algorithms