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 r1 and the other has a channel capacity of r2. 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 r1+r2.
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!
O brave new quantum world!
In a weird coincidence, Jon Yard gave a talk at Perimeter today, and this new result was thrown in. Really interesting results! Quantum informations seems to be more couter-intuitive than I would ever have thought.
Jon’s talk: http://pirsa.org/08090021/
Hi Dave,
I should mention that what Graeme and I showed is somewhat different from Matt’s result. Graeme and I showed that the operationally defined quantum capacity is not additive in the worst possible way – two zero capacity channels can have a nonzero capacity together. Matt’s result implies that a conjectured formula (the maximum Holevo – or mutual – information over a single instance of the channel) for the classical capacity cannot be the right formula. A similar result was found by Shor and Smolin back in 1996 in regards to the quantum capacity. They showed that the maximum of the coherent information is not generally additive, which implies that the quantum capacity is not generally given by the maximization of the coherent information over a single instance of the channel. Shor/Smolin had a bit of an easier time with this because they used a depolarizing channel which was noisy enough to give coherent information = 0. With mutual information this could not work because if the maximum mutual information over a channel is zero, it displays *no* correlations between its input and output. This remains so if you get to use the channel many times. So, a problem that is still open is whether or not the classical capacity itself (given by the regularized maximization of mutual information) is additive. Again, it is impossible to show that 0 + 0 > 0 as we did for the quantum capacity, so who knows how it could be proved/disproved?