<\/p>\n
Codes, Geometry and Random Structures<\/a><\/strong><\/p>\n Graeme Smith, Detecting incapacity<\/a>, based on 1108.1807<\/a><\/i><\/p>\n A central question in quantum information theory is determining when a channel has nonzero quantum capacity. Pretty much all we know here is that there are a few criteria for proving a channel has zero<\/i> quantum capacity: PPT channels can’t transmit entanglement (since LOCC can’t change PPT states to non-PPT states) nor can anti-degradable channels (because of no-cloning). These two arguments appear to both be pretty specific. Can we put them on the same footing, and hopefully also derive some new criteria? Jean-Pierre Tillich, Quantum turbo codes with unbounded minimum distance and excellent error-reducing performance<\/a><\/i><\/p>\n LDPC codes are successful classically, but quantumly they suffer many drawbacks: their distance isn’t so good (but see 0903.0566<\/a>), their Tanner graphs have short cycles (specifically 4-cycles), and iterative decoding doesn’t work. One particular no-go theorem is that there are no convolutional encoder that is both recursive and non-catastrophic (0712.2888<\/a>). Jurg Wullschleger, The decoupling theorem<\/a><\/i><\/p>\n The decoupling theorem is arguably the Book proof<\/a> of most quantum coding theorems. The encoder applies a random unitary (in some problem-dependent way) and transmits part of the output to the receiver. Treat this part as being traced out, and if she keeps part, then consider it to be controlled by Eve. If the resulting state has the reference system “decoupled” from Eve, then since the remaining parts of the state (controlled by Bob) purify everything, then a local unitary on Bob’s side can give him pure entangled states with both the reference, and separately with Eve. This allows the complicated task of transmitting quantum information reliably (which is hard enough that proving that the coherent information was the quantum capacity originally took a lot of difficult technical work) can be reduced to the simpler goal of destroying<\/i> correlations. Fr\u00e9d\u00e9ric Dupuis , Classical coding via decoupling<\/a><\/i><\/p>\n Decoupling is great for sending quantum messages, and gives simpler proofs than even the original HSW proof of the classical capacity (or any other known proofs). Thus it’s interesting to find a decoupling-based proof of the HSW theorem not only for the sake of the unification of knowledge, but also so we can get a simpler proof. This is essentially what is achieved here, although only when the inputs are uniformly distributed.<\/p>\n Mark Wilde, Polar codes for classical, private, and quantum communication<\/a><\/i><\/p>\n We are really good at dealing with correlated information, with tools like Slepian-Wolf, side-information-assisted hypothesis testing and multiple-access channel codes. So we can treat inputs to channels in this way. We can perform simple $latex mathbb{F}_2$-linear maps on the inputs so that we can manipulate n binary channels each with capacity C become roughly nC channels with capacity roughly 1, and n(1-C) channels roughly with capacity 0. $latex 1 – {rm tr} Pi_N cdots Pi_1 rho Pi_1 cdots Pi_N leq 2 sqrt{sum_{i=1}^N {rm tr} (I-Pi_i)rho}$ .<\/p><\/blockquote>\n Mark calls this a “noncommutative union bound.” Note that using a Winter-style “gentle measurement lemma” puts the square root inside the sum, which for this application cuts the achievable rate in half. A big open question is to make the decoding efficient, and to figure out which channels are good.<\/p>\n
\nThat’s what this paper does. The talk was good, but the paper also describes the results clearly.
\nHere is a sample of the results.
\nAssume that R is unphysical on set S; e.g. S is the set of quantum states and R is the transpose map. Suppose that for any physical map D, there exists a physical map D^* with $latex Rcirc D = D^* circ R$. If R is the partial transpose then $latex D^*$ is simply the operation you get from taking the complex conjugate of all the Kraus operators.
\nTheir theorem then states that if $latex Rcirc N$ is physical, N cannot transmit the states in S. The proof is a simple exercise in composition.
\nIn this case we say that N “physicalizes” R<\/i> or, equivalently, R “incapacitates” N<\/i>.
\nThis is not quite enough to get the no-cloning criterion, but a mild generalization will do the job. Graeme gave a nice explanation in terms of how teleporting information involves going backwards in time through the EPR pairs, and if PPT states are used, then the time-traveling information gets confused and doesn’t know whether to get forwards or backwards. However, if this principle is implicit in the proof, then it’s very<\/i> implicit.<\/p>\n
\nIn this talk, Tillich discusses a catastrophic and recursive encoder. It achieves rate 1\/8 and somewhat surprisingly, it achieves minimum distance of $latex Omega(log(n) \/ loglog(n))$ with high probability. He conjectures that this should be $latex Omega(log n)$ for the right choice of interleaver.
\nThe resulting code can be thought of not so much as “error-correcting” but “error-reducing.” Error rate p=0.14 becomes 10-3<\/sup>, and p=0.105 becomes 10-4<\/sup>. This compares favorably with the toric code threshold of p=0.15. He suspects that the limitation here comes from the iterative decoder.<\/p>\n
\nDecoupling theorems were originally developed for the state-merging problem, by Horodecki-Oppenheim-Winter ’05 (where it was “Lemma 5” or something similarly marginal). Then it was further developed by quant-ph\/0606225<\/a>, where it was called a Theorem. Then in <\/a>, it moved to the title. So it took some time for the community to fully appreciate how useful this tool is.
\nSome of these tools use smoothed min- and max-entropies, which can be thought of as one-shot variants of von Neumann entropy that are either pessimistic or optimistic, depending on application. Amusingly, the smoothed max-entropy is not defined by taking a smoothed rank, but is defined in order to satisfy a relation that we’d like (which also holds for pure states). This is reminiscent of the speed of light, which is an integer number of meters\/second by definition.
\nFor any pure state $latex rho^{XYE}$, define the smoothed max entropy to be
\n$latex H_{max}^epsilon(X|Y))_rho = – H_{min}^epsilon H(X|E)_rho$.
\nOther definitions are also used, but are pretty close.
\nIn this talk, Jurg described a converse theorem to the decoupling theorem, and explained many scenarios in which it applies. See his paper<\/a> for the details.<\/p>\n
\nQuantumly, much of this goes through, but we need the ability to simultaneously apply typical projections. This key lemma is Lemma 3 in Pranab Sen’s paper arXiv:1109.0802<\/a>.<\/p>\n
\nFor private communication, we can polarize into channels of four types: either good for Bob and good for Eve, bad for both, or good for one and bad for the other. We send random bits into the channels that are good for both, and arbitrary bits into the ones that are bad for both. Information bits go into the ones that are good for Bob and bad for Eve, and shared secret key goes into the ones that are bad for Bob (so he effectively gets the message anyway), and good for Eve.
\nThis generalizes to quantum communication using Devetak’s technique from quant-ph\/0304127<\/a>. Channel inputs are<\/p>\n\n
\n Bob<\/p>\n Eve<\/p>\n input<\/p>\n \n Good<\/p>\n Good<\/p>\n $latex |+rangle$<\/p>\n \n Good<\/p>\n Bad<\/p>\n information<\/p>\n \n Bad<\/p>\n Good<\/p>\n shared entanglement<\/p>\n \n Bad<\/p>\n Bad<\/p>\n arbitrary
\n<\/table>\n