Grover's algorithm

Grover's algorithm is a quantum algorithm for searching an unsorted database with "N" entries in "O(N^1/2)" time and using "O("log"N)" storage space (see big O notation). It was invented by Lov Grover in 1996.

Classically, searching an unsorted database requires a linear search, which is "O(N)" in time. Grover's algorithm, which takes "O(N^1/2)" time, is the fastest possible quantum algorithm for searching an unsorted database.Bennett C.H., Bernstein E., Brassard G., Vazirani U., " [http://www.cs.berkeley.edu/~vazirani/pubs/bbbv.ps The strengths and weaknesses of quantum computation] ". SIAM Journal on Computing 26(5): 1510-1523 (1997). Shows the optimality of Grover's algorithm.] It provides "only" a quadratic speedup, unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts. However, even quadratic speedup is considerable when "N" is large.

Like many 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. (An example of a deterministic quantum algorithm is the Deutsch-Jozsa algorithm, which always produces the correct answer with probability one.)

Applications

Although the purpose of Grover's algorithm is usually described as "searching a database", it may be more accurate to describe it as "inverting a function". Roughly speaking, if we have a function "y=f(x)" that can be evaluated on a quantum computer, this algorithm allows us to calculate "x" when given "y". Inverting a function is related to the searching of a database because we could come up with a function that produces a particular value of "y" if "x" matches a desired entry in a database, and another value of "y" for other values of "x".

Grover's algorithm can also be used for estimating the mean and median of a set of numbers, and for solving the Collision problem. In addition, it can be used to solve NP-complete problems by performing exhaustive searches over the set of possible solutions. This would result in a considerable speed-up over classical solutions, even though it does not provide the "holy grail" of a polynomial-time solution.

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.

Setup

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

Let us number the database entries by 1, 2,... , "N". Choose an observable, "Ω", acting on "H", with "N" distinct eigenvalues whose values are all known. Each of the eigenstates of "Ω" encode one of the entries in the database, in a manner that we will describe. Denote the eigenstates (using bra-ket notation) as

:$\{|1\; ang,\; |2\; ang,\; cdots,\; |N\; ang\}$

and the corresponding eigenvalues by

:$\{lambda\_1,\; lambda\_2,\; cdots,\; lambda\_\{N\}\; \}$

We are provided with a unitary operator, "U_ω", which acts as a subroutine that compares database entries according to some search criterion. The algorithm does not specify how this subroutine works, but it must be a "quantum" subroutine that works with superpositions of states. Furthermore, it must act specially on one of the eigenstates, |"ω">, which corresponds to the database entry matching the search criterion. To be precise, we require "U_ω" to have the following effects:

:$U\_omega\; |omega\; ang\; =\; -\; |omega\; ang$:$U\_omega\; |x\; ang\; =\; |x\; ang\; qquad\; mbox\{for\; all\}\; x\; e\; omega$or:$langle\; omega|\; omega\; ang\; =1$.:$langle\; omega|\; x\; ang\; =langle\; x|\; omega\; ang\; =0$.:$U\_omega\; |omega\; ang\; =\; (I-2|\; omega\; angle\; langle\; omega|)|omega\; ang=|omega\; ang-2|\; omega\; angle\; langle\; omega|omega\; ang=-|omega\; angle$.:$U\_omega\; |x\; ang\; =\; (I-2|\; omega\; angle\; langle\; omega|)|x\; ang=|x\; ang-2|\; omega\; angle\; langle\; omega|x\; ang=|x\; angle$.

Our goal is to identify this eigenstate |ω>, or equivalently the eigenvalue ω, that U_ω acts specially upon.

