Exact quantum lower bound for Grover's problem

Catalin Dohotaru, Peter Hoyer

One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Gr…