Quantum Bayesian Networks

March 31, 2012

Dogs is people too, and bluffing a pride of lions

Filed under: Uncategorized — rrtucci @ 11:57 am

This is very technical and nerdy, but I find it really cool.

Recently, Carlen and Lieb proved a very nice inequality for entanglement. Check out

Bounds for Entanglement via an Extension of Strong Subadditivity of Entropy

by Eric A. Carlen, Elliott H. Lieb

Let me try to summarize their main result.

Consider a bipartite density matrix \rho_{12}, and define \rho_1 = {\rm tr_2}\rho_{12} and the same with 1 and 2 swapped. Suppose S_{12} is the von Neumann entropy of 12, S_{1} is that of 1 and S_{2} is that of 2. Call the classical counterparts of these entropies H_{12}, H_{1} and H_{2}. Call S_{2|1} = S_{12} - S_1 (respectively, H_{2|1} = H_{12} - H_1) the quantum (resp., classical) conditional spread (or conditional variance) of 2 given 1.

One can show that

H_{2|1}\geq 0,
H_{1|2}\geq 0

so classically, conditional spreads must be positive (or zero). However, in quantum mechanics such spreads can be negative. The Araki-Lieb inequality S_{12}\geq |S_1-S_2| says that

S_{2|1}\geq -S_2,
S_{1|2}\geq -S_1.

Now, having a negative conditional spread is a bit of a dog, because spreads are not supposed to be negative.

The new Carlen/Lieb inequality teaches us that dogs can count too. If E is entanglement (either entanglement of formation or squashed entanglement), then, according to Carlen/Lieb,

E\geq max(-S_{1|2}, -S_{2|1}, 0)

So a dog (i.e, a negative conditional spread S_{1|2}<0) forces the entanglement to be greater than zero by -S_{1|2}. An example of a highly influential dog.

P.S. I recently wrote some email to Profs. Lieb and Carlen asking them something about their paper. I felt infinitely dumb in their email presence, like a mouse in the presence of lions (As you probably know, The Lion and the Mouse is a beautiful fable by Aesop.) But I believe I successfully muddled and bluffed my way through the conversation. Amazing but true, it is possible to bluff a pride of lions. If you don’t believe me, watch this amazing YouTube video, entitled “BBC – Men stealing meat from lions”. In the video, 3 extremely courageous and also extremely foolish African guys, with scant weapons other than their daunting audacity, intentionally walk right into the middle of a pride of lions that is having dinner.

March 15, 2012

Judea Pearl Wins Turing Award For Bayesian Networks

Filed under: Uncategorized — rrtucci @ 6:46 pm

Check out

A Turing Award for Helping Make Computers Smarter
By Steve Lohr (New York Times, March 15, 2012)


Google search, I.B.M.’s Watson Jeopardy-winning computer, credit-card fraud detection and automated speech recognition.

There seems not much in common on that list. But it is a representative sampling of the kinds of modern computing chores that use the ideas and technology developed by Judea Pearl, the winner of this year’s Turing Award.

Dr. Pearl, 75, a professor at the University of California, Los Angeles, is being honored for his contributions to the development of artificial intelligence.

In the 1970s and 1980s, the dominant approach to artificial intelligence was to try to capture the process of human judgment in rules a computer could use. They were called rules-based expert systems.

Dr. Pearl championed a different approach of letting computers calculate probable outcomes and answers. It helped shift the pursuit of artificial intelligence onto more favorable terrain for computing.

Dr. Pearl’s work on Bayesian networks — named for the 18th-century English mathematician Thomas Bayes — provided “a basic calculus for reasoning with uncertain information, which is everywhere in the real world,” said Stuart Russell, a professor of computer science at the University of California, Berkeley. “That was a very big step for artificial intelligence.”

Of course, I believe Bayesian networks are highly relevant to quantum computing and quantum Shannon Information theory. Quantum Mechanics is, after all, just another probability theory.

I first heard of Bayesian Networks from Bill Gates, founder of Microsoft.

Okay, Okay, I don’t really know the guy. I don’t even know his chauffeur. Nevertheless, there is some kernel of truth, this time at least, to my statements.

