# Quantum Bayesian Networks

## February 26, 2011

### Quoth the Raven: “No more Moore”

Filed under: Uncategorized — rrtucci @ 2:01 pm

Edgar Allan Poe’s poem “The Raven” describes a night when a black bird flew into the study of the man who is narrating. The raven answers all the narrator’s questions in the same way, by intoning the single word “Nevermore”, answering this way even his question about whether he will ever see his deceased love Leonore again, in the afterlife.

Moore’s Law describes the blistering pace of development that the semiconductor industry has followed, as a self-imposed discipline more than as a law of nature, for more than 50 years. It’s an exponential growth law. It says that you get 2 every 2. (i.e., the density of transistors in an integrated circuit increases by a factor of 2 every 2 years.)

Will we ever see our love LawMoore again, or are we destined to see her nevermoore?

Intel, a.k.a. chipzilla, sets the pace in the semiconductor industry. Their Sandy Bridge 32nm (nanometer) node-length chips are already available in the market, and their Ivy Bridge 22nm node-length chips are scheduled to arrive before the end of this year.

Intel has announced that it is ready to start construction this year of a \$5 billion fab in Arizona that will manufacture 14 nm node-length chips. The fab is expected to go on line by 2013.

The 14nm node-length chips will be followed by 11nm node-length ones, which, if current trends hold, will arrive to market by approx. 2015.

The future beyond 11nm is hard to predict. Even the 11nm node-length chips are iffy at this point in time. That’s because the distance between atoms in an unstrained silicon crystal is about 0.5nm. A transistor with 11nm node-length will have a gate-length of about 6nm (about 12 Si atoms). Theoretical calculations predict that transistors with such tiny gate lengths will suffer from significant amounts of quantum tunneling. As a result, going below 11nm will require a paradigm shift: exploiting optical transistors or spin-electronics, or some other very new techniques and phenomena. No doubt, any of these new techniques will involve a large dose of quantum mechanics.

Quantum Mechanics is a Borg, and its message to chip manufacturers is: “Resistance is futile, you will be assimilated. And if you are going to do quantum mechanics, you might as well also consider quantum computation, which can solve some problems much faster (with a more favorable time complexity) than classical computation.”

## February 19, 2011

### I For One Welcome Our New Probabilistic Computer Overlords

Filed under: Uncategorized — rrtucci @ 4:44 pm

On TV broadcasts aired on Feb. 14, 15 and 16 of 2011, IBM’s Watson computer played the trivia game of Jeopardy with the all-time best human players, Ken Jennings and Brad Rutter, beating them by a wide margin.

In his final answer, Ken Jennings wrote “I for one welcome our new computer overlords”

Jeopardy-relevant trivia about the origins of this phrase:

(My source and more information here): Operation Overlord was the code-name given to the Battle of Normandy, June 1944, the World War II battle on the west coast of France that launched the Allied Force invasion of German occupied Western Europe.

Arthur C. Clark’s 1953 sci fi novel “Childhood’s End” revolves around an alien race known as the Overlords that takes over the human race.

The 1977 film adaptation of the H.G. Wells short story “Empire of the Ants” uses the phrase “I, for one, welcome our new insect overlords”.

In the 1994 episode of The Simpsons titled, “Deep Space Homer”, news announcer Kent Brockman believes that the Earth is being invaded by giant space ants. He says “One thing is for certain: there is no stopping them; the ants will soon be here. And I for one welcome our new insect overlords. I’d like to remind them that as a trusted TV personality, I can be helpful in rounding up others to toil in their underground sugar caves.”

Much has been said and will be said in the future about the Feb. 14-16 Jeopardy event. Everyone interprets the event slightly differently, depending on their own experiences, interests, and world view.

To me, it was a spectacular, dramatic, breath-taking, amazing, awesome event. A humbling moment for carbon based life-forms. A great technological and scientific achievement in fast natural language processing. A grand synthesis of prior computer hardware and software inventions. A giant publicity coup for IBM.

(1)Querying a computer in natural language à la Star Trek
(2)Having that computer hypothesize multiple answers to that query, and then cross-check those answers and rate its confidence on them, basing those answers, not on a laboriously curated data base, but on an unstructured data base that is written in messy natural language.
Watson has jumped well over these two major AI hurdles with great panache (displaying super-human response times and success rates, performing high up in the “winner’s cloud”).

I see Watson as a powerful vindication of the idea of using probabilistic techniques for AI (Artificial Intelligence) and machine learning. Since I’m so interested in quantum computing, I can’t help pondering about the connections and implications of Watson for quantum computing. The main connection I see is that quantum computers are probabilistic computers too. In fact, QCs are ideally suited for doing quantum mechanics, and quantum mechanics can be viewed as a souped up version of classical probability theory. In my work, I use QCs to do Bayesian networks and Gibbs sampling, two of the most important techniques of probability theory and AI.

I hear the “Raiders of the Lost Ark”, Indiana Jones theme music play in my head every time I think of Watson’s intrepid programmers. I see Watson’s amazing software as a reminder that computers are useless without good software. It seems to me that currently, in the quantum computing field, software development is not being stressed enough.

