One of the simplest applications of Grover’s algorithm is to calculate the average of an unstructured function. Let me explain one way of doing this.
Let with
for all
. Thus
is just a string of
bits. Suppose we want to find the average of a function
that maps each
to a real number. In other words, we want to find
.
This can also be interpreted as the integral of over the space of all
. We will assume the function
is bounded above and below: i.e., for all
, there exist reals
such that
. Then replace
by the more convenient function
which satisfies
for all
,
and
.
Let label
distinct qubits and
an extra single qubit.
We will assume that one can construct the following “target" state using poly(n) number of steps:
where is some real number and
is some normalized state. For
to be normalized, we must have
so
To find , one can use Grover's algorithm (or better still, my home-brewed version of Grover's algorithm, what I call AFGA. Unlike plain Grover's algorithm, AFGA always converges exactly to the target without overshooting). AFGA converges in order
steps. For our “starting" state
, we will use:
where is some
bit string for which
.
Note that
so the AFGA converges in order steps. By comparison, classical averaging takes order
steps if
is unstructured.
Finally, note that
Hence, if we ignore the qubits and only measure the
one, and if
and
are the number of zeros and ones respectively that we measure for
, then
.
There are other ways of finding using Grover's algorithm. One way was given by Grover. Later, Brassard, Hoyer and others found alternative ways. Here are some references:
- “A Framework for fast quantum mechanical algorithms”, by Lov Grover, http://arxiv.org/abs/quant-ph/9711043
- “Quantum Amplitude Amplification and Estimation”,
G. Brassard, P. Hoyer, M. Mosca, A. Tapp, http://arxiv.org/abs/quantph/0005055 - “An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance”, by G. Brassard, F. Dupuis, S. Gambs, A. Tapp, http://arxiv.org/abs/1106.4267