Quantum Bayesian Networks

June 20, 2011

Animated Gif of Grover Type Algorithm

Filed under: Uncategorized — rrtucci @ 11:36 pm

It doesn’t take long to notice that the Internet is literally crawling with animated gifs. Some are quite funny, like one I saw today—someone’s avatar—a picture of a guy who is a coffee addict, drinking cup after cup of joe in rapid succession. A bit of nuttiness caught up in an infinite loop. The looping part is important. Any animated gif worth its salt is in the infinite loop mode, playing over and over and over…

Animated gifs are very retro and low-tech, decidedly primitive by today’s standards. Nowadays there are much more efficient ways of producing motion in a web page, like MPEG-4, Flash, and other video formats.

Because of their retro look, animated gifs make me nostalgic for the past. They are to the modern web page what chrono-photography (photographic time-sequences) were to modern motion pictures. Chrono-photography had its heyday during the Victorian era. One of its most famous practitioners, Edward Muybridge, made photographic time-sequences that showed that there are times during a horse’s gallop when all 4 hooves are off the ground at the same time. (I recommend the Muybridge Wikipedia article. It has a “must see” animated gif of a galloping horse, made from Muybrigde’s photographs.)

A nice thing about animated gifs compared with the more modern stuff is that, due to their simplicity, they can be made by any nincompoop, without expensive or complicated software tools. Next I’ll explain how this nincompoop made one.

I wanted to make an animated gif having to do with quantum computation. I decided to make one that illustrates an algorithm that I call AFGA (Adaptive Fixed-Point Grover’s Algorithm.) I’ve reported previously about AFGA in the following blog post and the ArXiv paper mentioned therein:

Like the original GA (Grover’s Algorithm), AFGA takes a starting state $|s\rangle$ to a target state $|t\rangle$ in order$(\sqrt{N})$ easy steps, where $N=2^n$ and $n$ is the number of bits required to specify the states. AFGA is a generalization of the original GA. It improves upon it in several ways:

1. AFGA does not require that $\langle s|t\rangle$ be small. (The original GA only works if $\langle s|t\rangle \sim 1/\sqrt{N}$ )
2. AFGA converges with absolute certainty to the target state (The original GA converges only with a finite probability.)
3. In AFGA, the state of the system keeps getting closer to the target state with each successive step. (In the original GA, the state of the system periodically comes close to the target state then moves away from it, like Halley’s Comet and the Earth.)

The following is a single frame from my animated gif:

and this is a link to the full, gloriously animated gif.

The thin blue arrow travels from $|s\rangle$ to $|t\rangle$ along the red zigzag path on the Bloch sphere. I like to describe AFGA’s procedure as “bouncing between two longitudes”.

How I made my animated gif

I first used Microsoft PowerPoint. With it, I drew one initial slide without the moving parts. Then I created 20 duplicate slides (i.e., identical clones) of that initial slide, all in the same project.

Then I added the moving parts to the 21 slides. In my case, there was just one moving part, the roving arrow. I added that arrow to each of the 21 slides (at a different place in each slide, of course).

Then I generated 21 gifs, one for each slide. Powerpoint allowed me to generate all 21 gifs with just one click (one of the save options). Nice!

Then I used a very simple free tool called UnFreez (only 20 Kilobytes in size) to chain the 21 gifs together into a single animated gif. Piece of cake. (There are many other software programs that could have been used instead of UnFreez)

Note that I did not create a native “PowerPoint animation” first and then used that to create the animated gif. There is no cheap converter software to convert a native PowerPoint animation into an animated gif. And for good reason. An animated gif is composed of just a handful of single-instant sub-gifs (known as “frames”). In my case there were 21 frames. A PowerPoint animation is a much more sophisticated animal and has many, many more frames than an animated gif. You would have to tell the converter software precisely at which instants to extract a frame from the PowerPoint animation. Too messy. Not the best approach.