Tight Bounds on Quantum Searching

1998/06/01 by Michel Boyer, Gilles Brassard, Peter Høyer +1 · 71 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications

paper · doi:10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p

Abstract

We provide a tight analysis of Grover's algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Finally, we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm comes within 2.62% of being optimal.

Cited by

• Quantum Computing with NMR
• Quantum Computing and Data Processing for Frequent Itemset Mining
• Amplitude-amplified coherence detection and estimation
• Quantum Algorithm for Searching for the Longest Segment and the Largest Empty Rectangle
• Constraint-Optimal Driven Allocation for Scalable QEC Decoder Scheduling
• Resource Estimation for VQE on Small Molecules: Impact of Fermion Mappings and Hamiltonian Reductions
• Machine Learning by Adiabatic Evolutionary Quantum System
• Hybrid Quantum-Classical Detection for RIS-Assisted SC-FDE via Grover Adaptive Search
• Experimental Demonstration of Blind Quantum Computing
• Quantum Search in Superposed Quantum Lattice Gas Automata and Lattice Boltzmann Systems
• Reverse Supervision at Scale: Exponential Search Meets the Economics of Annotation
• End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
• Quantum Algorithm for Binary Vector Encoding and Retrieval Utilizing the Permutation Trick
• C2|Q>: A Robust Framework for Bridging Classical and Quantum Software Development
• Error tolerance in an NMR implementation of Grover’s fixed-point quantum search algorithm
• Control of non-controllable quantum systems: a quantum control algorithm based on Grover iteration
• Grover’s quantum search algorithm for an arbitrary initial mixed state
• Optimal phase change for a generalized Grover's algorithm
• Compressed Permutation Oracles
• Nested Grover's Algorithm for Tree Search
• Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking
• Traq: Estimating the Quantum Cost of Classical Programs
• Private Quantum Database
• Expressivity Limits in Quantum Walk-based Optimization
• Deterministic Quantum Search via Recursive Oracle Expansion
• A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Complexity of learning matchings and half graphs via edge queries
• Quantum reinforcement learning in dynamic environments
• Demonstration of measurement-free universal fault-tolerant quantum computation
• Weyl's Relations, Integrable Matrix Models and Quantum Computation
• Optimal quantum sampling on distributed databases
• Toward Entailment Checking: Explore Eigenmarking Search
• Hybrid Quantum-Classical Maximum-Likelihood Detection via Grover-based Adaptive Search for RIS-assisted Broadband Wireless Systems
• A Black-box Testing Framework for Oracle Quantum Programs
• Quantum algorithms: an overview
• Information and computation: Classical and quantum aspects
• Realization of generalized quantum searching using nuclear magnetic resonance
• Algebraic analysis of quantum search with pure and mixed states
• Quantum Reinforcement Learning
• Interference versus success probability in quantum algorithms with imperfections
• Speedup via quantum sampling
• Calculating the thermal rate constant with exponential speedup on a quantum computer
• Grover’s quantum search algorithm and Diophantine approximation
• Quantum Mechanics Helps in Learning for More Intelligent Robots
• Exact quantum algorithm to distinguish Boolean functions of different weights
• Spatial Search by Nonlinear Quantum Walk
• Quantum lower bounds by polynomials
• Group Theoretical Formulation of a Quantum Partial Search Algorithm
• Cryptography in a Quantum World
• Optimal and Deterministic Quantum Search on the Simplex of Complete Graphs
• Implementation of Grover’s quantum search algorithm in a scalable system
• Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
• Algorithms on ensemble quantum computers. [europepmc]
• Quantum exhaustive key search with simplified-DES as a case study. [europepmc]
• Complete 3-Qubit Grover search on a programmable quantum computer. [europepmc]
• Committing to quantum resistance: a slow defence for Bitcoin against a fast quantum computing attack. [europepmc]
• Quantum-accessible reinforcement learning beyond strictly epochal environments. [europepmc]
• Implementation and analysis of quantum computing application to Higgs boson reconstruction at the large Hadron Collider. [europepmc]
• Robust Quantum Search with Uncertain Number of Target States. [europepmc]
• Quantum Density Peak Clustering Algorithm. [europepmc]
• Quantum-effective exact multiple patterns matching algorithms for biological sequences. [europepmc]
• Gaussian Amplitude Amplification for Quantum Pathfinding. [europepmc]
• Quantum Computing Approaches for Vector Quantization-Current Perspectives and Developments. [europepmc]
• Suppression of Crosstalk in Quantum Circuit Based on Instruction Exchange Rules and Duration. [europepmc]
• A concept of controlling Grover diffusion operator: a new approach to solve arbitrary Boolean-based problems. [europepmc]
• Characterizing Grover search algorithm on large-scale superconducting quantum computers. [europepmc]
• Grover's algorithm in a four-qubit silicon processor above the fault-tolerant threshold. [europepmc]
• Demonstration of measurement-free universal logical quantum computation. [europepmc]
• Nested Grover's Algorithm for Tree Search. [europepmc]
• Inverse Problems, Constraint Satisfaction, Reversible Logic, Invertible Logic and Grover Quantum Oracles for Practical Problems [europepmc]

Related

• Strength and Weakness in Grover's Quantum Search Algorithm
• Is Quantum Search Practical?
• A Grover-based quantum search of optimal order for an unknown number of marked elements
• Quantum Database Searching by a Single Query
• Accelerated quantum search using partial oracles and Grover's algorithm