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:

September 18, 2013

Branding This Blog

Filed under: Uncategorized — rrtucci @ 8:48 pm

(Secret message: Operation Lisbeth is going very well.)

We’ve all heard the phrases “Branding is everything”, “It’s all about the brand”. These are the battle cries of marketing gurus & weasels that are highly adept at tugging at your heart strings and finding the mot juste to get you to buy. Apple, Coca Cola, Nike, Harley Davidson, pharmaceuticals… each spends 100’s of millions of dollars a year in advertisement. Companies like Apple inspire fierce customer loyalty and have managed to weave themselves in bold colors into the tapestry of our daily lives and culture.

Not to be left behind, we here at the QUANTUM BAYESIAN NETWORKS skyscraper have decided to spend 100 million bit coin dollars in product placement. Our brand is especially fortunate in that it combines not just 1 but 3 of the tallest lightning rods of the scientific world. We will start our branding campaign by rolling out the following triptych of postcards. A coffee mug, an umbrella, a tee-shirt, a baseball cap, a happy meal with Rev. Bayes action figurine, and Burma Shave style billboards may soon follow.

“I can't believe that God plays dice with the universe.” (Albert Einstein) “I can’t believe that God plays dice with the universe.” (Albert Einstein)

I filched this photo from Wikipedia's entry for Autonomy_Corporation. This neon sign can be found at the Autonomy offices in Cambridge.
I filched this photo from Wikipedia’s entry for Autonomy_Corporation. This neon sign can be found at the Autonomy offices in Cambridge, England. I’ve also learned from Stephen Bond’s website plover.net that the A stands for asshole and the B for Bayesian. I’ll say more about Stephen Bond’s website in a future post.

Zuckerberg-circle-of-friends
The “Director of National Intelligence” (old bald white guy on extreme right of network) is named The Clapper. Would I lie to you?

September 8, 2013

3 Killer Goldfish Unleashed on Academia

Filed under: Uncategorized — rrtucci @ 10:38 pm

Another week, another post. (If you haven’t noticed, I try to post approximately once a week, even if it’s only something really brief.)

Patents have been on my mind lately. This has been the case for two main reasons: First, because in the past few months, 3 of my patent applications were approved in quick succession. And second, because I’m hard at work on a new patent. (I’m referring to US patents only).

Of course, 3 goldfish are no match for 100 piranhas but it’s better than nothing, right? The 3 killer goldfish that I am unleashing on Academia are entitled

  • “Method for Sampling Probability Distributions Using a Quantum Computer”
  • “Method for Driving Starting Quantum State to Target One”
  • “Method for Evaluating Quantum Operator Averages”

Each of the 3 patents includes with it a software program which is an example (or, in patent parlance, a “preferred embodiment”) of the invention. These software programs are: Quibbs (in Java), Afga (in Octave) and QOperAv (in Java), respectively. They are available at my website (www.ar-tiste.com)

As you can see from this list, I had 3 previous QC patents so now I have a total of 6 QC patents. The new one I am working on right now is thus going to be my seventh deadly sin, seventh sea, seventh continent, seventh seal…

It usually takes about 3 years (!) from the time you apply for a patent to the time it is approved by a patent examiner and granted.

The approval process for my 3 new patents went very smoothly, thank God. For my 3 older patents, convincing the patent examiner to approve my patent application was an arduous, frustrating process. This time, 2 of the patent applications were approved without changes. K.H., the examiner of the third patent application, made me sweat a bit, but we managed to reach an agreement after several days of intense negotiations. I think K.H. is by far the smartest patent examiner I’ve had to date. We argued a lot over the telephone, but at least I felt he listened well and understood the main scientific issues quite well for someone trying to understand them from me!

I’ve been working on my new patent for only a few weeks but I think the research part of it is already about 75% finished. Good omen. Barking up the right tree! Of course the last 25% of a research project is always the hardest part to complete, at least for me. How long before I finish it? I don’t know. Finishing it might even take me infinite time if I hit an insurmountable snag. In the best of circumstances, it will take a LONG time because I want to write (1) a patent, (2) an arXiv paper and (3) a software program, all about this same idea. It’s also necessary for me to submit the patent application before publicly releasing the software or the arXiv paper. It used to be that for US patents, you could submit a patent application up to one year after a “public disclosure” such as publishing in arXiv. But the law has been changed and starting on March 16, 2013, patenting of an invention is not allowed after public disclosure.

I obviously can’t say much here and now about the subject of the new patent. It’s basically a QC algorithm for doing a certain aspect of AI. A lot of people are already working on the intersection of QCs and AI so I have classified this project Top Secret. Until I unveil my new patent, it will henceforth be referred to in this secret blog of mine by the codename Operation Lisbeth, or “the goldfish with the dragon tattoo”.

goldfish-with-dragon-tattoo

Don’t ever under-estimate the danger posed by a goldfish. They too can nibble a path of destruction. Here is an example of a recent news item from the British press about the very subject, killer goldfish.

Police called in after “killer” goldfish are dumped in nature reserve ponds

no-goldfish

Blog at WordPress.com.

%d bloggers like this: