Grover's algorithm

The Grover algorithm is a quantum algorithm for searching an unsorted database with N entries in steps and memory requirements ( see big O notation ). He was released by Lov Grover in 1996 and is so far the only known evidence that quantum computers can in principle faster than classical computers.

On a classical computer the principle fastest possible search algorithm is the linear search in an unsorted database, which requires computational steps. The Grover algorithm with steps thus provides a quadratic acceleration, which is significant for large N.

Like most quantum algorithms is Grover algorithm a probabilistic algorithm, ie it gives the correct response with a high probability, the probability of an erroneous response is reduced by a simple repetition of the algorithm.

Applications

The Grover algorithm enables not really the direct search in unsorted databases, but the reverse of a finite function y = f ( x), for a given value of y corresponds to a value of finding a value x in the domain of f

The Grover algorithm can also be used to calculate the mean and median of a set of numbers, as well as to solve the collision problem. Next it can be used to solve NP- complete problems, by going through the set of all possible problems. Although this "big" NP- complete problems can be solved significantly faster, even the Grover algorithm allows no solution in polynomial time complexity.

Detailed procedure

The following sequence of the algorithm refers to the search for a single search entry. The algorithm can be further optimized in order to find a plurality of possible entries, the number of which is known in advance.

Requirements

Given an unordered database of N entries, which is represented in an N- dimensional state space by log2N qubits. The entries are 0, 1, ..., numbered (N -1). Then we choose an observable acting on Ω with N different eigenstates

( in the Bra- Ket notation) and the corresponding eigenvalues

Furthermore, a unitary operator Uomega is given, which is a subroutine, the so-called "oracle", which effectively compares the database entries according to the search criteria. The algorithm does not specify how the oracle works, but it needs to process the superposition of quantum states and this eigenstate | ω > see:

The goal of the algorithm is this eigenstate | ω >, or equivalent to identify the eigenvalue ω.

Step sequence

Line of sight, and the determination of the step number R (n)

The initial state is

Geometrically, this means that | ω > and | s> at an angle of ( π / 2 - θ ) to each other, which is θ = θ (N ) is given by:

That is,

The operator Uomega is a reflection on the to | ω > orthogonal hyperplane; for vectors in the of | s> and | ω > plane spanned it acts as a reflection at the line by | ω × >. The operator Us is a reflection at the line by | s>. Thus, the state vector remains after application of Us and Uomega in by | s> and | ω > plane spanned. So that the operator UsUω rotated at each step of the iteration Grover the state vector at an angle of 2θ after | ω >.

The algorithm must stop so once the state vector | ω > has come the closest. More iterations would back him | spin ω > away and thus reduce the probability of the correct answer again. For the optimum number r of iterations for exact accordance with | ω > is true:

However, since r must be an integer, we set r equal to the rounded number π/4θ - 1/2. Thus, the probability to measure a wrong answer. The error probability for N database entries is asymptotically, ie it is negligibly small for large N.

For N >> 1 is true θ ≈ N-1 /2,

Extensions

If the database contains only one, but k searched entries, the algorithm works well, but is valid for the number r of iterations now π (N / k) 1/2/4 instead πN1/2/4. If k is unknown, one leads the Grover algorithm in

Iterations. For any k a sought entry with a sufficiently high probability found. The total number of iterations is at most

Optimality of Grover algorithm

The Grover algorithm is optimal in the sense that it can be less than computation steps no quantum algorithm. This result is important in order to understand the limitations of quantum computing. If the search problem solvable for example, in the worst case, with steps so NP would be contained in BQP.

Likewise, the number I.A. necessary iterations for k searched entries, ie π (N / k) 1/2/4, optimal.

Quality argument

To a heuristic understanding of the quantum mechanical method compared to the classical approach to win, and for generalizations, it is useful to consider the following special case: the required information should be on a specific grid point of a square lattice. The search requires so " classic " steps when the edge length of the square is. Quantum mechanical states are against "rays" in the Hilbert space, ie they are intended only to within a factor, and assuming the center of the square, the direction θ of the beam is given by a set of points that does not correspond to only the extent that the content of the square, that is an amount to provide a specific point on to find the selected beam, one needs to perform only interference experiments with other quantum- mechanical states, which without additional time is reasonably practicable. The information sought is obtained thus quantum mechanically in steps.