Quantum Bayesian Networks

June 29, 2011

Mission Impossible For String Theorists

Filed under: Uncategorized — rrtucci @ 5:10 pm

In previous posts, I’ve speculated that quantum Shannon Information Theory might help string theory. String theorists themselves have already made some attempts to apply quantum entanglement and information transmission concepts to the study of Hawking radiation and black holes.

But what about quantum complexity theory and its more applied sibling, quantum computing, can those help string theory too?

Some might say that string theory needs the help. It’s now 43 years old. In that time, thousands of papers have been written about the subject. But no one has yet managed to use string theory to make any precise quantitative predictions that could be used to test its validity. 43 years is a huge amount of time for a physics theory. All preceding, successful, physics theories have demonstrated their validity and worth in much less time than 43 years. String theory, you better hurry. Your biological clock is ticking away. 43 is almost too late to have babies.

String theory claims to be a theory of everything (TOE). I wonder, shouldn’t a TOE overlap significantly with computational complexity theory (CCT)? After all, they both try to determine the limitations and behavior of extremely large and complex things. Furthermore, any physics theory can be viewed as a computation theory and vice versa.

I see smart people like Scott Aaronson studying the rich links between CCT and quantum mechanics. The natural and logical next step would be to study the links between CCT and those elaborations of quantum mechanics that we call quantum field theory and string theory. String theorists are not currently doing this. Currently, top string theorists like Ed Witten use extensively the mathematical tools of differential geometry and group theory, but not those of CCT. Am I a loony for believing that they should be using CCT too?

Maybe CCT motivated constraints can help us formulate string theory in the same way that, for example, requiring general covariance helps us formulate general relativity. For instance, it’s very likely that P!=NP. This is a highly non-trivial observation about our universe, as nontrivial as is the observation that we live in 4-dimensions (at low energies, at least). Can’t CCT observations like P!=NP be used to constrain a TOE? Who knows, perhaps CCT ideas could yield a vacuum selection criterion for string theory.

String Theory Joe, your mission, if you decide to accept it, is to use CCT tools to elucidate string theory. As usual, this blog post will self-destruct in five seconds… Fizz.

P.S. I know very little about either string theory or quantum complexity theory. Therefore, as in that Far Side cartoon where a deer in the crosshairs is pointing at a nearby deer, I defer any questions about this topic to Scott Aaronson and professional string theorists.

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:

My Secret Life as a Captain of the Grover’s Algorithm

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.

June 15, 2011

Quantum Computers and the Coming Era of Personalized Medicine

Filed under: Uncategorized — rrtucci @ 10:10 am

“There is a world market for maybe five computers”
IBM’s Thomas J Watson

(some people claim this quote is a myth. That he never said this. It’s a great quote though. I wish I had said it.)

Sequencing the genome of a human individual has gone down in cost dramatically in the last decade. The Human Genome Project consortium, which included 18 institutions from around the world, published its final paper in 2004. The cost of that project has been estimated at more than $3 billion. Currently the cost of sequencing a human genome is about $10K.

It is expected that a human genome for $1000 will be announced by someone either this year or the next. There’s an NIH project specifically aimed at achieving the $1000 genome and an X prize to reward the first team to reach that mythical goal. There’s even a book for laymen entitled:

The $1,000 Genome: The Revolution in DNA Sequencing and the New Era of Personalized Medicine, by Kevin Davies

The book was published on Sept. 2010 and has received favorable reviews.

“Personalized medicine” involves sequencing your genome, and using that information to tailor the drugs you take for diseases which have a strong genetic component, like cancer. Many people are predicting that during the next decade, personalized medicine will become ubiquitous and indispensable in our health care. It could be a gigantic market. Imagine sequencing the genome of every person in an entire country (and that of your little dog too!).

But sequencing the genome of an individual is only the first step. One needs to interpret the results and compare them across wide populations. That means doing massive statistical analyses that require vast computational resources. I believe quantum computers could greatly help with this task, as QCs are ideally suited for doing statistical analyses. QCs can do sampling faster (with a more favorable time complexity) than classical computers (This is a subject near and dear to my heart. My “Quibbs” software is for doing Gibbs sampling with a QC).

“I’ll get you, my pretty — and your little dog too!”
The Wicked Witch of the West, The Wizard of Oz

June 9, 2011

Mark Wilde’s Magnum Opus

Filed under: Uncategorized — rrtucci @ 3:53 am

As I discussed in a previous post, the field of quantum SIT (Shannon Information Theory) has advanced by leaps and bounds in the last two decades. Recently, I’ve been studying quantum SIT for my research. I have found the early versions of Mark Wilde’s quantum SIT book, which he has been posting at his website under the Creative Commons License, to be really useful, truly pivotal to my research. And tonight, he has released his magnificent, monumental book (about 650 pages! hot dog!) on ArXiv.

From Classical to Quantum Shannon Theory, by Mark M. Wilde, arXiv:1106.1445

Oliver Heaviside was a giant in his field. He invented a large fraction of what we learn today in a modern ElectroMagnetism course. One of his many contributions to that field was to recast Maxwell’s equations from the original way Maxwell wrote them, as 20 quaternion equations, to the 4 div and curl equations that we use today. (If you’ve never seen them and are curious to do so, this article has a picture of the original 20 quaternion equations).

Heaviside got ahold of a copy of Maxwell’s treatise while it was still hot off the press, and it was a revelation to him. From the Wikipedia article on Heaviside:

In 1873 Heaviside had encountered James Clerk Maxwell’s newly published, and today famous, two-volume Treatise on Electricity and Magnetism. In his old age Heaviside recalled:

I remember my first look at the great treatise of Maxwell’s when I was a young man… I saw that it was great, greater and greatest, with prodigious possibilities in its power… I was determined to master the book and set to work. I was very ignorant. I had no knowledge of mathematical analysis (having learned only school algebra and trigonometry which I had largely forgotten) and thus my work was laid out for me. It took me several years before I could understand as much as I possibly could. Then I set Maxwell aside and followed my own course. And I progressed much more quickly… It will be understood that I preach the gospel according to my interpretation of Maxwell.[4]

Maybe this bit of history will repeat itself. Maybe you will fall in love with Mark Wilde’s excellent book while it is still hot off the e-press, and you will decide to devote your life to the study of quantum SIT.

Blog at WordPress.com.

%d bloggers like this: