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

### Like this:

Like Loading...

*Related*

If the particular function F is symmetric in the ordered interval 0,1…,2^(n)-1 of bitstrings, you only need to know the average over the first half [ 0,1,…,2^(n-1) ]. Can you see why?

Comment by Elagnel Exterminador — September 29, 2013 @ 8:59 am

Yes, Angel. But then, as you said, you integrate only over half the values.

Comment by rrtucci — September 29, 2013 @ 1:39 pm

This morning, I realized there is something fishy about my blog post. If one assumes that the state |t> can be constructed in poly(n) steps, then there is no need to do Grover’s algo at all. Just proceed immediately to tracing over .

Comment by rrtucci — September 29, 2013 @ 1:47 pm

After looking at the Brassard et al. papers more carefully, I think I understand what is bothering me.

Let |s_new>, the new starting state, be what I called |t> before

Let |t_new>, the new target state, be what I called |s> before, where now is defined so that .

Just like me, Brassard et al. assume that |s_new> = |t> can be produced using poly(n) number of steps. (See Algorithm 1, page 5 of http://arxiv.org/abs/1106.4267 )

Brassard et al seem to be concerned with driving |s_new> to |t_new> using Grover’s algorithm. I think it’s a very contrived (virtually useless in practice) application of Grover’s algorithm because if we know how to produce |t> in poly(n) steps, one can calculate directly from it by tracing over . One doesn’t need to use Grover’s. It’s true that the tracing method requires that one do the experiment several times to compile good statistics for P(0) whereas the method of encoding into an n bit string gives in one shot, but only after doing a lot of Grover iterations

Comment by rrtucci — September 30, 2013 @ 11:51 pm

Suppose you knew that the combinatoric powerset of any number of bits has a natural self-similarity build on it which is then partly inherited to any bitwise function. Can you think of more clever ways to utilise this?

http://cag.dat.demokritos.gr/publications/TR2011-1.pdf

Comment by Elagnel Exterminador — October 2, 2013 @ 2:09 pm

El Angel, I looked at (your?) paper. Looks very erudite and well written. I also looked at the reference by Curtright and Zachos about Schroeder’s method. (I happen to know your fellow compatriot Cosmas Zachos who works at Argonne Lab.) Right now, I can’t think of any uses of this in quantum computing. It does remind me of the Trotter and Suzuki approximations, which are very useful in quantum computing.

Comment by rrtucci — October 4, 2013 @ 12:47 pm