Quantum Bayesian Networks

December 29, 2012

2012 Nobel Lectures for QC

Filed under: Uncategorized — rrtucci @ 6:48 am

Nobel Physics Lectures are probably a bit too technical for non-physicists, but, for physicists, they are always worthwhile watching. One can be confident that they will be well prepared (Nobel prize winners don’t just pull an all-nighter the night before their Nobel lecture to get their powerpoint presentations finished. These darn things will follow them for eternity). And the people delivering these lectures certainly know their stuff well. This year’s Physics Nobel Prize of course went to experimental quantum computing (Eat your heart out HEP! Pow!…Take that Yuri Milner and String Theorists!). Check out the 2012 Physics Nobel Prize lectures

Besides physics, you will learn a bit of the history of the field from people who participated in it. Plus you might get a feeling for what these 2 guys are like.

December 21, 2012

The Boson Sampling Flying Machine Race Is On!

Filed under: Uncategorized — rrtucci @ 8:48 pm

magnificent_men_posterAt the risk of being accused of fronting for Scott Aaronson’s mother, I’d like to say that I think Boson Sampling is a really cool idea. To PROVE mathematically that quantum computers can perform certain calculations faster than classical computers. To show that a sacrosanct hypothesis of some people, the (Extended) Church-Turing thesis, is wrong. What could be more exciting? It reminds me of the experiments that measured clear violations of Bell’s inequality and thus proved mathematically that hidden variable theories of quantum mechanics are kaput and verboten.

I find boson sampling a much more worthy goal for quantum optics jocks to pursue than quantum crypto and quantum internet, which seem pointless to me.

On Dec 10 and 11, 2012, we were deluged with 4 ArXiv papers on boson sampling experiments:

If you are a quantum optics experimentalist, it’s time for you to join the race!

Chinese (1 measly member) and American (2 measly members) participation is so far anemic. But just wait until those two lame countries read this blog post and have their national prides badly bruised. And wait until they both realize that boson sampling can be used to improve bombs and spying devices.

So far, the experiments are limited to only 3 photons and 6 ports. To show beyond the shadow of a doubt that QCs can outrun classical computers, it is estimated that about 30 photons will be needed.

Is this the end of the road? Will these teams give up after plucking the lowest fruit of the tree (3 photons), or will they stick with it until they achieve 30 photons?

Will other teams join the fray?

How long will it take to reach 30 photons? 100 years? 2 years?

What nation will win the power and the glory?

My previous blog posts about Boson Sampling

December 15, 2012

The CERN Mutiny

Filed under: Uncategorized — rrtucci @ 6:41 am

bogart-caine-mutiny-monologueA monologue from the film The Caine Mutiny (1954).

(Captain Queeg, a SUSY Theorist, removes the steel balls from his pocket and spins them insistently in his hands as he speaks.)

Queeg (Humphrey Bogart):
No, I, I don’t see any need of that. Now that I recall, he might have said something about messboys (messy theories) and then again he might not — I questioned so many men and Harding was not the most reliable officer.

Lt. Greenwald (Jose Ferrer):
I’m afraid the defense has no other recourse than to produce (experimentalist) Lt. Harding.

Now there’s no need for that. I know exactly what he’d tell you, lies. He was no different from any other officer (experimentalist) in the ward room, they were all disloyal. I tried to run the ship properly, by the book, but they fought me at every turn. The (CERN) crew wanted to walk around with their shirt tails hanging out, that’s all right, let them. Take the tow line (LHC), defective equipment, no more, no less. But they encouraged the crew to go around scoffing at me, and spreading wild rumors about steaming in circles (circular theories) and then old yellow stain (in my pants). I was to blame for (Experimentalist) Lt. Maryk’s incompetence and poor seamanship (computer programming skills). Lt. Maryk was the perfect officer(physicist), but not Captain Queeg. Ah, but the strawberries Higgs, that’s, that’s where I had them, they laughed at me and made jokes, but I proved beyond the shadow of a doubt, and with geometric logic, that a duplicate key to the ward room icebox (a natural SUSY theory that fitted their data) did exist, and I’ve had produced that key(SUSY theory) if they hadn’t pulled the Caine (LHC) out of action. I, I know now they were only trying to protect some fellow officer (their bacon). … Naturally, I can only cover these things from memory. If I left anything out, why, just ask me specific questions and I’ll be glad to answer them, one by one.

December 7, 2012

Synergetic Ears

Filed under: Uncategorized — rrtucci @ 9:48 pm

The topic of monogamy has been recently in the news, and I’m not referring to the mormons. John Preskill, our own quantum information theory Jedi master, has extolled the virtues of monogamy in a recent blog post of his about the black hole information paradox. And Eric Verlinde, a recipient of 30 million dollars in research grants, courtesy of the Dutch government, at a time when Europe is on the brink of bankruptcy, for his so-far-only-a-pipe-dream theory of entropic quantum gravity, has recently advocated monogamy in a paper of his. But wait…What’s this? Lubos Motl thinks Eric Verlinde’s paper is junk. All this drama is a great excuse for me to preach about monogamy, a virtue which you might agree with even if you are clueless about black holes and quantum gravity.

I’ll use the ampersand symbol \& to denote entanglement, because this symbol looks pretty tangled to me, and, besides, so many other things in physics (like energy and electric field) are already represented by the letter E. Besides, the ampersand looks like an E because it was originally meant to abbreviate the Latin “Et”, which means “and”.

The CMI or squashed entanglement for the “random variables” \underline{a} and \underline{b} in the mixed state \rho_{\underline{a},\underline{b}} is defined by

\&_{\rho_{\underline{a},\underline{b}}} (\underline{a},\underline{b}) = \frac{1}{2} {\rm min}_{\underline{\Omega}} \;\; S_{\rho_{\underline{a},\underline{b},\underline{\Omega}}} (\underline{a}:\underline{b}|\underline{\Omega}).

Here S_{\rho_{\underline{a},\underline{b}, \underline{\Omega}}} (\underline{a}:\underline{b}|\underline{\Omega}) is the quantum CMI. The minimum is over all density matrices \rho_{\underline{a},\underline{b},\underline{\Omega}} which yield \rho_{\underline{a},\underline{b}} when you trace over \underline{\Omega}. If you think about it, this is basically minimizing over “all possible” random variables \underline{\Omega}.

The 1/2 factor in the definition of squashed entanglement is a normalization convention, used so that \&(\underline{a},\underline{b})=S(\underline{a})=S(\underline{b}) when \rho_{\underline{a},\underline{b}} is a pure state. Indeed, when \rho_{\underline{a},\underline{b}} is a pure state, S(\underline{a})=S(\underline{b}) (by the Schmidt decomposition). By definition,

S(\underline{a}:\underline{b}|\underline{\Omega}) =S(\underline{a}|\underline{\Omega}) + S(\underline{b}|\underline{\Omega})-S(\underline{a},\underline{b}| \underline{\Omega}).

Minimizing both sides of this equation over \underline{\Omega} when \rho_{\underline{a},\underline{b}} is a pure state yields

2\&(\underline{a},\underline{b})= S(\underline{a}) + S(\underline{b}) + 0= 2S(\underline{a}).

Next we shall consider the following inequality, which was first proposed by Coffman, Kundu and Wootters (CKW) in a 1999 paper:

\&(\underline{a}:\underline{b_1}) + \&(\underline{a}:\underline{b_2}) \leq \&(\underline{a}: \underline{b_1},\underline{b_2})

CKW proved this inequality for pure states. They didn’t prove it for mixed states because squashed entanglement had not been invented yet. Nowadays we know that squashed entanglement satisfies the CKW inequality for mixed states.

The proof that squashed entanglement satisfies the CKW inequality for mixed states is a very simple one line proof. Here it is: By the chain rule,

S(\underline{a}:\underline{b_1},\underline{b_2}|\underline{\Omega})= S(\underline{a}:\underline{b_1}|\underline{b_2},\underline{\Omega}) + S(\underline{a}:\underline{b_2}|\underline{\Omega}).

Minimizing both sides of this equation over \underline{\Omega} immediately yields the CKW inequality.

The CKW inequality implies the monogamy principle, although it implies much more than that. The monogamy principle says that if \underline{a} is maximally entangled with \underline{b_1}, then \underline{a} must have zero entanglement with any other random variable \underline{b_2}. To see how this principle must follow from the CKW inequality, note that if \underline{a} is maximally entangled with \underline{b_1}, then \&(\underline{a}:\underline{b_1})= \&(\underline{a}:\underline{b_1},\underline{b_2})=S(\underline{a}) so CKW implies that \&(\underline{a}:\underline{b_2})=0.

I like to think of squashed entanglement \&(\underline{a}:\underline{b}) as the correlation (or transmitted information) between two people (or events) \underline{a} and \underline{b} conditioned over and minimized over all possible observers \underline{\Omega}. In terms of this narrative, what the CKW inequality is saying is that a message is “heard” better if person \underline{a} sends a single message to a joint delegation of two people \underline{b_1} and \underline{b_2}, instead of sending separate messages to \underline{b_1} and \underline{b_2}. It’s what people call a synergetic or superadditive effect.

Here is a CMI cartoon representation of the CKW inequality.

The message sender \underline{a} is given a megaphone and the receivers (listeners) \underline{b_1} and \underline{b_2} are given ears. A single receiver listening alone has just one ear. Two receivers listening as a joint delegation have 3 ears! I like to call this picture of the CKW inequality “Synergetic Ears”.

December 2, 2012

CMI Cartoons

Filed under: Uncategorized — rrtucci @ 9:53 am

MI and CMI are measures of correlation that are frequently used in classical and quantum SIT (Shannon Information Theory). MI stands for Mutual Information. CMI stands for Conditional Mutual Information (you can pronounce CMI as “see me”). MI and CMI obey many identities and inequalities that are very useful. For example, MI and CMI are always non-negative. I’ve waxed poetic about CMI many times before in this blog. For example, in the following post:

CMI, the Universal Translator Built by the SIT-ian Race

The thing that I want to discuss now that I haven’t discussed before is a pictorial way of representing CMI identities and inequalities.

In quantum SIT, CMI is used to define squashed entanglement. Squashed entanglement seems to occupy a privileged position in the pantheon of entanglement measures because it’s the only known definition of entanglement that obeys the Monogamy Inequality for mixed states, something considered to be a very desirable trait for an entanglement measure. I’ll talk more about squashed entanglement and prove that it satisfies monogamy in a future post, but in this post I’ll restrict myself to speaking mostly about classical SIT. I’ll do this only for simplicity. Let me emphasize that everything that I say in this post generalizes easily to quantum SIT.

Let me review some definitions. I’ll represent random variables by underlined letters. In classical SIT, one defines

  • the entropy (i.e., the variance or spread) of \underline{a} by
    H(\underline{a}) = \sum_a P(a) \log \frac{1}{P(a)},

  • the conditional spread (of \underline{a} given \underline{b}) by
    H(\underline{a} |\underline{b}) = \sum_{a,b} P(a,b) \log \frac{1}{P(a|b)},

  • the mutual information (MI) (i.e., the correlation) between \underline{a} and \underline{b} by
    H(\underline{a}:\underline{b}) = \sum_{a,b} P(a,b) \log \frac{P(a,b)}{P(a)P(b)},

  • the CMI by
    H(\underline{a}:\underline{b}|\underline{c}) = \sum_{a,b,c} P(a,b,c) \log \frac{P(a,b|c)}{P(a|c)P(b|c)}.

Classical Bayesian networks (CB nets) are (directed acyclic) networks of random variables. In the slide below, I portray a typical CB net with nodes labeled by the random variables \underline{a} through \underline{g}. Then I show how to represent an MI and 2 CMIs for that CB net.


One can represent a CMI right on the CB net, but for simplicity I’ve represented the CMI in a diagram that doesn’t contain some of the nodes and that contains none of the lines with single arrowheads that belong to the CB net.

The convention is clear. Let us say CMI has 3 slots H(slot_1: slot_2| slot_3).

  • lines with single arrowheads: belong to the CB net
  • lines with no arrowheads: one of them connects all the random variables in the first slot of CMI. Another connects all the random variables in the second slot of CMI
  • lines with arrowheads at both ends: connect all variables in slot 1 with all variables in slot 2.
  • double circled nodes: correspond to the random variables in slot 3.

In the slide below, I show how to represent two examples of the chain rule for CMI.


Quantum Bayesian networks (QB nets) are a generalization of CB nets to quantum mechanics. The above two slides are for CB nets. However, very similar results hold for QB nets. That is one of the cool things about QB nets. That one can easily translate a CB net to its counterpart QB net or vice versa. This facilitates comparisons between the classical and quantum cases.

Blog at WordPress.com.

%d bloggers like this: