Bayesian Networks + Information Theory = Papa-the-Camel’s Book

My religious epiphany for the week:
For those of you who, like me, are fans of both

• Bayesian Networks (a divine theory, also known by many other names, just like God/Yahweh/Allah etc. is) and

• Shannon Information Theory (SIT) (another divinely inspired theory),

here is an excellent book that merges these two fascinating topics. A preliminary draft of the book can be downloaded from ArXiv.

arXiv:1001.3404
Lecture Notes on Network Information Theory
Abbas El Gamal, Young-Han Kim

(I am told by my impeccable internet sources that “El Gamal” means “The Camel” in Arabic. “Abbas” means “papa”. It does remind me of capacity. Information Capacity Regions is a fascinating subject which the El Gamal/Kim book often discusses.)

The arxiv version of the book is quite adequate for many purposes, but a more polished version has recently been published (in fact, published just today! No stale news in this blog!) by Cambridge University Press. 714 pages of goodness. Amazon link to book

One of my lifelong goals is to build a quantum version of B.Nets and SIT, and to apply it to physics. I’m of course not the only one, or even the first one, to arrive at this idea. I see that Mark Wilde, a rising luminary of quantum information theory, already cites the El Gamal/Kim book in several of his arxiv papers. Good find Mark!

Abbas El Gamal is a professor at Stanford University. Stanford is one of the CHIMPS of quantum computing, meaning they haven’t done much in that area. On the other hand, Stanford is the home of Cover and Thomas, the authors of one of the canonical books on SIT, and also the home of Daphne Koller, coauthor of one of the canonical books about B nets. I think eventually Stanford will learn how to add simple things like
quantum + B.Nets + SIT + physics.

By the way, Stanford is also home of the indescribable Lenny Susskind, String Theorist extraordinaire, who, if my prediction for 2012 is right, will soon be singing Q-Comp, Q-Comp!. Once already, a few years ago, Lenny invited Scott Aaronson to speak at one of his String Theory shindigs, so Lenny has already shown some potential for conversion to our QC faith.

Unethical or Really Dumb (or both) Scientists from University of Adelaide “Rediscover” My Version of Grover’s Algorithm

This new paper

arXiv:1201.1707
An improved formalism for the Grover search algorithm,
by James M. Chappell (1,2) , M. A. Lohe (2), Lorenz von Smekal (3), Azhar Iqbal (1) and Derek Abbott (1)

1. School of Electrical and Electronic Engineering, University of Adelaide 5005, Australia
2. School of Chemistry and Physics, University of Adelaide, South Australia 5005, Australia
3. Institut f¨ur Kernphysik, Technische Universit¨at Darmstadt, Schlossgartenstraße 9, 64289 Darmstadt, Germany

“rediscovers” the fixed-point version of Grover’s algorithm that I invented and presented in the following paper:

arXiv:1001.5200
An Adaptive, Fixed-Point Version of Grover’s Algorithm,
by Robert R. Tucci

The Chappell et al. paper has 24 references but does not refer to my paper, even though their paper and mine are eerily similar. Compare them yourself. With the excellent Google and ArXiv search engines, I would say there is zero probability that none of its five authors knew about my paper before they wrote theirs. (I have also written multiple posts in this blog describing my algorithm and linking to my arxiv paper about it, so nobody can claim that it was kept well hidden)

Addendum Jan 16, 2012:
Now that my emotions have calmed down, I was able to look at the Chappell et al paper more carefully. Our algorithms are more different than I initially thought. I’m not sure yet if one algorithm is faster or more accurate than the other. They may be about the same, or they may not be. More analysis will be required to answer this. I still think Chappell et al should have mentioned my paper. I would have done so if I had been in their shoes. After all, my paper was published 2 years earlier than theirs, and it solves the same problem, albeit using a different strategy.

Of Bananas and String Theorists

I figured out how to distill the message of the previous post into an ape/monkey picture. (Ape/Monkey) Pictures make difficult concepts more intuitively understandable. They provide much guidance for physicists (and other primates).

My Prediction for 2012: Quantum Computerists Will Occupy String Theory Bastions Like Princeton’s IAS

Quantum Computer Programmers Too

“String theorists don’t make predictions, they make excuses” -Feynman (1918-1988)

In America during the 1960′s, the hippies and draft dodgers rose up against the powers that be. At present, a similar phenomenon is sweeping through many Islamic countries (the so-called Arab Spring), and America (the Occupy Wall Street protest movement). It seems that every 50 years or so, the young rise up against the ruling class elites and abusers of power.

I predict that in 2012, a new protest movement will bubble up from that boiling cauldron of unrest that is Academia, and start a new String Theory revolution.

I, Nostradamucci, see the future clearly. The end times. A world in turmoil. Four horsemen. QC barbarians at the String Theory ramparts. En masse occupation of IAS by quantum computerists. Mass defections from the String Theory ranks to the QC ranks. A Great Cheapening of the once venerable String Theory brand. The QC Winter. The end of innocence.

There have been some recent, very foreboding developments at the crossroads between high energy physics and quantum computing, that give my prediction an air of inevitability. Here are some of those ominous signs:

• In a previous blog post of mine,

  Set a Thief to Catch a Thief

  I gave a brief historical review of the idea of simulating quantum mechanical systems using a QC.

  There is a steadily increasing logjam of quantum mechanical theories (examples can be found in the fields of quantum gravity in general, String Theory in particular, relativistic quantum field theory, condensed matter physics, etc. ) that resist analysis in their strong and intermediate coupling regimes, regimes where an expansion in powers of the coupling constant fails to converge. So far nobody knows how to milk such theories very well.

  Perhaps if we could simulate such theories on some kind of computer, we could compare their predictions with laboratory measurements. We might then be able to discard or modify or refine those theories. We might also be able to simplify such theories to their sweet spot, the spot where they are simple enough that we can figure out how to solve them analytically, yet complicated enough that they still make useful predictions which agree reasonably well with the laboratory data.

  A QC would be the ideal device for simulating such currently intractable quantum theories. Feynman himself was the first to point out that using a QC instead of a classical computer to simulate a quantum system allows one to perform such simulations faster by a factor exp(n), where n is the number of bits in the input data. Also, no need for iffy Wick rotations. And QCs can simulate both the strong and weak coupling regimes of a theory with the same software code and with the greatest of ease.

• Recently, some researchers have proposed in the following paper, a method similar to the methods discussed in the above Thieves post, but this time for using a QC to simulate the phi^4 relativistic quantum field theory in 3+1 dimensions. They have worked out some of the nitty-gritty details of Feynman’s original dream:

  Quantum Computation of Scattering in Scalar Quantum Field Theories
  Stephen P. Jordan, Keith S. M. Lee, John Preskill

  Papers that give methods for doing QC simulations of quantum field theories that also include fermions and gauge fields, are no doubt being written as we speak. Much work remains to be done in this area. All the details of how one would simulate a String Theory on a QC remain undiscovered yet. Maybe you will be the one who finds them.

• Lattice Gauge Theories were invented circa 1974 by Ken Wilson and others. It has taken scientists many decades of grueling work, using Monte Carlo techniques on classical supercomputers, to simulate lattice QCD (Quantum Chromodynamics), and to derive the mass spectra predicted by it. Imagine if QCs could do all that work in seconds.

  On classical computers, to reduce the computational-resource requirements to a non-prohibitive size, one is often forced to butcher the fermionic degrees of freedom of the lattice gauge theory by using ugly, poorly understood approximations. This would not be necessary if the simulations were done on a QC.

  QCs can do Monte Carlo much faster than classical computers, a fact which I’ve explained in many previous posts in this blog, and which I exploit in my own QC Gibbs sampling software called Quibbs.

• Recently there have been some paltry attempts to use disgustingly classical supercomputers to try to squeeze out some straight answers from String Theory. Quantum computers could do such analyses much more quickly, accurately and painlessly.

• New Source of Funding: As Kermit the frog is fond of saying, it’s not easy being green (or a string theorist). String theory is a hard subject to sell to the general public. No verified quantitative predictions so far. No practical applications. But if string theorists start selling themselves by saying that we are helping to develop quantum computers at the same time that we explore our theory, they might get some new buyers. Even the military and DARPA, which don’t normally fund string theorists, might bite.

