# 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?

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

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

Create a free website or blog at WordPress.com.