Site Tools


grover

Table of Contents

Grover

Grover's algorithm is a quantum search algorithm that finds a marked element in an unstructured database of items in queries. It was invented by Lov Grover in 1996 and provides a quadratic speedup over classical brute-force search, which requires queries in the worst case.

The algorithm works with a phase oracle that marks the target state by flipping its phase: if , and otherwise. Starting from the uniform superposition , repeated Grover iterations amplify the amplitude of until it can be measured with high probability.

Grover iteration

A single Grover iteration consists of two operations. First, the oracle flips the sign of the target state's amplitude. Second, the diffusion operator reflects the state about the uniform superposition, amplifying the target amplitude and suppressing all others.

Optimal number of iterations

Starting from , after Grover iterations the probability of measuring is where . The optimal number of iterations before measuring is , giving a success probability close to 1.

Optimality

Grover's algorithm is provably optimal: no quantum algorithm can search an unstructured database faster than queries. The quadratic speedup is therefore the best possible for unstructured search.

grover.md · Last modified: