Grover's algorithm searches an unsorted database in roughly the square root of its size.
Lov Grover published the algorithm in 1996. A classical search may need to check about N entries in the worst case, whereas Grover’s quantum procedure finds a marked entry in about √N oracle queries. Its advantage is quadratic rather than exponential, but it applies broadly to unstructured search problems.
The algorithm uses a quantum oracle to identify the desired item and a diffusion operation to increase the marked state’s amplitude. Repeating these steps makes measurement increasingly likely to return the target. The number of iterations must be chosen carefully; too many can reduce the success probability.
Grover’s algorithm is often confused with Shor’s algorithm. Shor’s algorithm targets integer factorization and discrete logarithms, while Grover’s algorithm addresses search and related tasks. For an unsorted database, no quantum algorithm can improve the query complexity beyond the square-root scale in the usual black-box model.