Also we can write::$langomega|s\; ang\; =lang\; s|omega\; ang\; =\; frac\{1\}\{sqrt\{N$.:$langle\; s|\; s\; ang\; =Nfrac\{1\}\{sqrt\{Ncdot\; frac\{1\}\{sqrt\{N=1$.:$U\_omega\; |s\; ang\; =\; (I-2|\; omega\; angle\; langle\; omega|)|s\; ang=|s\; ang-2|\; omega\; angle\; langle\; omega|s\; ang=|s\; ang-frac\{2\}\{sqrt\{N|omega\; angle$.

:$U\_s(|s\; ang-frac\{2\}\{sqrt\{N|omega\; angle)\; =\; (2\; |s\; ang\; lang\; s|\; -\; I)(|s\; ang-frac\{2\}\{sqrt\{N|omega\; angle)=2\; |s\; ang\; lang\; s|s\; ang-|s\; ang-frac\{4\}\{sqrt\{N|s\; ang\; langle\; s|omega\; ang+frac\{2\}\{sqrt\{N|omega\; ang=$.:$=2|s\; ang-|s\; ang-frac\{4\}\{sqrt\{Ncdotfrac\{1\}\{sqrt\{N|s\; ang+frac\{2\}\{sqrt\{N|omega\; ang=|s\; ang-frac\{4\}\{N\}|s\; ang+frac\{2\}\{sqrt\{N|omega\; ang=frac\{N-4\}\{N\}|s\; ang+frac\{2\}\{sqrt\{N|omega\; ang$.After application of the two operators ( $U\_omega$ and $U\_s$ ), the amplitude of the searched-for element increases. And this is one Grover iteration "r". "N"=2"ⁿ", "n" is number of qubits in blank (zero) state.

Algorithm steps

The steps of Grover's algorithm are as follows:

1. Initialize the system to the state::$|s\; ang\; =\; frac\{1\}\{sqrt\{N\; sum\_\{x=1\}^\{N\}\; |x\; ang$
2. Perform the following "Grover iteration" "r(N)" times. The function "r(N)" is described below.
   #Apply the operator $U\_omega=I-2|\; omega\; angle\; langle\; omega|$.
   #Apply the operator $U\_s\; =\; 2\; left|s\; ight\; angle\; leftlangle\; s\; ight|\; -\; I$.
3. Perform the measurement Ω. The measurement result will be λ_ω with probability approaching 1 for N>>1. From λ_ω, ω may be obtained.

Our initial state is

:$|s\; ang\; =\; frac\{1\}\{sqrt\{N\; sum\_\{x=1\}^\{N\}\; |x\; ang$

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

:$langomega|s\; ang\; =lang\; s|omega\; ang\; =\; frac\{1\}\{sqrt\{N$

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

:$cos\; left(frac\{pi\}\{2\}\; -\; frac\{\; heta\}\{2\}\; ight)\; =\; frac\{1\}\{sqrt\{N$:$sin\; frac\{\; heta\}\{2\}\; =\; frac\{1\}\{sqrt\{N$

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 straightforward to check that the operator U_sU_ω of each Grover iteration step rotates the state vector by an angle of θ 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":

:$r\; ightarrow\; frac\{pi\; sqrt\{N\{4\}$Furthermore, the probability of obtaining the wrong answer is $O(1/N)$, which approaches zero as N increases.

The probability of measuring the correct answer is::$sin^2left(\; frac\{2r+1\}\{2\}\; heta\; ight)\; ,$where "r" is the (integer) number of Grover iterations, and:$heta\; =\; 2arccosleft(\; sqrt\{1-frac\{1\}\{N\; ight)=2arcsin\; frac\{1\}\{sqrt\{2^n\; .$

Extensions

If, instead of 1 matching entry, there are "k" matching entries, the same algorithm works but the number of iterations must be "π(N/k)^1/2/4" instead of "πN^1/2/4".There are several ways to handle the case if "k" is unknown. For example, one could run Grover's algorithm several times, with

:$pi\; frac\{N^\{1/2\{4\},\; pi\; frac\{(N/2)^\{1/2\{4\},\; pi\; frac\{(N/4)^\{1/2\{4\},\; ldots$

iterations. For any "k", one of iterations will find a matching entry with a sufficiently high probability. The total number of iterations is at most

:$pi\; frac\{N^\{1/2\{4\}\; left(\; 1+\; frac\{1\}\{sqrt\{2+frac\{1\}\{2\}+cdots\; ight)$

which is still O("N^1/2").

Optimality

It is known that Grover's algorithm is optimal. That is, any algorithm that accesses the database only by using the operator U_ω must apply U_ω at least as many times as Grover's algorithm. This result is important in understanding the limits of quantum computation. If the Grover's search problem was solvable with "log^c N" applications of U_ω, that would imply that NP is contained in BQP, by transforming problems in NP into Grover-type search problems. The optimality of Grover's algorithm suggests (but does not prove) that NP is not contained in BQP.

The number of iterations for "k" matching entries, "π(N/k)^1/2/4", is also optimal.

References

* Grover L.K.: " [http://arxiv.org/abs/quant-ph/9605043 A fast quantum mechanical algorithm for database search] ", Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
* Grover L.K.: " [http://arxiv.org/abs/quant-ph/0109116 From Schrödinger's equation to quantum search algorithm] ", American Journal of Physics, 69(7): 769-777, 2001. Pedagogical review of the algorithm and its history.
* http://www.bell-labs.com/user/feature/archives/lkgrover/
* http://arxiv.org/abs/quant-ph/0301079 Grover's Algorithm: Quantum Database Search
* [http://xstructure.inr.ac.ru/x-bin/theme3.py?level=1&index1=359266 Grover's algorithm on arxiv.org]

Notes