Holevo Additivity Falls? The Quantum Universe Gets Even Stranger

Major news from the quantum information front. Today I see posted on the arXiv a paper by M.B. Hastings: arXiv:0809.3972 "A Counterexample to Additivity of Minimum Output Entropy." If correct this resolves one of the most famous open problems in quantum information theory, and, even more interestingly says that in a quantum world, transmitting classical information down quantum channel defies your classical intuition. Blessed be our quantum world, which just continues and continues to amaze.

Previously I explained the idea channel capacity. You're sending (classical) information from one party to another and this information gets distorted while it being transmitted down a channel. If the channel acts noisily then you can't send information perfectly. But by encoding the information suitably you can, with exponentially vanishing probability of failure, robustly transmit this information at the expense of using more bits for every bit you want to send. The capacity of a channel is the maximum value of the ratio of encoded to raw bits which allow you to reliably transmit information.

Now suppose you have two channels. One of them has a channel capacity of r₁ and the other has a channel capacity of r₂. Now suppose that you transmit messages down both of these channels at the same time. What is the capacity of the channel? A classic (err...bad pun) result of information theory is that the capacity of the channels is additive: that is the capacity of using both in parallel is r₁+r₂.

Given that we live in a world which obeys quantum theory, one of the first parts of information science to arise was to study how you can transmit information down a system which obeys quantum theory. Thus you could study how much classical information you could send down a quantum channel or you could study how much quantum information you could send down a quantum channel. Recently a major breakthrough was achieved by Yard and Smith who showed that if you are transmitting quantum information down a quantum channel, the quantum channel capacity is not additive. The did this by showing that there are two zero capacity quantum channels which, when used together, can be used to transmit quantum information with non-zero capacity (see my "old" blog post.) This is an amazing result and settles a very important basic quantum information theory (and gives a surprising answer, in my opinion.)

So what does the new paper do? It talks about the additive question for the question of the classical information capacity of a quantum channel. In particular suppose that you are trying to transmit classical information (bits) but you send then using a quantum channel. The maximum rate at which you can transmit classical information using quantum information systems is known as the Holevo capacity of the channel. (Note that if you are dealing with a noiseless channel, the the Holevo capacity is unity. This means that if you can't transmit five bits, by using one qubit. To transmit a n classical bits you need n quantum bits.)

So a natural question to ask is whether the Holevo capacity of a quantum channel is additive. That is, if you are transmitting classical information down a quantum channel, do the Holevo capacities simply add? In some sense what you are asking is: does the additivity of classical information really hold in our universe (since our universe seems to obey the laws of quantum theory.) What the paper I referenced above claims to show is that the Holevo capacities are not additive. I haven't gone through the paper yet, but if this holds up, this is a major result. And it says something totally amazing about quantum information theory: that transmitting classical information in a quantum world does not end up with the answer that Shannon came up with, and which is the conforming additive answer.

(Update 9/26: Read the comment by Jon Yard below. If I understand Jon correctly, what Matt has shown is that the maximum Holevo information when thinking about single instances of the channel is not additive. This is different from saying that the classical capacity of a quantum channel is not additive, since to really define this operationally one must talk about a regularized version of the capacity in which multiple uses of the channel are allowed.)

Forget two new large prime numbers being discovered within a few weeks: the two major additivity questions of quantum information seem to have fallen within months of each other. Exciting times these!