I see Watson as an inspiration for people, corporations, and nations to do more science (including Quantum Computing Science):

• For people: This event is sure to inspire countless young people to pursue scientific careers, or at least to learn more science.

• For corporations: This event may encourage more corporate investment in scientific R&D. The event is a tremendous boost to IBM’s reputation. IBM suddenly doesn’t look so old-fashioned, dowdy, and out-of-touch anymore. Google, Microsoft and Autonomy must be green with envy at this technological and publicity coup in AI by IBM. They are sure to redouble their own, already considerable efforts in the AI field, so as not to be left behind by IBM. Shouldn’t the all mighty Google, king of answering questions, have done this first?

• For nations: This event sends a clear message to everyone in the world that American science and technology, in particular its computer science and technology, is still among the strongest in the world. America’s reputation is greatly enhanced by this. Other nations will try to emulate us (and also compete against us) in this arena. Such competition should be welcomed, since it will result in significant advancements in science, something that ultimately benefits us all.

• How significant is this event in the history of AI ?

• How does Watson work? Describe in detail Watson’s software and algorithms (i.e., the magic behind the curtain).

• What would be a good incremental next step for Watson and AI? An obvious one is integrating Watson with already existing and quite robust speech recognition technology. Another one is porting Watson technology to non-English languages (grunt work, but consider how useful it would be and how many good jobs would be generated in the writing and utilization of such ports).

• How soon before this technology shows up in commercial products?

• How soon before amateur computer programmers (hackers) can look at and tinker with the Watson code, or another computer code with similar capabilities? According to Wikipedia, “Watson was written in both Java and C++[12] and uses IBM’s DeepQA software and SUSE Linux Enterprise Server 11.”

• Will a supercomputer be necessary for running future versions of Watson? According to Eric Brown, one of the research managers of the Watson project, the first version of Watson ran on a Blue Gene/P, IBM’s biggest supercomputer, but this turned out to be way too slow and was replaced by the current POWER7 cluster architecture, which uses fewer cores than a Blue Gene/P, but those cores run 4 times faster. (Blue Gene/P has 4,096 cores that run at 850 MHz, whereas Watson uses a POWER7 cluster with 2,880 cores that run at 3.55 GHz).

It’s also quite telling that while the computer program Deep Blue that beat Gary Kasparov in 1997 required a specialized supercomputer to run, nowadays one can purchase computer programs like Rybka, Deep Fritz or Deep Junior which can consistently beat Deep Blue and require only a single personal computer to run. These newer programs use much smarter, more efficient algorithms than Deep Blue.

Some References

1. Smarter than you think. What Is I.B.M.’s Watson? By Clive Thompson (New York Times, June 16, 2010)

2. How Watson works: a conversation with Eric Brown, IBM Research Manager, by Amara D. Angelica (January 31, 2011)
3. Wikipedia article Watson_(artificial_intelligence_software)

## February 7, 2011

### “A Landmark Proof” for Anyons, According to Wilczek

Filed under: Uncategorized — rrtucci @ 5:48 pm

MIT professor Frank Wilczek is primarily a high energy physicist (he won, together with D.Gross and H.D. Politzer, the 2004 Nobel Prize in Physics, for discovering a high energy physics phenomenon, viz. the asymptotic freedom of the strong force). However, Wilczek is also interested in anyons.

Many scientists believe that non-abelian anyons would make good qubits because they would be inherently insensitive to external decohering noise. Anyons are described by topological quantum field theories. Michael Freedman’s group Station Q at UCSB specializes in topological (anyonic) quantum computing. John Preskill’s Course 219 has a nice introduction to the subject of topological quantum computing.

Check out:

A landmark proof
by Frank Wilczek (Physics 4, 10 (2011), February 7, 2011)

In this lucid, introductory, viewpoint article, Wilczek explains anyons, and he trumpets a recent paper by Parsa Bonderson, Victor Gurarie, and Chetan Nayak which “proves” something that had been hypothesized for a long time, but had eluded proof until now, that systems exhibiting the fractional quantum Hall effect can be used to produce non-abelian anyons. The “proof” is a physicist’s proof, and, as such, contains a lot of new computational methods that are bound to help scientists calculate things about such systems that nobody knew how to calculate before. The last sentence of Wilczek’s article is:

Now we eagerly await the next great step: experimental confirmation.

My main specialty in the QC field is quantum computer programming. I try to write QC programs in a platform-independent way; i.e, a way that is independent of which particular qubit realization eventually wins the grand race for a scalable QC. Whether that be anyons or any of the many other realizations currently being tried. Nevertheless, I am always excited to learn about theory and experiments for any particular realization, such as anyons.

I hope trumpeting the connection between quantum computing and topological quantum field theories will help to attract high energy and solid state physicists into the QC field.

## February 3, 2011

### One Channel Capacity to Rule Them ALL

Filed under: Uncategorized — rrtucci @ 8:35 pm

One Ring to rule them all, One Ring to find them, One Ring to bring them all and in the darkness bind them, In the Land of Mordor where the Shadows lie.

