Quantum Bayesian Networks

September 28, 2013

How to Use Grover’s Algorithm to Find the Average (a.k.a Mean, Integral) of a Weirdo Function

Filed under: Uncategorized — rrtucci @ 4:28 pm

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 x^n =(x_{n-1},\ldots,x_2,x_1,x_0) with x_j\in \{0,1\} for all j. Thus x^n is just a string of n bits. Suppose we want to find the average of a function F() that maps each x^n to a real number. In other words, we want to find

\overline{F}=\frac{1}{2^n} \sum_{x^n} F(x^n).

This can also be interpreted as the integral of F() over the space of all x^n. We will assume the function F() is bounded above and below: i.e., for all x^n, there exist reals a,b such that a< F(x^n) < b. Then replace F() by the more convenient function f(x^n) = (F(x^n)-a)/b which satisfies 0\leq f(x^n) \leq 1 for all x^n, \overline{f} = (\overline{F}-a)/b and 0\leq \overline{f} \leq 1.

Let \alpha^n label n distinct qubits and \beta an extra single qubit.

We will assume that one can construct the following “target" state using poly(n) number of steps:

|t\rangle_{\alpha^n,\beta}=  \left[\sum_{x^n}\sqrt{\frac{f(x^n)}{2^n}}|x^n\rangle_{\alpha^n}|0\rangle_\beta\right]+  z |\psi\rangle  _{\alpha^n} |1\rangle_{\beta}

where z is some real number and |\psi\rangle is some normalized state. For |t\rangle to be normalized, we must have \overline{f} + z^2 = 1 so

z = \sqrt{ 1 - \overline{f}}

To find \overline f, 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 \frac{1}{\langle t | s \rangle} steps. For our “starting" state |s\rangle, we will use:

|s\rangle_{\alpha^n,\beta}=  |a^n\rangle_{\alpha^n} |0\rangle_\beta

where a^n is some n bit string for which 1/2^n << f(a^n) \leq 1.

Note that

\frac{1}{\langle s | t \rangle} =  \sqrt{\frac{2^n}{f(a^n)}}

so the AFGA converges in order \sqrt{2^n} steps. By comparison, classical averaging takes order 2^n steps if f() is unstructured.

Finally, note that

{\rm tr}_{\alpha^n}|t\rangle\langle t |=\overline{f}   |0\rangle\langle 0 |_\beta+(1 - \overline{f})|1\rangle\langle 1 |_\beta

Hence, if we ignore the \alpha^n qubits and only measure the \beta one, and if N(0) and N(1) are the number of zeros and ones respectively that we measure for \beta, then

\overline{f}=P(0) = \frac{N(0)}{N(0) + N(1)}.

There are other ways of finding \overline{f} using Grover's algorithm. One way was given by Grover. Later, Brassard, Hoyer and others found alternative ways. Here are some references:



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

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

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

  3. 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 |t\rangle\langle t| over \alpha^n.

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

  4. 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 a^n is defined so that \overline {f} = \sum_{j=0}^{n-1} a_j/2^{j+1}.

    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 \overline{f} directly from it by tracing |t\rangle\langle t| over \alpha^n. 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 \overline f into an n bit string a^n gives \overline f in one shot, but only after doing a lot of Grover iterations

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

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


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

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

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: