Another famous algorithm that made a splash in the world of quantum
computing was invented by L. K. Grover in 1997 [40]. This algorithm is in
a different class from the ones we have studied so far, which may all be said
to be QFT-based. Grover’s algorithm introduced a new technique: amplitude
amplification. Even though it did not demonstrate an exponential speed-up
over the classical case, it was still dramatic enough to get noticed.
The problem Grover attacked was that of search for an element in an
unstructured database. The problem is like doing a reverse search in a phone
directory: you have a number and need to know the person it belongs to. Thus
there is no regular short-cut to the search, you have to go through each entry
in the book and check if it matches the number you have.
The problem can be phrased in the language of oracles, if we assume that
the criterion for the search is built into a function evaluator: a function that
tells you whether the input number matches the search criterion or not. So
we imagine that the numbers x are indices to the entries in the database, and
one index, let’s say k, belongs to the entry being searched for. Then
f
k
(x) =
(
1 if x = k
0 otherwise.
(8.70)
Here, if x is an n-bit number, then the size of the database is 2
n
= N . As
Leave a Reply