Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Wiley eBooks

Tight Bounds on Quantum Searching

Michel Boyer, Gilles Brassard, Peter Høyer, Alain Tappa

Published Oct 12, 1999• 153 citations
Publisher

Abstract

This chapter contains sections titled: Abstract 1 Introduction 2 Overview of Grover's Algorithm 3 Finding a Unique Solution 4 The Case of Multiple Solutions 5 The Case t = N/4 6 Unknown Number of Solutions 7 An Improved Lower Bound 8 Conclusions and Future Directions Acknowledgements References
DOI
10.1002/3527603093.ch10

Related papers

Tight Bounds on Quantum Searching

Michel Boyer, Gilles Brassard, Peter Høyer +1 more

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.

arXiv:quant-ph/9605034•Fortschritte der Physik•Jun 1, 1998•1,338 citations

Searching in an Unsorted Database

Sándor Imre, Ferenc Balázs

This chapter contains sections titled: The Basic Grover Algorithm Quantum Counting Quantum Existence Testing Finding Extreme Values in an Unsorted Database The Generalized Grover Algorithm Further Reading

Wiley eBooks•Nov 19, 2004•0 citations

Quantum Algorithms

Julia Kempe

This chapter contains sections titled: Introduction Precursors Shor's Factoring Algorithm Grover's Algorithm Other Algorithms Recent Developments

Wiley eBooks•Nov 6, 2006•1 citation

Quantum Walk Search Algorithms

Richard J. Lipton, Kenneth W. Regan

This chapter contains sections titled: 15.1 Search in Big Graphs, 15.2 General Quantum Walk for Graph Search, 15.3 Specifying the Generic Walk, 15.4 Adding the Data, 15.5 Toolkit Theorem for Quantum Walk Search, 15.6 Grover Search as Generic Walk, 15.7 Element Distinctness, 15.8 Subgraph Triangle Incidence, 15.9 Finding a Triangle, 15.10 Evaluating Formulas and Playing Chess, 15.11 Problems, 15.12 Summary and Notes

•Jan 1, 2014•0 citations

Grover's quantum search algorithm

Samuel J. Lomonaco

This paper is a written version of a one hour lecture given on Lov Grover's database search algorithm. Table Of Contents 1 ... Problem Definition 2 ... The quantum mechanical perspective 3 ... Properties of the inversion I_|psi> 4 ... The method in Lov's "madness" 5 ... Summary of Grover's algorithm 6 ... An example of Grover's algorithm References

arXiv:quant-ph/0010040•Oct 10, 2000•5 citations

On Multi‐Particle Entanglement

Noah Linden, Sandu Popescu

This chapter contains sections titled: Abstract 1 Introduction 2 The Number of Parameters Needed to Describe Inequivalent States 2.1 Dimension of a General Orbit 2.2 A Single Spin 2.3 Two Spins 2.4 Three Spins 3 Invariants 3.1 Examples 3.2 General Case 4 Orbit Types 5 Conclusion Acknowledgements References

Wiley eBooks•Oct 12, 1999•16 citations
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.