• An anonymous quantum computerists, probably an ex-physicist working in Wall Street, recently sent me the following wordy, demented manifesto for a protest movement that he is trying to start:

  We are the 99% who are not String Theorists. Let’s now define the set of people who are not String Theorists as being Quantum Computerists, just like Lilliput had its Big Enders and Small Enders. We Quantum Computerists believe that String Theorists who work at primo places like Princeton’s IAS (the Institute for Advanced Study, where Ed Witten works, where Einstein and Godel once worked, a place rated by Sidney Coleman as the most boring town he has ever lived in) control too much of the wealth (in funding booty, post doc slaves and public imagination) of physics. And so far String Theorists have squandered that wealth and patrimony.

  Let’s face it, investments in String Theory were a huge gamble from the very beginning—I mean, even at its christening, Feynman didn’t give his blessing to John Schwarz’s baby, but Feynman certainly did give his blessing to his own baby, quantum computing.

  String Theorists have failed miserably to balance their books (no good quantitative agreement between the two sides of the ledger, theory and experiment). But they are not being held accountable for their poor book-keeping practices. They continue to be bailed out by the government because their business is considered too big to fail, according to Peter Woit.

  Even after the Great Recession caused by multiverse ideas, most String Theorists still deny that they ever did anything wrong. They continue to do business as usual, steadfast in their Enron-esque opinion that they are the smartest people in the room, and, therefore, they can do no wrong. Well, I’ve got news for them, some quantum computerists (most notably the complexity theorists) think they are even smarter. (note from rrtucci: Leave me out of it. I belong to the 99% of the 99% who are as blissfully dumb as Ed Witten’s hamster.)

  We quantum computerists are not against laissez faire capitalism. That would be like being against truth, justice and the American way. So we are not against String Theory per se either, or against any other lesser theories of quantum gravity. What we deplore is that the gains made by String Theorists in the past few decades are not trickling down to us.

  Let’s face it. String Theory is as transparent as a Credit Default Swap. Perhaps quantum computerists can make String Theory more transparent by simulating various facets of it on a quantum computer?

One Blog is Worth a Thousand Conferences (said by Confused-cius, circa 500 BC)

This blog is mostly about quantum computing(1). Nevertheless, the medium —in this case blogging— always becomes part of the message. So I decided to pay homage to blogging by scouring the WWW and collecting from it cartoons about blogging that I especially liked. This is but a small sample. There are lots of good ones out there about the subject.

I believe reading blogs benefits many people. (I for one get a lot out of reading them.) A blog (especially if used in combination with ArXiv) is a very efficient way of disseminating scientific information to the general public and to the blogger’s peers. It is an excellent vehicle for one to explain the motivation behind one’s work, and for answering other people’s questions about that work. It’s also very good for discussing other people’s work.

Scientific conferences, on the other hand, I view less favorably. For one thing, conferences seem to be harder to opt out of, if you don’t like them, once you are there. In our times, now that it’s possible to communicate so easily, quickly and comprehensively between almost any two points on earth, physical conferences seem to me a bit antiquated. A big bit. Perhaps even an anachronism. This suggests the question, should physical conferencing be updated or simply abolished? I bet Steve Jobs would have immediately replied abolished. But Steve Jobs was a visionary who got things done, and such people are few and far between in Academia. Academia changes at a glacial pace compared with technology and industry. Academics are very slow learners about their own system.

(1) By this I mean it’s not about carpentry or home gardening, it’s not about every single topic under the sun that interests me, and it’s for the most part not about me. I try to keep this blog sharply focused on quantum computing. There are lots of blogs on the web that are of a more personal nature, and I myself much enjoy some blogs that are like that, but this one isn’t intended to be very personal. Of course, a blog is like a big bay window into a blogger’s inner soul, whether he wants it or not, but in this blog, I try to avoid as much as possible talking about myself (and my dark past…), except when I talk about my work on quantum computing.

Q Comp, Q Comp! (New York, New York!)

In this blog, I frequently argue for REAL QC programming (instead of QC programming vaporware). Frank Sinatra was also very interested in QC programming. One of his most famous songs is about the very subject. Here are the lyrics.

Q Comp, Q Comp! (New York, New York!)

Start spreading the news (Start spreading the news)
I’m q coding now, (I’m leaving today)
I want to be a part of it (I want to be a part of it)
Q Comp, Q Comp (New York, New York)

Make parallel moves (These vagabond shoes)
Like Schroedinger’s meow (Are longing to stray)
And pass right through pesky barriers (And step around the heart of it)
Q Comp, Q Comp (New York, New York.)

I want to write in a Q language (I want to wake up in a city,)
that doesn’t suck, (That doesn’t sleep,)
To find the min of the hill- ah- (To find I’m king of the hill- ah-)
Least of the heap. (Top of the heap.)

My classical views (My little town blues)
Are melting away (Are melting away)
I’m gonna make a brand new start of it (I’m gonna make a brand new start of it)
In weird Q Comp. (In old New York.)
If I can make it there, (If I can make it there,)
I’d make it anywhere (I’d make it anywhere)
It’s up to you, (It’s up to you,)
Q Comp, Q Comp. (New York, New York.)

Important news in the QC programming area: Recently, D-Wave opened a “developer portal“. A very good move, in my opinion. It’s sure to benefit not only D-Wave, but the field of QC programming as a whole. (Henning Dekant has an insightful blog post about it here) I hope that we will soon witness the emergence of even more portals into this new dimension.

Extra, Extra, Read All About It: Decoherence Times of Latest Superconducting Qubits Now Very Close to Times Needed For Quantum Error Correction

Check out

Viewpoint: Superconducting Qubits Are Getting Serious
by Matthias Steffen, December 5, 2011 / Physics 4, 103 (2011)

(The html version of Steffen’s article is a bit mangled at the present time, but you can download (for free) the pdf version and that one is just peachy.)

This excellent article by Herr Doktor Matthias Steffen (at IBM) reviews the following paper by a group of people from Yale Univ.:

Observation of High Coherence in Josephson Junction Qubits Measured in a Three-Dimensional Circuit QED Architecture, by Hanhee Paik, D. I. Schuster, Lev S. Bishop, G. Kirchmair, G. Catelani, A. P. Sears, B. R. Johnson, M. J. Reagor, L. Frunzio, L. I. Glazman, S. M. Girvin, M. H. Devoret, and R. J. Schoelkopf

The first superconducting qubit, built in 1999, had decoherence times of about 1 nanosecond. The Yale group has demonstrated superconducting qubits with relaxation times T1 = 60 μs and dephasing times T2 = 20 μs. That’s an improvement by a factor of 10,000 in ten years! Mamma Mia! Hot Dog! (Gate model-) quantum computers are so close, I can taste them!

Compare this to the decoherence times of 4 μs for the resonators of UCSB’s von Neumann architecture which I described in a previous blog post (in English, in Spanish ). The Yale qubits are bigger than the UCSB ones and they are enclosed in a 3 dimensional cavity. (See original Yale paper for a picture of their setup with dimensions indicated.)

Steffen estimates that the new Yale decoherence times slightly surpass what is needed for doing quantum error correction. And he believes that there is still plenty of room for improvement. It appears that no fundamental roadblocks have been encountered yet, although the sources and mechanisms of decoherence are still not well understood.

P.S. The “Viewpoint” articles of the APS (American Physical Society) are one of my favorite online overviews of leading edge physics. They are carefully written by an expert in the field. They contain references to the original papers. They are broader, briefer and less technical than the original papers. But they are much more technical, accurate and detailed than the garbage one reads in most university press releases or popular science articles. Plus they are freely available on the Internet. I’d like to congratulate APS for a brilliant idea, and I hope that for a very long time, they continue to perform this service which is so valuable to science.

California Dreaming

Recently, Californian universities UCSB and USC have been making great strides in quantum computing. Those quantum computerists who work at IQC (in Waterloo, Canada) may enjoy this song. (I much enjoy the song myself. I also enjoy throwing a monkey wrench into Perimeter/IQC’s hyperactive, vaporous publicity machine )

California Dreaming (by the Mamas and the Papas)

all the leaves are brown
and the sky is grey
I’ve been for a walk
on a winter’s day

I’d be safe and warm
if I was in L.A
California Dreamin’
on such a winter’s day

stopped into a church
I passed along the way
well, I got down on my knees
and I pretend to pray

you know the preacher likes the cold
he knows I’m gonna stay
California Dreamin’
on such a winter’s day

all the leaves are brown
and the sky is grey
I’ve been for a walk
on a winter’s day

if I didn’t tell her
I could leave today
California Dreamin’
on such a winter’s day x3

Il Trionfo Di King Kong (The Triumph of King Kong)

“King Kong vs. Godzilla” (1962) is a Japanese movie which has been translated to more languages than the Bible. (Eat your heart out Akira Kurosawa) As one might expect, there is an extensive Wikipedia entry for this important cultural classic. Here are some of its original movie posters, in various languages.

If you want to see many more posters for this movie, go here.

