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

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

Advertisements

Branding This Blog

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

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

3 Killer Goldfish Unleashed on Academia

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

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