Grover's algorithm

Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N^-1/2) time. It was invented by Grover in 1996.

Classically, searching an unsorted database requires a linear search, which is O(N). Grover's algorithm provides "only" quadratic speedup, unlike other quantum algorithms which provide exponential speedup over their classical counterparts. However, it is the fastest possible quantum algorithm for searching an unsorted database, and even quadratic speedup is considerable when N is large.

Grover's algorithm can be used for mean and median estimation, and solving the collision problem. It can be used to solve NP-complete problems by performing exhaustive searches over all possible solutions.

Below, we present the basic form of Grover's algorithm, which searches for a single matching entry. The algorithm can be further optimized if there is more than one matching entry and the number of matches is known beforehand.

Procedure

Consider an unsorted database with N entries. The algorithm requires an N-dimensional state space H, which can be supplied by log₂N qubits.

Number the database entries 0, 1, ... N-1. Choose an observable Ω acting on H. By the spectral theorem, we can construct an orthonormal basis of eigenkets {|0>,|1>,...|N-1>}. The eigenvalues {λ₀,λ₁,...,λ_N-1} label distinct database entries. We wish to find the label |ω> for the database entry matching our search criterion.

We are provided with a unitary operator U_ω which compares database entries with our search criterion. The algorithm does not specify how this subroutine works, but it must be a quantum subroutine that works with superpositions of states, and it must have the following effects on the label kets:

U_ω |ω> = - |ω>

U_ω |x> = |x>     x ≠ ω

The steps of the Grover algorithm are:

1. Initialize the system to the state

   |s> = N^-1/2 Σ_x |x>

2. Perform the following "Grover iteration" r(N) times.
   r(N) is described below; for N>>1, r ≈ πN^1/2/4.
   1. 1. Apply the operator U_ω
   1. 1. Apply the operator U_s = 2 |s> <s| - I
3. Perform the measurement Ω. The measurement result will be λ_ω with probability approaching 1 for N >> 1. From λ_ω, ω may be obtained.

Explanation of the Algorithm

Our initial state is

|s> = N^-1/2 Σ_x |x>

Consider the plane spanned by |s> and |ω>. Let |ω^×> be a ket in this plane perpendicular to |ω>. Since |ω> is one of the basis vectors, the overlap is

<ω|s> = N^-1/2

In geometric terms, there is an angle (π/2 - θ) between |ω> and |s>, where θ is given by:

cos (π/2 - θ) = N^-1/2

sin θ = N^-1/2

The operator U_ω is a reflection about the vector |ω^×>. The operator U_s is a reflection about the vector |s>. It is straightforward to check that the operator U_sU_ω, applied during each Grover iteration, step rotates the state vector by an angle 2θ toward |ω>.

We need to stop when the state vector passes close to |ω>; after this, subsequent iterations rotate the state vector away from |ω>, reducing the probability of obtaining the correct answer. The number of times to iterate is given by r. In order to align the state vector exactly with |ω>, we need:

π/2 - θ = 2θr

r = (π/θ - 2)/4

However, r must be an integer, so generally we can only set r to be the integer closest to (π/θ - 2)/4. The angle between |ω> and the final state vector is O(θ), so the probability of obtaining the wrong answer is O(1 - cos²θ) = O(sin²θ).

For N >> 1, θ ≈ N^-1/2, so

r ≈ π N^1/2 / 4

Furthermore, the probability of obtaining the wrong answer becomes O(1/N), which goes to zero for large N.