# Quantum Error Correction

One can correct the errors in a quantum channel iff the coherent information of the input state is not reduced by the channel. This is analogous to sending quantum entanglement through a channel. If the loss of coherent information by the channel is $< \varepsilon$, can one still correct errors? Can one restore the loss of information to provide for perfect correction?

-
It is in principle a perfectly rigorous question that can be taken as mathematics. In detail, however, I have no idea what the question is. –  Greg Kuperberg Oct 12 '10 at 20:44
It is not at all clear. According to your very first sentence, if the coherent information is reduced by the channel, then you cannot correct errors. Then you ask "If the loss of coherent information is reduced by at most $\varepsilon$, can one still correct errors?". –  Eric Tressler Oct 12 '10 at 20:54
I think I see the source of some confusion. One can correct quantum information perfectly if one can provide an input state (possibly entangled over several channel uses) so that the coherent information is not reduced by the channel. Most channels aren't so good to provide perfect error correction, but many will let you reduce the loss of coherent information to an arbitrarily small amount by encoding the input in an entangled state over many channel uses. This should be explained in papers about the quantum capacity of a quantum channel. –  Peter Shor Oct 13 '10 at 3:11
And I'm not at all sure that cstheory.stackexchange.com would do any better for answers than this site. CS theory isn't generally considered to include information theory (probably mainly for historical reasons), and most people working on quantum channel capacity are either physicists or information theorists. –  Peter Shor Oct 13 '10 at 3:17
A new theoretical physics SE site should be launched pretty soon area51.stackexchange.com/proposals/23848/theoretical-physics and will be more suited than MO for specific quantum information questions. –  Anthony Leverrier Nov 23 '10 at 23:38

The quantum channel capacity is the asymptotic amount of quantum information that can be carried by a quantum channel. There is a formula for it: it is given by the maximization of the regularization of the coherent information, as discussed in this paper by Graeme Smith which is a recent, short survey article. No single-letter formula (the Holy Grail of information theorists) is known.

If there is a density matrix on the input space of a channel for which the coherent information is positive, then there is an asymptotic sequence of quantum codes whose rate approaches this coherent information. Because coherent information is not additive, you can sometimes (although explicit examples are quite rare) improve the rate by using input states on the tensor product of $n$ copies of the channel.

Unlike classical information, which can be carried by any channel whose output is not independent of the input, there are some channels (such as classical channels) which are too noisy to carry quantum information. For these, for any input density matrix, the coherent information formula is always non-positive.

As for the OP's question, as best as I can interpret it, if the channel is not too noisy to carry quantum information, then for any $\epsilon$ there are codes (with block length going to $\infty$) for which the output quantum state is within $\epsilon$ of the input quantum state, although you cannot generally ensure perfect transmission of the input quantum state. Otherwise, the channel cannot be used to establish near-pure-state entanglement between the sender and the receiver, which means that any quantum information sent through the channel will always be degraded by some fixed amount.

-

The question as you have it formulated currently has "no" for an answer. If the loss of coherent information means you cannot correct the errors, then obviously the loss of coherent information means you cannot correct any errors.

In non-quantum coding, it is possible to generate error correcting codes that are capable of correcting $a$-bit errors per $n$ bits (obviously, $a \lt n$), and of detecting $b$-bit errors per $n$ bits, ($a \lt b \lt n$), while greater than $b$ erroneous bits would be a catastrophic undetectable and uncorrectable error. These error-correcting codes depend on sending redundant information, decreasing the information content or the information content below the maximal Shannon information density possible on that communication stream. There is no way around having to reduce information density to increase the quality of the transmission.

Hamming codes allow for 1-bit error correction, 2-bit detection; Reed-Solomon codes are used to perform error correction on audio compact-discs. While your comment says you "meant not PERFECT error correction", your question still says "to provide for perfect error correction". Perhaps you could edit your question to provide more rigorous mathematical definitions and ask explicitly exactly what you mean.

-
And more or less the same thing happens in quantum error correcting codes. –  Peter Shor Oct 13 '10 at 3:18
@Peter Shor, thanks for the confirmation that I'm understanding this concept clearly. –  sleepless in beantown Oct 13 '10 at 3:23
Not all quantum channels have positive quantum capacity. Some channels (entanglement breaking channels) are not completely noisy, but noisy enough that if you input half of an entangled state, no entanglement comes out. These cannot transmit quantum information. Other channels are too noisy to transmit pure-state entanglement, but still can transmit some kinds of quantum entanglement. Finally, some channels have positive quantum capacity. If you transmit at a rate slower than the capacity, with large enough block length you can find codes that transmit quantum states arbitrarily well. –  Peter Shor Oct 13 '10 at 3:50
@Peter Shor, thanks again for the clarification. Could you perhaps point me to a good review article or book to look at the details of this? Is the quantum channel capacity a function of the medium, or perhaps of the encoding scheme? (once again, apologies if this is an embarassingly naive question; I am conversant with information theory, though not as well informed about quantum computation and information processing) –  sleepless in beantown Oct 13 '10 at 3:55
There's a quantum capacity formula (like the Shannon capacity) which is unfortunately not single-symbol. My conjecture is that for most simple channels whose capacity is not near 0, the quantum capacity is actually given by the single-symbol version of the formula. A good reference on quantum information theory may be John Preskill's lecture notes, especially chapter 5 (but they don't cover quantum error correcting codes or the quantum capacity of a quantum channel; just the classical capacity of a quantum channel). –  Peter Shor Oct 13 '10 at 4:08