Since that day, forever etched in my memory, when I overheard Bill Gates’s boffo remarks about Bayesian Networks, I have been a devoted fan of them, especially of their quantum version. My very first paper in ArXix is entitled, appropriately enough, “Quantum Bayesian Nets”. My understanding of q-b-nets has increased quite a lot since that paper. Many of my subsequent papers have dealt with q-b-nets (better than cabinets). Sometime ago, I wrote a Mac application called “Quantum Fog” that does quantum Bayesian networks. (It uses algorithms of exponential complexity so it is only intended for pedagogical purposes. ) And of course, this blog is named after qbnets, and many of its post are about the very subject.

Addendum: Above, I only mentioned Judea Pearl’s work on Bayesian networks. More recently, Pearl has also written some papers and a book on his own theory of causality (which is an extra structure built on top of the foundation of Bayesian networks). However, to date, his theory of causality (“causality calculus”) has been used by others MUCH less frequently than his previous work on Bayesian networks, especially in industrial computer applications.

March 9, 2012

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

Filed under: Uncategorized — rrtucci @ 6:13 am

I am currently trying very hard to write a long, crazy paper on quantum SIT (Shannon Information Theory). So I’m thinking a lot about SIT these days. Here is a short “song” about the subject.

Sometimes two parties cannot understand each other without the help of an intermediary.

When the two parties involved are made of people, we human beings have invented clever devices and human professions whose goal is to intervene, and mediate a transaction between the two parties. For example,

  • devices – Rosetta stone, translation dictionaries, Google’s Translate, DARPA’s TRANSTAC, Universal Translator in “Star Trek” (and many other sci-fi stories), C3PO in “Star Wars”, dog2human translation devices in “Up”…
  • people – nearly simultaneous, human translators and interpreters of languages, sign language interpreters, marriage brokers and matchmakers, conflict mediators, divorce lawyers, judges…

When the two parties involved are objects instead of people, we often come up with devices to mediate transactions (e.g, electronic transistors, fluid valves, bridges,…)

Star Trek's Universal Translator (looks like a cordless microphone)

Since SIT (Shannon Information Theory) is an attempt to model in a very general way the communication of information between several parties, it’s not surprising that SIT has its own universal translator. Indeed, in SIT one defines a “universal translator function” called the CMI (Conditional Mutual Information), pronounced by me as “see-me”. CMI, denoted here by H(\underline{a}:\underline{b}|\underline{c}), is a real valued function with 3 slots filled by the random variables \underline{a}, \underline{b}, \underline{c}. (In what follows, we will indicate random variables by underlining.) In H(\underline{a}:\underline{b}|\underline{c}), \underline{a}, \underline{b} are the two parties that are having trouble understanding each other and \underline{c} is the mediator.

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)}.

But note that H(\underline{a}), H(\underline{a}|\underline{b}) and H(\underline{a}:\underline{b}) can all be expressed in terms of the CMI. Indeed,

H(\underline{a}) = H(\underline{a}:\underline{a}|empty)

H(\underline{a}|\underline{b}) = H(\underline{a}:\underline{a}|\underline{b})

H(\underline{a}:\underline{b}) = H(\underline{a}:\underline{b}|empty)

So the spread, conditional spread and MI are all just special cases of CMI.

CMI has many nice properties, by which I mean that it satisfies some cool equalities (a.k.a. identities) and inequalities.

One identity that I find really neat is

H(\underline{a}|\underline{c}) = H(\underline{a}:\underline{x}|\underline{c}) + H(\underline{a}|\underline{x},\underline{c}).

I usually remember this one by the mnemonic :\underline{x} + |\underline{x} = 1. Basically, this identity is saying to me that the spread of \underline{a} can be decomposed into a correlation (of \underline{a} and \underline{x}) plus a conditional spread (of \underline{a} given \underline{x}).

Another cool identity satisfied by CMI is the chain rule, which says basically that the “:” operator behaves sort of like a differential operator.

CMI also satisfies a slew of cool inequalities; for instance, CMI >= 0, the data processing inequalities, Fano’s inequality, and subadditivity (a.k.a. the independence bound).

This blog post is just a quick introduction to CMI. For a more complete discussion of CMI, you might consult the SIT textbooks mentioned below.

Almost every statement in both Cover&Thomas’ book and Papa the Camel’s book, two great books on classical SIT, involves CMI (or one of the aforementioned special cases of CMI). Thus, CMI is pretty universal!

So far we have discussed classical CMI. One can also define a quantum version of CMI. The quantum version of CMI again shows up almost everywhere in Mark Wilde’s very complete book on quantum SIT. (By the way, Mark’s book is excellent and free.)

