quantum search algorithm
Tue, 13 Mar 2001 15:28:50 -0500 (EST)
Directly from the oven :-):
Excerpt from a short module description is given below.
Grover's algorithm assumes that one is given a quantum function, also called
an oracle, that indicates, when confronted with any number between 0 and N-1,
whether this number is or is not the special number being sought.
The algorithm enables one to find a marked item in unstructured N-item database
in a time that scales not as N, as a classical computer would require, but only
as sqrt N.
Putting it another way: the maximum number of calls to oracle is proportional to
sqrt N. Think about a scenario when the oracle charges you per call, or
when its computations are very lengthy. The answer is probabilistic, but
given with very high degree of probability.
In our implementation the 'search' function is able to find specifically
marked number from the assemble of 8 numbers: 0..7 in just two calls to oracle,
with very high degree of probability. The 'test' performs m such searches.
Note that the final stage of the search is simulated as a quantum measurement
performed on the state vector.