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.

In models of classical computation, searching an unsorted database cannot be done in less than linear time (so merely searching through every item is optimal). Grover's algorithm illustrates that in the quantum model searching can be done faster than this; in fact its time complexity O(N^1/2) is asymptotically the fastest possible for searching an unsorted database in the quantum model.^[1] It provides 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 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.)

1 Applications
2 Setup
3 Algorithm steps
4 The first iteration
5 Geometric proof of correctness
6 Algebraic proof of correctness
7 Extensions
8 Optimality
9 See also
10 Notes
11 References

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. 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 n=log₂ N qubits. Consider the problem of determining the index of the database entry which satisfies some search criterion. Let f be the function which maps database entries to 0 or 1, where f(ω)=1 and ω satisfies the search criterion. We are provided with (quantum black box) access to a subroutine in the form of a unitary operator, U_ω, which acts as:

$U_\omega |\omega\rang = - |\omega\rang$

$U_\omega |x\rang = |x\rang \qquad \mbox{for all}\ x \ne \omega$

Our goal is to identify the index $|\omega\rang$ .

Algorithm steps

The steps of Grover's algorithm are given as follows. Let $|s\rangle$ denote the uniform superposition over all states

$|s\rang = \frac{1}{\sqrt{N}} \sum_{x=1}^{N} |x\rang$ .

Then the operator

$U_s = 2 \left|s\right\rangle \left\langle s\right| - I$

is known as the Grover diffusion operator.

Here is the algorithm:

Initialize the system to the state

$|s\rang = \frac{1}{\sqrt{N}} \sum_{x=1}^{N} |x\rang$
Perform the following "Grover iteration" r(N) times. The function r(N), which is asymptotically O(N^½), is described below.
1. Apply the operator $U_\omega$ .
2. Apply the operator $U_s$ .
Perform the measurement Ω. The measurement result will be λ_ω with probability approaching 1 for N≫1. From λ_ω, ω may be obtained.

The first iteration

A preliminary observation, in parallel with our definition

$U_s = 2 \left|s\right\rangle \left\langle s\right| - I$ ,

is that U_ω can be expressed in an alternate way:

$U_\omega = I - 2 \left|\omega\right\rangle \left\langle \omega\right|$ .

To prove this it suffices to check how U_ω acts on basis states:

The following computations show what happens in the first iteration:

$\lang\omega|s\rang =\lang s|\omega\rang = \frac{1}{\sqrt{N}}$ .

$\langle s| s\rang =N\frac{1}{\sqrt{N}}\cdot \frac{1}{\sqrt{N}}=1$ .

$U_\omega |s\rang = (I-2| \omega\rangle \langle \omega|)|s\rang=|s\rang-2| \omega\rangle \langle \omega|s\rang=|s\rang-\frac{2}{\sqrt{N}}|\omega\rangle$ .

$U_s(|s\rang-\frac{2}{\sqrt{N}}|\omega\rangle) = (2 |s\rang \lang s| - I)(|s\rang-\frac{2}{\sqrt{N}}|\omega\rangle)=2 |s\rang \lang s|s\rang-|s\rang-\frac{4}{\sqrt{N}}|s\rang \langle s|\omega\rang%2B\frac{2}{\sqrt{N}}|\omega\rang=$

$=2|s\rang-|s\rang-\frac{4}{\sqrt{N}}\cdot\frac{1}{\sqrt{N}}|s\rang%2B\frac{2}{\sqrt{N}}|\omega\rang=|s\rang-\frac{4}{N}|s\rang%2B\frac{2}{\sqrt{N}}|\omega\rang=\frac{N-4}{N}|s\rang%2B\frac{2}{\sqrt{N}}|\omega\rang$ .

Geometric proof of correctness

$\lang\omega|s\rang =\lang s|\omega\rang = \frac{1}{\sqrt{N}}$

In geometric terms, the angle θ between |ω〉 and |s〉 is given by:

$\cos \theta = \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 $\pi - 2\theta \approx 2/\sqrt{N}$ .

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 exact probability of measuring the correct answer is:

$\sin^2\left( \left( r%2B \frac{1}{2} \right)\left( \pi - 2\theta \right) \right) ,$

where r is the (integer) number of Grover iterations. The earliest time that we get a near-optimal measurement is therefore $r \approx \pi \sqrt{N} / 4$ .

Algebraic proof of correctness

To complete the algebraic analysis we need to find out what happens when we repeatedly apply $U_s U_\omega$ . A natural way to do this is by eigenvalue analysis of a matrix. Notice that during the entire computation, the state of the algorithm is a linear combination of $s$ and $\omega$ . We can write the action of $U_s$ and $U_\omega$ in the space spanned by $\{|s\rang, |\omega\rang\}$ as:

$U_s�: a |\omega \rang %2B b |s \rang \mapsto (|\omega \rang \, | s \rang) \begin{pmatrix} -1 & 0 \\ 2/\sqrt{N} & 1 \end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}.$

$U_\omega�: a |\omega \rang %2B b |s \rang \mapsto (|\omega \rang \, | s \rang) \begin{pmatrix} -1 & -2/\sqrt{N} \\ 0 & 1 \end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}.$

So in the basis $\{ |\omega\rang, |s\rang \}$ (which is neither orthogonal nor a basis of the whole space) the action $U_sU_\omega$ of applying $U_\omega$ followed by $U_s$ is given by the matrix

$U_sU_\omega = \begin{pmatrix} -1 & 0 \\ 2/\sqrt{N} & 1 \end{pmatrix} \begin{pmatrix} -1 & -2/\sqrt{N} \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2/\sqrt{N} \\ -2/\sqrt{N} & 1-4/N \end{pmatrix}.$

This matrix happens to have a very convenient Jordan form. If we define $t = \arcsin(1/\sqrt{N})$ , it is

$U_sU_\omega = M \begin{pmatrix} \exp(2it) & 0 \\ 0 & \exp(-2it)\end{pmatrix} M^{-1}$ where $M = \begin{pmatrix}-i & i \\ \exp(it) & \exp(-it) \end{pmatrix}.$

It follows that rth power of the matrix (corresponding to r iterations) is

$(U_sU_\omega)^r = M \begin{pmatrix} \exp(2rit) & 0 \\ 0 & \exp(-2rit)\end{pmatrix} M^{-1}$

Using this form we can use trigonometric identities to compute the probability of observing ω after r iterations mentioned in the previous section,

$\left|\begin{pmatrix}\lang\omega|\omega\rang & \lang\omega|s\rang\end{pmatrix}(U_sU_\omega)^r \begin{pmatrix}0 \\ 1\end{pmatrix} \right|^2 = \sin^2\left( (2r%2B1)t\right)$ .

Alternatively, one might reasonably imagine that a near-optimal time to distinguish would be when the angles 2rt and -2rt are as far apart as possible, which corresponds to $2rt \approx \pi/2$ or $r = \pi/4t = \pi/4\arcsin(1/\sqrt{N}) \approx \pi\sqrt{N}/4$ . Then the system is in state

$(|\omega \rang \, | s \rang) (U_sU_\omega)^r \begin{pmatrix}0\\1\end{pmatrix} \approx (|\omega \rang \, | s \rang) M \begin{pmatrix} i & 0 \\ 0 & -i\end{pmatrix} M^{-1} \begin{pmatrix}0\\1\end{pmatrix} = | w \rang \frac{1}{\cos(t)} - |s \rang \frac{\sin(t)}{\cos(t)}.$

A short calculation now shows that the observation yields the correct answer ω with error O(1/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%2B \frac{1}{\sqrt{2}}%2B\frac{1}{2}%2B\cdots\right)$

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

It can be shown that this could be improved. If the number of marked items is k, where k is unknown, there is an algorithm that finds the solution in $\left(\frac{N}{k}\right)^{1/2}$ queries. This fact is used in order to solve the collision problem.

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.^[1] 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.^[2]

Notes

^ ^a ^b Bennett C.H., Bernstein E., Brassard G., Vazirani U., The strengths and weaknesses of quantum computation. SIAM Journal on Computing 26(5): 1510–1523 (1997). Shows the optimality of Grover's algorithm.
^ Michel Boyer; Gilles Brassard; Peter Hoeyer; Alain Tapp (1996). "Tight bounds on quantum searching". arXiv:quant-ph/9605034v1 [quant-ph].

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
Grover L.K.: 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.
What's a Quantum Phone Book?, Lov Grover, Lucent Technologies
Grover's Algorithm: Quantum Database Search, C. Lavor, L.R.U. Manssur, R. Portugal
Grover's algorithm on arxiv.org

Quantum information science

General	Quantum computer • Qubit • Quantum information • Quantum programming • Timeline of quantum computing

Quantum communication	Quantum capacity • Quantum channel • Quantum cryptography (Quantum key distribution) • Quantum teleportation • Superdense coding • LOCC • Entanglement distillation

Quantum algorithms	Universal quantum simulator • Deutsch–Jozsa algorithm • Grover's search • quantum Fourier transform • Shor's factorization • Simon's Algorithm • Quantum phase estimation algorithm • Quantum annealing

Quantum complexity theory	Quantum Turing machine • BQP • QMA • PostBQP

Quantum computing models	Quantum circuit (Quantum gate) • One-way quantum computer (cluster state) • Adiabatic quantum computation • Topological quantum computer

Decoherence prevention	Quantum error correction • Stabilizer codes • Entanglement-Assisted Quantum Error Correction • Quantum convolutional codes

Physical implementations

Quantum optics	Cavity QED

Ultracold atoms	Trapped ion quantum computer • Optical lattice

Spin-based	Nuclear magnetic resonance QC • Kane QC • Loss–DiVincenzo QC • Nitrogen-vacancy center

Superconducting quantum computing	Charge qubit • Flux qubit • Phase qubit