Quantum CMI can even be used to define quantum entanglement.

There are, however, correlations between 4 or more random variables that cannot be expressed in terms of CMI. (or can they be?) So the fact that most of the classical and quantum SIT books talk almost exclusively about CMI does not mean that CMI is the most general SIT function possible, and that all others can be expressed in terms of CMI. It just means that most of our current SIT-ing knowledge involves correlations of <= 3 random variables, because that is the lowest fruit in the tree of SIT. So there are limits to the universality of CMI. Our universal translator is not perfect, but it’s the best one we have on board the starship Enterprise.

Are you a CMI user, a.k.a. a CMI-an? (pronounced the same way as the word “simian”)

March 1, 2012

Purveyors of Quantum Bustle Skirts

Filed under: Uncategorized — rrtucci @ 9:54 pm

Check out the following article

Secret codes ready to take quantum leap in space
(Mar 2012, MSNBC) By Jeremy Hsu


“If we can build these quantum key distribution systems and make them global, we will be able to transfer information in such a way that if there’s a hacker who tries to find this information, we will know,” said Raymond LaFlamme, director of the Institute for Quantum Computing at the University of Waterloo in Ontario. “Then we will be able to find a better way to encrypt that bit of information.”

The European Space Agency has even pushed for a “QUEST” space experiment that would test quantum communication to and from the International Space Station. Researchers discussed such ideas during the annual meeting of the American Association for the Advancement of Science in Vancouver on Feb. 19.

The Canadian Space Agency is working on plans for its Quantum Encryption and Science Satellite, while the European Union has teamed up with China’s Academy of Sciences for an intercontinental quantum key distribution test. The European Union also continues to work on using the space station to transfer a quantum key between ground stations separated by 870 miles.

Meanwhile, Japan has been running its own Earth-based quantum key distribution network in Tokyo. The country could launch an experimental satellite in four or five years, said Masahide Sasaki, director of the National institute of Information and Communications Technology in Tokyo.

The U.S. has seemed strangely absent from the quantum communications discussion, researchers agreed.

He forgot to mention that the US already spent millions of dollars on a boondoggle quantum network. It was built by the defense contractor Raytheon-BNN in Boston. (Ref) Maybe the US realized, after they had built it, that there was no use for it.

The most common use of the word “bustle” is to describe a situation full of activity, as in the sentence “the small harbor bustled with boats”. However, the word is also the name of a kind of frame worn under a skirt to make it puff out conspicuously in the derrière. Bustles were commonly used during the Victorian era (the period of Queen Victoria’s reign, 1837-1901). Victorians were big fans of good science and technology (Charles Darwin, Sherlock Holmes…). But they also patented the bustle. I find Victorian bustles decidedly ugly and unsexy. Especially so when compared with other historic female fashions, like, for instance, my favorite, flapper outfits from the roaring twenties (think naughty girls, jazz, swing dance, speakeasies, art deco, slang such as “bee’s knees”).

Quantum cryptography, a flourishing fashion in the quantum information field, reminds me of the Victorian bustle skirt. The public is clamoring for sexy quantum computers (the equivalent of flapper outfits), but instead, some governments are spending millions of dollars to subsidize research aimed at producing quantum crypto (the equivalent of bigger bustles).

The heads of 3 prestigious scientific institutes

  • Artur Ekert (director of Centre for Quantum Technologies in Singapore)

  • Raymond Laflamme (director of the Institute for Quantum Computing in Waterloo, Canada.)

  • Anton Zeilinger (head of his own team at University of Vienna in Austria)

(Each one has a personal Wikipedia page longer than the ones for Einstein and Feynman combined 🙂 )

have been recently putting out press releases ardently proclaiming the wondrous, game changing research that their institutes are conducting into making bigger quantum bustle skirts.

Meanwhile, almost at the same time, IBM has been reporting on their truly exciting advances in the hot topic of building superconducting QCs. IBM is the bee’s knees right now. It makes the 3 institutes mentioned above look as glamorous as the bustled Victorian lady in the following photo.


Institutes headed by Ekert, Laflamme, Zeilinger

I’ve spoken about quantum cryptography in previous blog posts. See, for example:

Post Quantum Crypto

A must read is Bruce Schneier’s opinion about quantum cryto.

Blog at WordPress.com.

%d bloggers like this: