Grover's algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O(log N) storage space (see big O notation). Lov Grover formulated it 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(N1/2) is asymptotically the fastest possible for searching an unsorted database in the linear 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. Unsorted search speeds of up to constant time are achievable in the nonlinear quantum model.[2]

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.)

Applications[edit]

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[edit]

Consider an unsorted database with N entries. The algorithm requires an N-dimensional state space H, which can be supplied by n=log2 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 if and only if ω 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 follows (for the ω for which f(ω)=1):

 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[edit]

Quantum circuit representation of Grover's algorithm

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:

  1. Initialize the system to the state
    |s\rang = \frac{1}{\sqrt{N}} \sum_{x=1}^{N} |x\rang
  2. 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.
  3. Perform the measurement Ω. The measurement result will be λω with probability approaching 1 for N≫1. From λω, ω may be obtained.

The first iteration[edit]

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:

 (I-2| \omega\rangle \langle \omega|)|\omega\rang=|\omega\rang-2| \omega\rangle \langle \omega|\omega\rang=-|\omega\rangle = U_\omega |\omega\rang.
 (I-2| \omega\rangle \langle \omega|)|x\rang=|x\rang-2| \omega\rangle \langle \omega|x\rang=|x\rangle = U_\omega |x\rang for all  x \neq \omega.

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+\frac{2}{\sqrt{N}}|\omega\rang=
=2|s\rang-|s\rang-\frac{4}{\sqrt{N}}\cdot\frac{1}{\sqrt{N}}|s\rang+\frac{2}{\sqrt{N}}|\omega\rang=|s\rang-\frac{4}{N}|s\rang+\frac{2}{\sqrt{N}}|\omega\rang=\frac{N-4}{N}|s\rang+\frac{2}{\sqrt{N}}|\omega\rang.

After application of the two operators ( U_\omega and U_s ), the amplitude of the searched-for element has increased from  \left| \lang \omega | s \rang \right|^2 = 1/N to  \left| \lang \omega | U_s U_\omega s \rang \right|^2  \approx 9/N.

Description of Uω[edit]

Grover's algorithm requires a "quantum oracle" operator U_{\omega} which can recognize solutions to the search problem and give them a negative sign. In order to keep the search algorithm general, we will leave the inner workings of the oracle as a black box, but will explain how the sign is flipped. The oracle contains a function f which returns f(x) = 1 if |x\rang is a solution to the search problem and f(x) = 0 otherwise. The oracle is a unitary operator which operates on two qubits, the index qubit |x\rang and the oracle qubit |q\rang:

|x\rang|q\rang \overset{U_{\omega}}\longrightarrow |x\rang|q\oplus f(x)\rang

As usual, \oplus denotes addition modulo 2. The operation flips the oracle qubit if f(x) = 1 and leaves it alone otherwise. In Grover's algorithm we want to flip the sign of the state |x\rang if it labels a solution. This is achieved by setting the oracle qubit in the state (|0\rang - |1\rang)/\sqrt{2}, which is flipped to (|1\rang - |0\rang)/ \sqrt{2} if |x\rang is a solution:

|x\rang\left(|0\rang - |1\rang\right)/\sqrt{2}  \overset{U_{\omega}}\longrightarrow (-1)^{f(x)}|x\rang\left( |0\rang- |1\rang\right)/\sqrt{2}

We regard |x\rang as flipped, thus the oracle qubit is not changed, so by convention the oracle qubits are usually not mentioned in the specification of Grover's algorithm. Thus the operation of the oracle U_{\omega} is simply written as:

|x\rang \overset{U_{\omega}} \longrightarrow (-1)^{f(x)}|x\rang

Geometric proof of correctness[edit]

Picture showing the geometric interpretation of the first iteration of Grover's algorithm. The state vector |s\rang is rotated towards the target vector |\omega\rang as shown.

Consider the plane spanned by |s\rang and |\omega\rang; equivalently, the plane spanned by |\omega\rang and the perpendicular ket |s'\rang = \frac{1}{\sqrt{N - 1}}\sum_{x \neq \omega} |x\rang. We will consider the first iteration, acting on the initial ket |s\rang. Since |\omega\rang is one of the basis vectors in |s\rang the overlap is

 \lang s'|s\rang = \sqrt{\frac{N-1}{N}}

In geometric terms, the angle \theta/2 between |s\rang and |s'\rang is given by:

 \sin \theta/2 = \frac{1}{\sqrt{N}}

The operator U_{\omega} is a reflection at the hyperplane orthogonal to |\omega\rang for vectors in the plane spanned by |s'\rang and |\omega\rang; i.e. it acts as a reflection across |s'\rang. The operator U_s is a reflection through |s\rang. Therefore, the state vector remains in the plane spanned by |s'\rang and |\omega\rang after each application of the operators U_s and U_{\omega}, and it is straightforward to check that the operator U_s U_{\omega} of each Grover iteration step rotates the state vector by an angle of \theta = 2\arcsin \frac{1}{\sqrt{N}}  .

We need to stop when the state vector passes close to |\omega\rang; after this, subsequent iterations rotate the state vector away from |\omega\rang, reducing the probability of obtaining the correct answer. The exact probability of measuring the correct answer is:

 \sin^2\left( \left( r+ \frac{1}{2} \right)\theta\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[edit]

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 + 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 + 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+1)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).

Extension to space with multiple targets[edit]

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 πN1/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 the 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\right)=\pi \frac{N^{1/2}}{4} \left( 2+\sqrt{2}\right)

which is still O(N1/2). It can be shown that this can be improved. If the number of marked items is k, where k is unknown, there is an algorithm that finds the solution in \sqrt{N/k} queries. This fact is used in order to solve the collision problem.[3][4]

Quantum partial search[edit]

A modification of Grover's algorithm called quantum partial search was described by Grover and Radhakrishnan in 2004.[5] In partial search, one is not interested in finding the exact address of the target item, only the first few digits of the address. Equivalently, we can think of "chunking" the search space into blocks, and then asking "in which block is the target item?". In many applications, such a search yields enough information if the target address contains the information wanted. For instance, to use the example given by L.K. Grover, if one has a list of students organized by class rank, we may only be interested in whether a student is in the lower 25%, 25-50%, 50-70% or 75-100% percentile.

To describe partial search, we consider a database separated into K blocks, each of size b = N/K. Obviously, the partial search problem is easier. Consider the approach we would take classically - we pick one block at random, and then perform a normal search through the rest of the blocks (in set theory language, the complement). If we don't find the target, then we know it's in the block we didn't search. The average number of iterations drops from N/2 to (N-b)/2.

Grover's algorithm requires \pi/4\sqrt{N} iterations. Partial search will be faster by a numerical factor which depends on the number of blocks K. Partial search uses n_1 global iterations and n_2 local iterations. The global Grover operator is designated G_1 and the local Grover operator is designated G_2.

The global Grover operator acts on the blocks. Essentially, it is given as follows:

  1. Perform j_1 standard Grover iterations on the entire database.
  2. Perform j_2 local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block.
  3. Perform one standard Grover iteration

The optimal values of j_1 and j_2 are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by Korepin and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.

Optimality[edit]

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 logc 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.[3]

Applicability and Limitations[edit]

When applications of Grover's algorithm are considered, it should be emphasized that the database is not represented explicitly. Instead, an oracle is invoked to evaluate an item by its index. Reading a full data-base item by item and converting it into such a representation may take a lot longer than Grover's search. To account for such effects, Grover's algorithm can be viewed as solving an equation or satisfying a constraint. In such applications, the oracle is a way to check the constraint and is not related to the search algorithm. This separation usually prevents algorithmic optimizations, whereas conventional search algorithms often rely on such optimizations and avoid exhaustive search. These and other considerations about using Grover's algorithm are discussed in [6]

See also[edit]

Notes[edit]

  1. ^ 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.
  2. ^ Meyer, D.A. and Wong, T.G. Nonlinear Quantum Search Using the Gross-Pitaevskii Equation.
  3. ^ a b Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp (1998), Fortsch. Phys. 46: 493–506, arXiv:quant-ph/9605034, Bibcode:1998ForPh..46..493B, doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P 
  4. ^ Andris Ambainis (2004), "Quantum search algorithms", SIGACT News 35 (2): 22–35, arXiv:quant-ph/0504012, Bibcode:2005quant.ph..4012A, doi:10.1145/992287.992296 
  5. ^ L.K. Grover and J. Radhakrishnan,Is partial quantum search of a database any easier?. quant-ph/0407122
  6. ^ Viamontes G.F.; Markov I.L.; Hayes J.P. (2005), "Is Quantum Search Practical?", IEEE/AIP Computing in Science and Engineering 7 (3): 62–70 

References[edit]

External links[edit]