Premium
Tight Bounds on Quantum Searching
Author(s) -
Boyer Michel,
Brassard Gilles,
Høyer Peter,
Tapp Alain
Publication year - 1998
Publication title -
fortschritte der physik
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.469
H-Index - 71
eISSN - 1521-3978
pISSN - 0015-8208
DOI - 10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p
Subject(s) - quantum algorithm , simple (philosophy) , factoring , element (criminal law) , algorithm , quantum , quantum phase estimation algorithm , computer science , quantum sort , mathematics , search algorithm , discrete mathematics , quantum error correction , quantum mechanics , philosophy , physics , epistemology , finance , political science , law , economics
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.