Tight Bounds on Quantum Searching

作者：Michel Boyer, Gilles Brassard, Peter Høyer, Alain Tapp · 年份：1996 · 被引用次数：844 · 研究领域：Quantum Computing Algorithms and Architecture、Quantum Information and Cryptography、Quantum Mechanics and Applications

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. Keywords: Quantum computation. Searching. Lower bound. This research was presented at the Fourth Workshop on Physics and Computation, Boston, 23 November 1996. y D'epartement IRO, Universit'e de Montr'eal, C.P. 6128, succursale centre-ville, Montr'eal (Qu'ebec...