Quantum Bayesian Networks

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