In 2 previous blog posts, I spoke about classical and quantum SIT (Shannon Information Theory). Let me now say a few words about one of the main and most interesting constructs of SIT, the channel capacity.

In SIT, one considers a situation where Alice sends messages to Bob through a “channel”. Alice is allowed to perform some processing, called encoding, of the message before sending it. Bob is allowed to do some processing of his own, called decoding, to undo, as much as possible, the encoding done by Alice. The goal is for Bob to be able to get Alice’s message with zero error, despite the fact that the intervening channel is “noisy”.

The CC (channel capacity) is defined as the maximum number of bits per channel use that can be sent by Alice to Bob with zero error. CC is like a maximum possible efficiency: If each channel use transmits one bit, then CC is the ratio of input bits to output bits (where the input is to the encoder and the output is from the encoder to the channel). CC is an “optimal” efficiency: all efficiencies less than CC are “achievable”, and none greater than CC are achievable (with zero error). (Communication theorists like to use the word “rate” instead of “efficiency”).

A CC is subject to the constraints imposed by the physical theory being considered. (This reminds me of special relativity, a theory which can be deduced in its entirety from the simple constraint that messages cannot travel through a channel at a speed greater than the speed of light.)

There are various types of CC, depending on what constraints are imposed on the resources available to Alice and Bob, and on the channel connecting them. In quantum mechanics, the resources and channel are constrained to obey the laws of quantum mechanics. Since quantum mechanics subsumes classical mechanics but is far richer, there are more types of CC in quantum SIT than in classical SIT.

Let $n$ and $k$ be integers. Let ${\cal N}$ and ${\cal M}$ represent channels. Let ${\cal N}^{\otimes n}$ be a channel consisting of $n$ parallel uses of channel ${\cal N}$. Let $CC({\cal N})$ be a generic channel capacity for channel ${\cal N}$. In general, there exists a function $f({\cal N})$ such that

$Eq.(1) \;\;\;\;\;\;\; CC({\cal N}) = \lim_{n\rightarrow \infty}\frac{1}{n}f({\cal N}^{\otimes n})$.

One Letter Formula for CC. For some CCs, the limit of Eq.(1) can be shown to equal an easily computable “one letter formula”. For instance, the main CC used in classical SIT can be shown to equal the mutual information $I(X:Y)$, a quantity that does not involve any limits over $n$.

Additivity of CC. In general, any function $f({\cal N})$ (or $CC({\cal N})$) is said to be additive if for any two channels ${\cal N}$ and ${\cal M}$, even if ${\cal N} \neq {\cal M}$,

$f({\cal N} \otimes {\cal M} )= f({\cal N}) + f({\cal M})$.

From Eq.(1), one gets

$CC({\cal N}^{\otimes k}) = k \lim_{n\rightarrow \infty}\frac{1}{nk}f({\cal N}^{\otimes nk})=kCC({\cal N})$.

So any CC satisfies

$CC({\cal N}^{\otimes k})=kCC({\cal N})$.

However, this does not imply that all CCs are additive; there could still exist unequal channels ${\cal N}$ and ${\cal M}$ such that $CC({\cal N} \otimes {\cal M} )\neq CC({\cal N}) + CC({\cal M})$.

$I(X:Y)$, the main CC used in classical SIT, is additive. The capacity of water channels (e.g., pipes) is also additive.

The Quest to Find the One Channel Capacity to Rule then All. A very interesting feature of quantum SIT is that, for most of the quantum CCs that researchers have proposed so far, a one letter formula is not known, and they are non-additive. For instance, consider the CC for transmitting quantum messages, usually denoted by $Q({\cal N})$. A one letter formula for $Q({\cal N})$ is not known. Furthermore, it is possible to define channels ${\cal N}$ and ${\cal M}$ such that $Q({\cal N})=Q({\cal M})=0$ and yet $Q({\cal N}\otimes {\cal M})\neq 0$.

Scientists are beginning to question whether their current definitions of quantum CCs are too narrow. It would be nice to find a ring to rule them all, a definition of a quantum CC such that:

• it reduces in special cases to the classical CC (i.e., $I(X:Y)$) and to some of the previously considered, more narrow definitions of quantum CCs

• we know a one letter formula for it

• if it’s non-additive, we know the precise reasons for this, and how to control its non-additivity.

Carlo Bennetto, the Gandalf of quantum information theory, and his hobbits at the IBM shire, have been trying for centuries to find the one ring, sometimes coming within a hair’s breadth of it. Graeme Smith recently published a short (just 5 pages), superb review paper on the current status of quantum channel capacities.

I wish I could have written this story in the beautiful language used in both the novel and movies “The Lord of the Rings”, a language that mesmerizes with its archaic sounding vocabulary, syntax, rhythm and rhyme. But I leave that task to storytellers more skillful than I am, for I must embark immediately upon the quest to find the one ring to rule them all.

• wikipedia on Lord of the Rings(books) here

• wikipedia on Lord of the Rings(films) here

• wikiquote on Lord of the Rings(books) here

• wikiquote on Lord of the Rings(films) here

Blog at WordPress.com.