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.
Consider an unsorted database with N entries. The algorithm requires an N-dimensional state space H, which can be supplied by log2N 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 {λ0,λ1,...,λ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:
Our initial state is
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:
For N>>1, θ ≈ N-1/2, so
References:
Procedure
The steps of the Grover algorithm are:
r(N) is described below; for N>>1, r ≈ πN1/2/4.
Explanation of the Algorithm
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
In geometric terms, there is an angle (π/2 - θ) between |ω⟩ and |s⟩, where θ is given by:
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 Us is a reflection at the line through |s>. Therefore, the state vector remains in the plane spanned by |s⟩ and |ω⟩ after each application of Us and after each application of Uω, and it is straighforward to check that the operator UsUω of each Grover iteration step rotates the state vector by an angle of 2θ toward |ω⟩.
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 - cos2θ) = O(sin2θ).
Furthermore, the probability of obtaining the wrong answer becomes O(1/N), which goes to zero for large N.