Tight bounds on quantum searching
arXiv:quant-ph/9605034 · 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 recent 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. Using techniques from Shor's quantum factoring algorithm in addition to Grover's approach, we introduce a new technique for approximate quantum counting, which allows to estimate the number of solutions. Finally we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm nearly comes within a factor 2 of being optimal in terms of the number of probes required in the table.
8 pages, LaTeX2e, PhysComp 96 submission
Cited by in corpus (185)
- Quantum algorithms: an overview
- Grover's quantum searching algorithm is optimal
- Information and Computation: Classical and Quantum Aspects
- Experimental Demonstration of Blind Quantum Computing
- Quantum reinforcement learning
- Quantum-assisted and Quantum-based Solutions in Wireless Systems
- Search via Quantum Walk
- The General Quantum Interference Principle and the Duality Computer
- Complete 3-Qubit Grover Search on a Programmable Quantum Computer
- Fixed-point quantum search with an optimal number of queries
- Quantum attacks on Bitcoin, and how to protect against them
- Quantum speedup for active learning agents
- Quantum Computing with NMR
- Implementation of Grover's Quantum Search Algorithm in a Scalable System
- Experimental quantum speed-up in reinforcement learning agents
- Implementation of quantum search algorithm using classical Fourier optics
- On Arbitrary Phases in Quantum Amplitude Amplification
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- Grover's search algorithm: An optical approach
- Phase matching in quantum searching
- Quantum Algorithm for Linear Regression
- Quantum Search on Bounded-Error Inputs
- Quantum Algorithm Implementations for Beginners
- Speed-up via Quantum Sampling
- Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
- Calculating the Thermal Rate Constant with Exponential Speed-Up on a Quantum Computer
- Quantum query complexity of some graph problems
- Quantum SDP-Solvers: Better upper and lower bounds
- Hamiltonian Simulation with Optimal Sample Complexity
- Effects of Noisy Oracle on Search Algorithm Complexity
- Quantum searches on highly symmetric graphs
- Improved Bounds on Quantum Learning Algorithms
- Time-Space Complexity of Quantum Search Algorithms in Symmetric Cryptanalysis
- Accuracy vs run time in adiabatic quantum search
- Grover search with pairs of trapped ions
- A Review on Quantum Search Algorithms
- An entanglement monotone derived from Grover's algorithm
- Approximate quantum counting on an NMR ensemble quantum computer
- Experimental realization of a fetching algorithm in a 7 qubit NMR quantum computer
- The Measure-and-Reprogram Technique 2.0: Multi-Round Fiat-Shamir and More
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Single quantum querying of a database
- A Family of Grover's Quantum Searching Algorithms
- Tradeoffs in the Quantum Search Algorithm
- Grover's Quantum Search Algorithm for an Arbitrary Initial Mixed State
- Geometric Strategy for the Optimal Quantum Search
- Local copying and local discrimination as a study for non-locality of a set
- Implementation of efficient quantum search algorithms on NISQ computers
- A quantum genetic algorithm with quantum crossover and mutation operations
- Quantum anomaly detection in the latent space of proton collision events at the LHC
- Generalized Quantum Search with Parallelism
- Applying Grover's Algorithm to Hash Functions: A Software Perspective
- Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection
- Grover's algorithm in a four-qubit silicon processor above the fault-tolerant threshold
- Fast Quantum Search Algorithms in Protein Sequence Comparison - Quantum Biocomputing
- Experimental requirements for Grover's algorithm in optical quantum computation
- Number Partitioning with Grover's Algorithm in Central Spin Systems
- Control of non-controllable quantum systems: A quantum control algorithm based on Grover iteration
- Quantum algorithm for Feynman loop integrals
- Comprehensive characterization of three-qubit Grover search algorithm on IBM's 127-qubit superconducting quantum computers
- Prospect of using Grover's search in the noisy-intermediate-scale quantum-computer era
- Experimental implementation of local adiabatic evolution algorithms by an NMR quantum information processor
- Critically damped quantum search
- Geometric Algebra and Information Geometry for Quantum Computational Software
- Quantum Searching via Entanglement and Partial Diffusion
- Quantum Computation of a Complex System : the Kicked Harper Model
- Decoherence on Grover's quantum algorithm: perturbative approach
- On the adiabatic condition and the quantum hitting time of Markov chains
- Exponential Separation of Quantum and Classical Online Space Complexity
- A Grover search-based algorithm for the list coloring problem
- Error tolerance in an NMR Implementation of Grover's Fixed-Point Quantum Search Algorithm
- Fetching marked items from an unsorted database in NMR ensemble computing
- Finding structural anomalies in star graphs: A general approach
- A Hybrid Quantum Encoding Algorithm of Vector Quantization for Image Compression
- Threshold-Based Quantum Optimization
- Optimization of Partial Search
- Quantum mechanics helps in learning for more intelligent robot
- An optimized quantum minimum searching algorithm with sure-success probability and its experiment simulation with Cirq
- On the insecurity of quantum Bitcoin mining
- Quantum Chaos and Quantum Algorithms
- Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
- A Lower Bound for Quantum Phase Estimation
- Robust Logic Gates and Realistic Quantum Computation
- Faster quantum mixing for slowly evolving sequences of Markov chains
- Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
- Cryptographic One-way Function Based on Boson Sampling
- Realization of generalized quantum searching using nuclear magnetic resonance
- Quantum search on noisy intermediate-scale quantum devices
- Deterministic quantum search with adjustable parameters: implementations and applications
- Quest for Fast Partial Search Algorithm
- A Tool For Debugging Quantum Circuits
- The quantum query complexity of read-many formulas
- A Quantum-Search-Aided Dynamic Programming Framework for Pareto Optimal Routing in Wireless Multihop Networks
- Quantum Counterfeit Coin Problems
- Quantum algorithm to distinguish Boolean functions of different weights
- Quantum Annealing - Foundations and Frontiers
- Trajectory optimization using quantum computing
- Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
- A General SU(2) Formulation for Quantum Searching with Certainty
- Finding Small and Large k-Clique Instances on a Quantum Computer
- Group Theoretical Formulation of Quantum Partial Search Algorithm
- Fixed-point Quantum Search for Different Phase Shifts
- Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems
- Quantum-accelerated constraint programming
- Analysis of Grover's quantum search algorithm as a dynamical system
- Classical Artificial Neural Network Training Using Quantum Walks as a Search Procedure
- A Query-based Quantum Eigensolver
- Quantum Algorithms for String Processing
- A Framework for Distributed Quantum Queries in the CONGEST Model
- Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
- A General Phase Matching Condition for Quantum Searching Algorithm
- Cellular Structures for Computation in the Quantum Regime
- An Investigation on Support Vector Clustering for Big Data in Quantum Paradigm
- Using Quantum Computers to Speed Up Dynamic Testing of Software
- A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
- Modified Grover's algorithm for an expectation value quantum computer
- Quantum Computing for Software Engineering: Prospects
- Quantum-accessible reinforcement learning beyond strictly epochal environments
- Quantum Computation of Eigenvalues within Target Intervals
- Algebraic analysis of quantum search with pure and mixed states
- Performance analysis of a hybrid agent for quantum-accessible reinforcement learning
- Quantum Speedup of the Dispersion and Codebook Design Problems
- Quantum Probabilistic Subroutines and Problems in Number Theory
- Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs
- Spectral implementation of some quantum algorithms by one- and two-dimensional nuclear magnetic resonance
- The Precise Formula in a Sine Function Form of the norm of the Amplitude and the Necessary and Sufficient Phase Condition for Any Quantum Algorithm with Arbitrary Phase Rotations
- Quantum Portfolios
- Reconstructing Strings from Substrings with Quantum Queries
- Quantum search with resonances
- Quantum computation of multifractal exponents through the quantum wavelet transform
- Circuit Design for Clique Problem and Its Implementation on Quantum Computer
- Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
- Error Avoiding Quantum Codes and Dynamical Stabilization of Grover's Algorithm
- Grover's algorithm on a Feynman computer
- Quantum Optimization for Combinatorial Searches
- Interference versus success probability in quantum algorithms with imperfections
- Quantum Algorithm for Lexicographically Minimal String Rotation
- Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
- Amplitude Amplification for Optimization via Subdivided Phase Oracle
- Searches on star graphs and equivalent oracle problems
- Higher order perturbation theory for decoherence in Grover's algorithm
- Why adiabatic quantum annealing is unlikely to yield speed-up
- Quantum density peak clustering
- A classical limit of Grover's algorithm induced by dephasing: Coherence vs entanglement
- Implementation of Grover search algorithm with Josephson charge qubits
- Test-State Approach to the Quantum Search Problem
- Performance of Equal Phase-Shift Search for One Iteration
- Quantum algorithm for exact Monte Carlo sampling
- Quantifying Grover speed-ups beyond asymptotic analysis
- Hilbert Space Average Method and adiabatic quantum search
- Fixed-point quantum continuous search algorithm with optimal query complexity
- Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security
- State preparation based on Grover's algorithm in the presence of global information about the state
- Quantum Oracles in Terms of Universal Gate Set
- Cryptography in a Quantum World
- Complementary-multiphase quantum search for all numbers of target items
- Quantum Timing and Synchronization Problems
- Query complexity for searching multiple marked states from an unsorted database
- Grover's Quantum Search Algorithm and Diophantine Approximation
- Near-deterministic quantum search algorithm without phase design
- Error-run-time trade-off in the adiabatic approximation beyond scaling relations
- Basic quantum subroutines: finding multiple marked elements and summing numbers
- Quantum Motif Clustering
- On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
- Formulation of the Electric Vehicle Charging and Routing Problem for a Hybrid Quantum-Classical Search Space Reduction Heuristic
- -symmetric mapping of three states and its implementation on a cloud quantum processor
- Quantum Lower Bounds by Sample-to-Query Lifting
- End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
- Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
- Implementation of quantum algorithms with resonant interactions
- Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma
- The Quantum Locker Puzzle
- Quantum algorithm for unstructured search of ranked targets
- Quantum Mechanical Search and Harmonic Perturbation
- Robust Quantum Circuit for Clique Problem with Intermediate Qudits
- Gaussian Amplitude Amplification for Quantum Pathfinding
- Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm
- Linguistic Predictability and Search Complexity: How Linguistic Redundancy Constraints the Landscape of Classical and Quantum Search
- Quantum Computation
- Function Maximization with Dynamic Quantum Search
- Topological order on the Bloch sphere
- Improved Quantum Query Complexity on Easier Inputs
- Quantum algorithms and approximating polynomials for composed functions with shared inputs
- Grover Energy Transfer at Relativistic Speeds