Ahhh, they don’t make movies like they used to. 

Who wins the fight? I promise not to tell. 

Currently there is a titanic battle raging on between Geordie Rose (alias King Kong, founder and Chief Technology Officer of D-Wave), and Scott Aaronson (alias Godzilla, or just God to his converts, MIT professor of theoretical computer science). 

We were taught in English class to look for the deep symbolism in everything mentioned in a novel, even if it’s a Harry Potter novel, for crying out loud. So let’s say that in this case, for the purposes of this, my book report, I’ll say that Geordie Rose symbolizes QC Industry and Scott Aaronson symbolizes QC Academia. 

One would think that Academia and Industry would be natural friends and allies. But for some reason, they aren’t. They are always poopooing each other. Besides, Society is goading them to fight on. She enjoys watching a good death-match between two gladiators. 

Recently Geordie/King Kong/Industry has been throwing some heavy barrels in the direction of Scott/Godzilla/Academia. In modern times, we need a photo, taken with an iPhone, to corroborate what we are saying, to capture the moment and post it on Facebook. So here is a photo capturing the moment.

Of course, this photo is deeply symbolic of something or other. Indeed, it symbolizes that recently Geordie/King Kong has landed some painful punches on Scott/Godzilla. Six months ago, King Kong signed a 10 million dollar contract with Lockheed Martin, and this week he has finished installing one of his computers at USC (University of Southern Calf.) at Marina del Rey, thus creating the first Quantum Computing Center ever. One can imagine how Shakespeare would have seen it: 
Industria: “Eateth thy heart out, MIT”. 
Academia: “Et tu, USC-Brute? Then fall, MIT-Caesar!”. 
USC’s California weather sure beats MIT’s crappy Boston weather. MIT should thank God for IQC at Waterloo (whose weather is even crappier). 

King Kong is also doing some REAL quantum computer programming instead of the ersatz variety. He is fostering the field of quantum computer programming by opening a “developer portal“. Very nice move, King Kong! 

I wouldn’t discount Godzilla yet, though. He might get as angry as a hornet’s nest, and respond with a surprise hook to the jaw. He might unleash upon King Kong a terrifying theorem that gives a lower bound on the complexity of an algorithm that solves some obscure problem that no one has ever heard of. 

By Jove! A String Theory Boffin is Selling Quantum Computers on the Telly!!!???

Brian Greene, not to be confused with the wonderful dead British writer Graham Greene, is a String Theorist. (Audience reaction may vary here, running from Gulp to Wow-Wee to Huh? to Yawn to Yuck).

Brian “the Brain” Greene has written many technical papers on String Theory and 4 popular science books about the subject. Public television in the US (PBS) is currently airing a “Nova” TV documentary with Brian Greene as the main narrator. It’s a series of 4 one-hour-long episodes, mostly about high energy physics, titled “The Fabric Of the Cosmos”. It’s an uneven series. For instance, I thought Episode 2, titled “The Illusion of Time”, was really crappy—very shallow, often misleading and incorrect in the physics (Lubos Motl wrote a blog post with which I mostly agree, that describes some of the serious flaws in the physics of Episode 2).

Okay, but this is a family blog about quantum computing. All the quantum computing news (or at least some of it) that’s fit to print, all the time. WTF does a documentary by a String Theorist have to do with quantum computing?

The answer is Episode 3, titled “Quantum Leap”. I thought it was much better than Episode 2. It gives a very nice introduction, for non-scientists, to quantum mechanics: its history, how we arrived at it, why we are stuck with it whether we like it or not (like your mom was with you), why it’s weird, what is quantum entanglement, what is quantum teleportation, what is the promise of quantum computing. You also get to hear the voices and see the faces of some famous people in the field. (The human interest angle.)

If you haven’t seen Episode 3, I recommend it. Here is the PBS webpage for the series.

Perhaps Episode 3 is a bit too glitzy or gimmicky for you. It’s debatable whether all those computer generated visual enhancements help you to understand physics better, or distract your attention from the essential points. Sometimes a crude, black and white, hand drawn cartoon or animation is much more instructive and beautiful than all the computer graphics in the world.

If you want a less high-tech, but super excellent introduction to quantum mechanics for the general public, I recommend Feynman’s Messenger lectures.

I’d also like to mention here one of my all-time-favorite science TV documentaries, “The Secret Life of Machines” (quantum computers is machines, not math! Soylent Green is people!)