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.
This development in the field of quantum computation may threaten and replace traditional encryption systems by utilizing algorithms such as Shor's quantum factoring algorithms, discrete algorithms, and Grover's algorithm. Thus, we should be looking to design new algorithms to resist the attacks against quantum algorithms whose contribution and progress in this field has become of significant importance and crucial necessity in the protection of information.
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.
The team was able to demonstrate that their diamond-encased system does indeed operate in a quantum fashion by seeing how closely it matched "Grover's algorithm."
When he was 17, his research paper had brought him an invitation from Bell Labs, US, and a chance to contact Lov Grover who discovered the ' Grover's algorithm' in 1996.
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.
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.e., F(A)=0 for an a appropriate functional F.
Grover's algorithm performs operations on a superposition of all possible search values that serve to increase the amplitude of the desired search value.
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.