Grover's algorithm

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 are thought to 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.

Like all quantum computer algorithms, Grover's algorithm is probabilistic in the sense that it gives the correct answer with high probability. The probability of failure can be decreased by repeating the algorithm.

Although Grover's algorithm is often described as searching a database, it would be more accurate to describe it as inverting a function. If a function y=f(x) can be computed by an algorithm for a quantum computer, then Grover's algorithm can calculate x, given y. Grover's algorithm wouldn't typically be used to search for names in a phone book, but it could be used to search for a key that decrypts an encrypted message. If the function for computing f(x) is given as a black box, then Grover's algorithm is the fastest possible algorithm for inverting it.

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. This will result in considerable speedups over classical methods, but won't achieve polynomial runtime for NP-complete problems.

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 with N distinct eigenvalues. By the spectral theorem, we can construct an orthonormal basis of eigenkets {|0⟩,|1⟩,...|N-1⟩} (see bra-ket notation). 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_ω
      2. 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 at the hyperplane orthogonal to |ω⟩; for vectors in the plane spanned by |s⟩ and |ω⟩, it acts as a reflection at the line through |ω^×⟩. The operator U_s is a reflection at the line through |s>. Therefore, the state vector remains in the plane spanned by |s⟩ and |ω⟩ after each application of U_s and after each application of U_ω, and it is straighforward to check that the operator U_sU_ω of each Grover iteration step rotates the state vector by an angle of 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.

References:

• Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
• http://www.bell-labs.com/user/feature/archives/lkgrover/