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 .
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