Grover's algorithm


Also found in: Wikipedia.

Grover's algorithm

[¦grō·vərz ′al·gə‚rith·əm]
(computer science)
An algorithm for finding an item in a database of 2 N items, using a quantum computer, in a time of order 2 N /2steps instead of order 2 N steps.
References in periodicals archive ?
Grover's Algorithm on a quantum computer allows for database searches in the square root of N instead.
When put to work in a "larger" quantum computer, Grover's Algorithm could spell the end for encryption such as DES.
While Shor's algorithm may be of more immediate utility, Grover's algorithm seems more interesting in a theoretical sense, as it highlights an area of fundamental superiority in quantum computation.
The idea of Grover's algorithm is to place the register in an equal superposition of all states, and then selectively invert the phase of the marked state, and then perform an inversion about average operation a number of times.
This Grover's algorithm flow chart is as shown in Figure 1.
However, the speed-up is only polynomial, not exponential, and it has been shown that Grover's algorithm is optimal for quantum computers.
Small cases indicate that Hogg's algorithms are more efficient than Grover's algorithm applied to structured search problems, but that the speed-up is likely to be only polynomial.
Grover's algorithm searches an unstructured list of size N for an x that makes a statement true.
If an amplitude of type A is detected, THEN trigger macroscopic reaction R where "type A" may be characterized by a condition such as that in Grover's algorithm, i.
Grover's algorithm performs operations on a superposition of all possible search values that serve to increase the amplitude of the desired search value.
1996] to Grover's algorithm to redevelop the result of Boyer et al.
Deutsch-Jozsa's algorithm for the rapid solution [1-3], Shor's algorithm for the factorization [2-4], Grover's algorithms for the database search [2,5-7] and so on are known, and efforts to expand applications of the quantum calculation are continued.