Polar codes for classical, private, and quantum communication
Wilde, Mark
Channel polarization is a phenomenon in which a particular recursive encoding induces a set of synthesized channels from many instances of a memoryless channel, such that a fraction of the synthesized channels become near perfect for data transmission and the other fraction become near useless for this task. The channel polarization effect then leads to a simple scheme for data transmission: send the information bits through the perfect channels and "frozen" bits through the useless ones. One contribution of the present work is to leverage several known results from the quantum information literature to demonstrate that the channel polarization effect takes hold for channels with classical inputs and quantum outputs. We construct linear polar codes based on this effect, and we also demonstrate that a quantum successive cancellation decoder works well, by exploiting Sen's recent "non-commutative union bound" that holds for a sequence of projectors applied to a quantum state. In addition, consider that Mahdavifar and Vardy have recently exploited the channel polarization phenomenon to construct codes that achieve the symmetric private capacity for private data transmission over a degraded wiretap channel. We build on their work and demonstrate how to construct quantum wiretap polar codes that achieve the symmetric private capacity of a degraded quantum wiretap channel with a classical eavesdropper. Due to the Schumacher-Westmoreland correspondence between quantum privacy and quantum coherence, we can construct quantum polar codes by operating these quantum wiretap polar codes in superposition. Our scheme achieves the symmetric coherent information rate for quantum channels that are degradable with a classical environment. This condition on the environment may seem restrictive, but we show that many quantum channels satisfy this criterion, including amplitude damping channels, photon-detected jump channels, dephasing channels, erasure channels, and cloning channels. Our quantum polar coding scheme has the desirable properties of being channel-adapted and symmetric capacity-achieving.
 Okay. Okay, Mark Wilde, Policodes. Okay, so sorry about that. Thanks for having me at this conference. And in light of the panel discussion last night, I've opened the panelists won't start throwing tomatoes at me, but my talk is about codes for quantum communication, not necessarily fault tolerance. We're trying to find codes that can achieve the capacity of a quantum channel for communication. The fact that I'm so interested in this, you can partially blame on Todd Brunn. He never made me take a note to preserve, protect, and defend the quantum computer. So in the classical world, in the past, since about 2008, there's been some work on codes called polar codes, which have pretty remarkable properties. And we've been going to these information theory conferences for the past few years, and so we decided recently it would be a good idea to see how to make these codes work in the quantum domain. In parallel, Renato Renner and his group in Zurich turns out that Renato Renner lives in the same apartment complex as the chief editor of the IEEE Transactions on Information Theory, and they have these birthday parties for their kids, you know, these information theory people have birthday parties. And Renato Renner asked the chief editor what he thought the biggest advance in coding theory in the past 10 years was, and the chief editor said, well, without a doubt, it would be polar codes. So their group started pursuing it, and about the same time we had papers appear on the archive. So we did these, Saikaku and I did these two papers here, and recently one of the co-authors on that paper, Joe Renas, we put our heads together and we came up with polar codes that can achieve this exotic super activation effect that Grim Smith was talking about, where two zero capacity channels, you can put them together, have non-zero capacity, except this is a near-explicit code construction for doing that. Okay, so just a little motivation. From quantum Shannon Theory, quantum information theory, we have a pretty good idea of capacities of channels for sending classical data or private classical data or quantum data. Only for certain channels we have this idea, but there's still some open problems. And there's been a fair amount of work on quantum turbo codes by David Poulon and others in an attempt to achieve the capacity of a quantum channel, and also quantum LDPC codes. These are explicit constructions, but you can't actually put these codes or capacity achieving. And there's actually very little work on codes for sending classical or private data, even though this is an important problem where you can actually demonstrate a quantum supremacy, as was said last night, turns out for a bosonic channel, if you have your detector perform a joint collective quantum measurement, there can be a significant increase in the amount of classical data you can send over this channel when there's a low photon number. And so, as I was saying, these polar codes are promising in the classical world, and from what I hear, they're being incorporated into standards for communication, so we thought why not explore their quantum generalization. And the result we found is a scheme that's near explicit, there's still some work that needs to be done in this direction. We can prove that their capacity achieving for certain channels. Okay, so I'll start by describing this channel polarization phenomenon, and we'll do it for the quantum case. And in particular, I realize this is not a CEC conference, but I'm going to start out with the classical case to build up to the quantum case, and eventually I'll get to QEC in the talk. Okay, so we'll begin with a channel that is a classical quantum channel, a CQ channel, I'll call it W. It has a classical binary input X, and conditional on that some state rho X is prepared at the output, and it doesn't matter if we mention the state. So if you put in zero outcomes, rho zero, put in one outcomes, rho one. An important channel parameter is something I'll call the information of W. In more detail, we'll call it the symmetric Halevo information. And it's just the mutual information, the correlations you can establish between the input and the output when you select the input uniformly at random. Okay, so that's why it's called symmetric Halevo information. If you have formula, it'll work out to this. And I could evaluate this information quantity with respect to this classical quantum state, which corresponds to an ensemble I can prepare using this channel at the output. And just to give you some idea, this parameter is equal to one if the channel is perfect, and it's zero if the channel is totally useless. So the useless case is when the cable is cut, like when Graham Smith was saying in his talk. Okay, so this is an important channel parameter. And the inventor of polar codes is a professor named Ari Kahn, and his idea was to take two copies of this channel and just do a classical C knot, okay, at the input. And what you can observe is this information preservation condition, okay. So if I compute twice the information of the original channel, it'll be this quantity when you work it out. And this is an information evaluated with respect to these two inputs. And since this gate is reversible, the information here is equal to the information of these when these two inputs are input. But what we can use is something that's well known in information theory. It's the chain rule for mutual information to break this information term into two parts, okay. So it's very important for the polar coding idea, okay. And this chain rule, it's suggesting that we can actually think about two different channels. There's a channel from the bit U1 to the two outputs, and a different channel from the bit U2 to the two outputs with the bit U1 as side information, okay. So to give a picture of this, this first channel is a bit channel from U1 to the two outputs where this is acting as noise. It's not known to the receiver, okay. I'll call that W minus. Maybe think it'd be a worse channel than the other one where U1 is available as side information, right. So I'm just taking this, this channel here is a bit channel from U2 to these outputs, U1 and the two quantum outputs. And what's happening is that this U1 is available as side information, okay. So when you look at these pictures, maybe it's already hinting at how a decoder could work in decoding these bits, okay. And what we came up with is an extension of Arikhan's ideas. We call it a quantum successive cancellation decoder. Okay, that's a name that comes from information theory. But the idea is that the decoder would first decode U1, assuming this is noise, and the receiver would do this by doing a simple quantum hypothesis test, right. While on U1, there's some state that's prepared at the output. I could call it say, or signal 1. And the receiver would just do what's called a helstrum measurement, project onto the positive eigenspace of the difference of these two operators that are prepared at the outputs, okay. And then, assuming that the decoder corrected U1, that the decoder decoded U1 correctly, it's then available as side information to do a second quantum hypothesis test to determine U2, okay. So that's the idea behind the decoder. But what you do is you continue this construction recursively, okay. Because we're going to need many copies of the channel to make some interesting statements, okay. So what I'm doing here is I'm taking, I had this channel, this channel W2, right, this block here, and I take copies of it, and this recursive construction, right. So I'm placing them here and here. This operation, which it just places all of the odd indices, U1 and U3 first, it's putting them here, and it's taking the even indices and putting them next. So in this case, it just amounts to a swap of the middle two bits. And then I do a C knot on every pair of bits coming at the input, okay. So the idea is just a bunch of C knots, swap things around, C knots, swap things around, and it happens recursively and it builds it up, okay. And you can use the same idea of the chain rule, this information preserving condition, four times the original information of the channel using the chain rule will distribute in this way, such that I can think of four different channels now. The channel where the receiver is trying to get U1 first, conditional on that, getting U2 and so on and so forth. So a picture of that again, just to have that point home, the decoder is trying to get U1, these bits are random. Assuming it gets this correctly, he's U2, and these are random, so on and so forth it continues, right. So finally I have this picture here. Okay. So you continue this construction recursively many times, and the chain rule recursively will be this, just where you're trying to get the bit I, conditional on the previous I bits, or the previous I minus 1 bits. And this is the important statement of channel polarization, okay. So we're thinking about these induced channels from bit I to the channel outputs, right. And the statement of channel polarization is that a fraction of the channels will be completely perfect. Okay. So we can prove this, and the complementary fraction will be totally useless, okay. And the fraction of channels that are perfect is equal to the capacity of the original channel, and the fraction of channels that are imperfect, the complementary number, okay. So you can prove this result using martingale theory, that's what Arikhan did, and we used quantum generalizations of Arikhan's inequalities to prove this result, okay. So I'll go into that in a little detail to give you some idea of how it works. There's a different parameter we can think about that we'll call the fidelity of the two output states. Now keep in mind we're not considering quantum communication here, we're considering classical communication. So the interpretation of fidelity is a little different. We interpret it as a distinguished ability measure, okay. So how well can I distinguish row zero from row one? And quantumly we know it's this Hilbert Schmidt norm of these two states. And so the fidelity actually is zero if the states are orthogonal, if they're perfectly distinguishable by some measurement, and it's equal to one if the states are completely indistinguishable, okay. So since it's classical transmission it's a different interpretation, okay. And this generalizes the classical fidelity, which in the classical world they call it the Botticharia parameter, okay. And sort of an operational interpretation of this quantity, this is a parameter of the channel, the CQ channel. If I'm trying to do a quantum hypothesis test to distinguish the bits from each other, then the fidelity serves as an upper bound on this error probability. And we use this in the proof to show that the scheme works well, okay. So you would expect these parameters to be related, right. In particular, if the channel is good for sending classical data, you'd expect the states to be distinguishable, right. So if the information is one, if the channel is perfect, the states should be totally distinguishable. And if the information is zero, if the channel is useless, you'd expect the states to be completely indistinguishable, okay. And you can make this precise with these bounds here, right. So if the fidelity is zero, this term here will lower bound the information, which you can show as one. And if the fidelity is one, if the states are not distinguishable, then the information will be zero, okay. So we can prove these bounds using prior results of Halebo and some recent results of Rogga and others. Okay, and what's nice about this is you can prove things about fidelity, and that will imply similar things about the information quantity by these bounds, okay. So recall this recursive channel construction that we had before, we do this many times. And I'm going to call the channel induced from the ith bit, so say i is two, we'd be thinking about u2, and the nth recursion level, so here the recursion level is two. There's some bit channel there. And what you can show in this recursive construction is that the information of the ith bit there and the next iteration of the recursion will spread away from the middle, okay. So there will be two places in the circuit that will sort of spring forth from the ith bit channel. And what happens is they move away from the center in this construction, okay. So this is actually how the polarization effect takes hold. These information quantities are moving away from the middle of the interval between zero and one, and they're being pushed towards an extreme, towards zero or one, okay. So that's what this is showing, and a complementary sequence set of inequalities holds for the fidelity parameter, okay. And there's some other inequalities that you need to show this, but this is the basic idea, okay, and we can prove the generalizations of Arikhan's ideas. Okay, so then we're thinking of this splitting process, the way that the channels get created under this recursive encoding, and you can actually model the channel splitting process as a random birth process, okay. So I take the ith bit in the nth recursion level, and I represent it as a binary sequence, and this tells you where I'm going in this tree, right. So I model this as a random process, and what you can show is the fidelity of the ith channel where I is a random parameter, right, it's this binary sequence. This process is a martingale, and you can use a martingale convergence result, and the inequalities in the previous slides to show that this random variable will converge to a zero one valued random variable. So that's the polarization effect, okay. And what you can show is that the probability that this ith channel is zero, the fraction of channel is good, is equal to the capacity. So that's the basic idea that we were able to show in the quantum case. So once you have this, it immediately leads to your coding scheme, right, I mean it's pretty obvious from there. If you know which channels are the good ones, so this is sort of the existence part, right, we're using this probabilistic argument to say that this effect will take hold. So if you know which channels are the good ones, you send your information bits through those, and if you know the good ones, you'll know the bad ones, so you'll just send a pre-agreed upon values for the uncillibits through those other channels, okay. And then the decoder is just this quantum successive cancellation decoder, so you perform the sequence of conditional hypothesis tests to figure out your bitstream, okay. And the key tool that we use to analyze the error process show that the scheme is in fact capacity achieving is a recent bound of Pernab-Senn found in the context of quantum information theory. I call this bound the non-commutative union bound, I've said it at a different conference, I think this bound is really important and can be used in many different contexts. It generalizes the union bound from probability theory and this is used all the time in many probabilistic arguments. And so the reason this is like a union bound, is there a, let me actually go to the board, sorry here real quick, just to show how it generalizes the union bound. So the union bound from probability theory, just to remind you, if I'm interested in computing a correct, the probability for a correct sequence of events, I can think about, oh I'm thinking, I want the intersection of a correct sequence of events, right. So I can instead analyze the complement of that, that's what this first term here corresponds to, right. So when I do so I apply the Morgan's law, right, and I'll get the union of the complements of the events. So once in the union bound this is bounded by the sum of the complements of the individual events, right. So that's what this is doing, right, except with projectors. So the sequence of projectors corresponds to a correct sequence of events and one minus that is the complement and then it's upper bounded by the complement of each individual event, the complement of these projectors with the exception that there's a two square root in front and that comes from the non-communitivity. If the projectors commute you can remove the two square root and get the union bound. But if they don't, in general, you need this two square root, you can find counter examples where you can demonstrate that this is needed. Okay. So the idea is we can bound each of these events, the events for the individual channels by an exponentially decreasing term and there's a linear number of them so there's an exponential finding the linear term and the exponential always wins. So that's the basic idea behind proving the scheme that achieves the capacity. Proving that it achieves the classical capacity. So now I realize that this is not the PEC conference, the conference for private classical communications. This is the step that we need to finally get to the QEC. So we have, this is in relation to what David Kribs was talking about, relations between sending private data and sending that to the conference. So assume that we have a quantum wire tap channel, it's a classical wire tap channel, there's some classical binary input, it leads to a state of the output that's shared between Bob and Eve. So we can think about the channel to Bob just by tracing over Eve and we can think about the channel to Eve just by tracing over Bob. I'm going to call the channel to Bob W and we want to Eve W star and what's known is that if the channel is degradable, meaning that Bob can simulate Eve by applying some channel to his output. So in a sense, his output is not as noisy as Eve's, then you can prove that the private capacity is equal to this information difference. So the idea is just that the amount of private information you can send is just the difference between what Bob gets and what Eve gets. And so what happens in this setting, we have two different channels, right, and each polarize in their own way. There's going to be channels that are good for Bob and bad for Bob and ones that are good for Eve and bad for Eve. So overall, the channel will polarize in four different ways. There will be those that are good for Bob and good for Eve as well. And we don't want Eve to get any information, so we won't be sending information bits through those, but since they're good for Eve, we want to randomize what she's getting. So we send random bits through those. And this all is important because we're going to make coherent versions of this on the fourth one in slides. Ones that are good for Bob and bad for Eve, well, that's where we can put our private data because Eve won't be able to get the information there, but Bob will. And so we just send the information bits into those. And finally, well, not finally yet, but there are ones that are bad for Bob and good for Eve. And we can't guarantee that Bob will be able to decode the bits put in there, but Eve might be able to. So we need to randomize her. So we need something that Bob will have access to, so he can decode faithfully. We also need to randomize Eve. So the best thing we can put in there is halves of secret key bits. So don't start flinging tomatoes yet. We can show that the amount needed here, the consumption rate of secret key, goes to zero for certain channels. And then finally, there are channels that are bad for Bob and bad for Eve. And since Eve can't get those, we'll just put the unsold bits there that Bob knows, such that it can help them decode the information that's sent through. And what we can show is that the channel is degradable, such that the map to the environment is classical. So there's some density operator for Eve, row zero, row one. And if it's diagonal on some basis, this is what I call a channel that's degradable with classical environment. And we can show that the scheme provably achieves the wire tap capacity using this successive cancellation decoder. There are actually many channels that have this property, amplitude damping channels, defasing channels, cloning channels, the racer channels, et cetera. So this is a useful scheme. And what we can also show is that this rate of secret key required goes to zero, an asymptotic limit. Okay, so now finally, we're at the QEC slide. The basic idea is to run the wire tap code in superposition. These are ideas that were used by Dev Attack to prove that the coherent information is an achievable rate for quantum communication. And so what we're doing instead is using a coherent version of the same encoder. The encoder is just going to be C knot gates and swaps. And when you consider the channel, you know, they're probably saying any channel will have an extension to an environment as well as Bob's, so the overall channel is unitary. So this induces a wire tap channel. So then there will be channels that polarize in four different ways, just like we had for the wire tap phase. So there will be channels that are good for Bob and good for Eve. Remember from before, we put random bits into those to randomize Eve. Now we're just going to put the coherent version of a random bit, which is a plus state, into those channels. There are channels that are good for Bob and bad for Eve. We put information qubits into those. There were those channels that were bad for Bob and good for Eve, so remember they're bad for Bob, so we need something there that can help them decode. While we want to randomize Eve, we put a secret qubit there before. Here the version of a secret bit is an ebit, an entangled bit, bell state. But remember for certain channels, we can show that this entanglement consumption rate goes to zero. And then finally, there were these channels that are bad for Bob and bad for Eve. And since they're bad for Eve, we can put something that's agreed upon for Bob to help them decode and we put an encilic qubit there. So the decoder in this case is going to consist of two steps. Remember we had a measurement, this quantum successive cancellation decoder that worked well for getting the private information. So we're going to run a coherent version of that. Any measurement you can do sort of as a controlled operation. So we'll be doing that. And so that's the first step. And finally the second step is a controlled decoupling unitary. It's guaranteed by Oman's theorem. This part is not efficient. The first part is not either, but it's explicit. And there's a linear number of quantum hypothesis tests. For Pauly channels, Renner and others were able to show that it is efficient. So in analyzing the proof that this scheme achieves the capacity, we just use the fact that the decoding measurement is reliable and also that it's secure to guarantee that the quantum data can be decoded well. So the decoding circuit would look something like this. This is the encoder consisting of all these C-nauts and permutations and outcomes something for Bob and something for Eve. This part right here without this is just the measurement that was this quantum successive cancellation decoder. And then running it coherently, I'm taking the outcomes and putting them in these two registers coherently. And then finally this is the controlled decoupling unitary. So this was the first scheme that we have in this paper. Then recently, within the past two weeks, I've been working with Joe Renez and we can use some of his ideas from his scheme to come up with a slightly different scheme, but there are relations between the schemes. So Joe Renez has written all these papers about how sending quantum data is like sending classical information in complementary bases in like 10 papers in this topic. And so we're using this idea except in this explicit context where we have this polar code construction. So the way he thinks about quantum information I've had to learn recently is if we have a quantum channel, we can think about a classical quantum channel where we're sending some bit into the amplitude basis, which is just the eigenbasis of the V-operator. And then if we're able to decode that successfully coherently, we can think of the next channel in line as this phase encoded channel where a Bell state is available at the decoder. This comes about from the decoding process. It sort of creates these Bell states that have phase information encoded onto them. So this is this phase encoded channel. And his coding scheme is, well, channels that are good. The channels that are both good for amplitude and good for phase, there's a section which will be able to decode these channels because decoding quantum data is like decoding classical data well in complementary bases. And the channels that are good for amplitude but bad for phase will need some phase bits there to help Bob decode the phase channel because those are bad in this right here. And ones that are bad for both bases will need halves of e-bits there because in a sense, if you have an e-bit and Alice does a measurement locally from the Zeoggan basis, Bob will be able to predict the outcome of that measurement. And the same happens in the phase basis. If Alice does a phase measurement, if she does a measurement of the X-operator locally, then Bob will be able to predict the outcome of that measurement. And related to that is why we need e-bits here because these e-bits will help decode the channels that are bad for both bases. And then finally, there are channels that are bad for the amplitude basis but good for the phase basis and Bob will need information in the amplitude basis to help him decode these bad channels. So we really wanted this archive number here because it's really symmetrical and pretty. We're going to wait for a while to get this nice pretty number here. There's no two, two, two, two, two. So the way that this works, we have these amplitude channels, channels in the amplitude basis and we know from the polarization results that this number of channels will be good for the amplitude basis. And then from the phase results, the C system here is the half that's available to Bob for helping decoding the phase information so we know that this number will be good. And then what you can show is that the net rate, when you just consider the sizes of these sets and sort of some basic set theoretic operations and the sizes of sets, shows that the net rate of quantum communication will be the sum of these two minus one. And so we're subtracting off the e-bits that were used to communicate. And what you can show, what Joe has done in previous papers, all these papers he wrote, this rate will be equal to the coherent information. And so this is a picture I lifted from one of Joe's papers. This is how the decoder would work. First you're decoding the amplitude information and then coherently copying it to this Anciller register. And then this process is what induces that phase channel that I had in the previous slide where the bell state was available with phase information encoded onto it because you're getting a coherent copy of the amplitude information in this register. So then the phase measurement run coherently, acts on these two systems and copies it to this register. And finally doing a whole linear number of controlled phase gates, you can decouple the environment. This isn't dynamical decoupling, but this is a decoupling operation. And so using a linear number of those, you can decouple the environment and get the quantum data that Alice was trying to transmit to Bob. What's nice about this is that this is explicit, this is explicit, and this is explicit. This is a linear number of coherent quantum hypothesis tests run in succession. This is the same type of thing. So this work reduces the problem of the decoder for general channels to figure out how to make these two things efficient. And this is known to be efficient. So this is an improvement over the previous scheme that I had in the slide. Now what's sort of the cool statement we can make is that this scheme will achieve super activation for the channels that Graham Smith and John Yar gave in the examples, the channels that could exhibit this for me. So the two channels that they gave were this four dimensional input PPT channel, positive partial transpose channel, that has zero capacity. The other channel by Graham's no cloning theorem argument was an eraser channel and that has a 50% eraser channel and that has zero quantum capacity. But put together, these have non-zero capacity and the result is a 16 dimensional channel. So we can factor these 16 dimensions as a tensor product of four qubit input spaces and we can use this qubit polar coding scheme to achieve the coherent information. And the way this works is you coherently decode these amplitude and phase variables in this order. So first you decode the amplitude variable for the first qubit channel, and then using that aside information in this coherency decoder, you decode the second amplitude variable for the second channel in the four fold tensor product. You keep doing this. So after four rounds you'll get all the amplitude variables, then you can use those as side information coherently, quantum side information to decode the phase variables. This scheme will achieve the coherent information. One thing we can't show is for these channels how to make the entanglement consumption rate go to zero. Because before we needed this condition that the channels were degradable. But this doesn't hold for these examples. So one thing I should say why we consider this a super activation is if the quantum capacity is zero, then also the catalytic quantum capacity is zero. That's maybe not obvious. The catalytic quantum capacity is your entanglement to be consumed, but then the net rate of communication is how many qubits you can get out minus the entanglement consumption rate. So what you can show is that if the quantum capacity is zero, the catalytic quantum capacity is also zero. So that's why I consider this a super activation because we can super activate this catalytic quantum capacity. So that's all I have for now. The polar coding scheme is nice. What's known is the encoder, the decoder. The encoder is efficient. You can do it with O of N log N operations, sort of a butterfly like Fourier transform, FFT type operation. You can decompose it that way. The decoder is a linear number of quantum hypothesis tests. We're still working on that. There has been progress. Joe and Renato and Frederic Dupuis had this paper on the archives where they showed that the decoder can be made efficient if the channel is packed. Maybe this would be useful in addressing some of Daniel Goddison's questions from the previous talk. So this is the most important problem to make this decoder efficient for general channels. And then the other one, of course, is figuring out which channels are the good ones. This would make the scheme totally explosive. So there's been progress in the classical information theory community on this problem using approximation algorithms to compute which channels are the good ones. And then we may want to extend this to other scenarios like compression or lossy data compression, et cetera. Okay. Thank you very much. Questions? In the classical case to achieve good polarization, you need very long codes like 2 to the 20. Is this the case in quantum case as well, I guess? I would think so. That's another bad aspect of polarization. It's very long. In your scheme, you were using the e-bit or half of an e-bit when both channels were bad, but it didn't show up in your diagram. So where is the other half? That was just sort of supposed to be a figurative diagram. You could draw a different diagram. Sorry about that. But where are they? Are they still at the same? Well, they're shared between Alice and Bob beforehand. You're assuming you know the indices of the channels that are good or bad for amplitude and bad for phase. So the other half is already with Bob? It's already available for Bob. Yeah. That's needed to show it works. But there was some work in the classical world on these schemes for private communication over a classical wiretap channel. And when they evaluated in practice how many secret key bits were needed, they were able to show in some cases that they were not needed. Also for Joe Renes for Polly channels, they were able to show numerically that they were not needed for a certain Polly channel in the classical world. One last question. You describe the recursive construction of these induced channels. I was wondering, is it possible to say beforehand which one of these two to the n induced channels you're going to get for a fixed channel to begin with? Or you start with a fixed channel into the construction. Is it possible to say which ones are going to be the good ones? Which ones are going to be the bad ones? That's who we don't know. I believe if it's your channel, you can actually compute efficiently which ones will be the good ones and the bad ones. But in general, there was work, these approximation algorithms who addressed this question. Related question is how quickly the effect actually kicks in that relates to Alexei's question. Is it understood from the... It's understood. Well, I think it's fairly... It's understood that the block has to be long. Like he was saying, two to the 18 in practice. Let's thank Mark again.
 Okay.  Okay, Mark Wilde, Policodes.  Okay, so sorry about that.  Thanks for having me at this conference.  And in light of the panel discussion last night,  I've opened the panelists won't start throwing tomatoes at me, but my talk is about codes  for quantum communication, not necessarily fault tolerance.  We're trying to find codes that can achieve the capacity of a quantum channel for communication.  The fact that I'm so interested in this, you can partially blame on Todd Brunn.  He never made me take a note to preserve, protect, and defend the quantum computer.  So in the classical world, in the past, since about 2008, there's been some work on codes  called polar codes, which have pretty remarkable properties.  And we've been going to these information theory conferences for the past few years,  and so we decided recently it would be a good idea to see how to make these codes work in  the quantum domain.  In parallel, Renato Renner and his group in Zurich turns out that Renato Renner lives  in the same apartment complex as the chief editor of the IEEE Transactions on Information  Theory, and they have these birthday parties for their kids, you know, these information  theory people have birthday parties.  And Renato Renner asked the chief editor what he thought the biggest advance in coding  theory in the past 10 years was, and the chief editor said, well, without a doubt, it would  be polar codes.  So their group started pursuing it, and about the same time we had papers appear on the  archive.  So we did these, Saikaku and I did these two papers here, and recently one of the co-authors  on that paper, Joe Renas, we put our heads together and we came up with polar codes that  can achieve this exotic super activation effect that Grim Smith was talking about, where two  zero capacity channels, you can put them together, have non-zero capacity, except this is a near-explicit  code construction for doing that.  Okay, so just a little motivation.  From quantum Shannon Theory, quantum information theory, we have a pretty good idea of capacities  of channels for sending classical data or private classical data or quantum data.  Only for certain channels we have this idea, but there's still some open problems.  And there's been a fair amount of work on quantum turbo codes by David Poulon and others  in an attempt to achieve the capacity of a quantum channel, and also quantum LDPC codes.  These are explicit constructions, but you can't actually put these codes or capacity  achieving.  And there's actually very little work on codes for sending classical or private data, even  though this is an important problem where you can actually demonstrate a quantum supremacy,  as was said last night, turns out for a bosonic channel, if you have your detector perform  a joint collective quantum measurement, there can be a significant increase in the amount  of classical data you can send over this channel when there's a low photon number.  And so, as I was saying, these polar codes are promising in the classical world, and  from what I hear, they're being incorporated into standards for communication, so we thought  why not explore their quantum generalization.  And the result we found is a scheme that's near explicit, there's still some work that  needs to be done in this direction.  We can prove that their capacity achieving for certain channels.  Okay, so I'll start by describing this channel polarization phenomenon, and we'll do it for  the quantum case.  And in particular, I realize this is not a CEC conference, but I'm going to start out  with the classical case to build up to the quantum case, and eventually I'll get to QEC  in the talk.  Okay, so we'll begin with a channel that is a classical quantum channel, a CQ channel,  I'll call it W. It has a classical binary input X, and conditional on that some state  rho X is prepared at the output, and it doesn't matter if we mention the state.  So if you put in zero outcomes, rho zero, put in one outcomes, rho one.  An important channel parameter is something I'll call the information of W. In more detail,  we'll call it the symmetric Halevo information.  And it's just the mutual information, the correlations you can establish between the input  and the output when you select the input uniformly at random.  Okay, so that's why it's called symmetric Halevo information.  If you have formula, it'll work out to this.  And I could evaluate this information quantity with respect to this classical quantum state,  which corresponds to an ensemble I can prepare using this channel at the output.  And just to give you some idea, this parameter is equal to one if the channel is perfect,  and it's zero if the channel is totally useless.  So the useless case is when the cable is cut, like when Graham Smith was saying in his talk.  Okay, so this is an important channel parameter.  And the inventor of polar codes is a professor named Ari Kahn, and his idea was to take two  copies of this channel and just do a classical C knot, okay, at the input.  And what you can observe is this information preservation condition, okay.  So if I compute twice the information of the original channel, it'll be this quantity  when you work it out.  And this is an information evaluated with respect to these two inputs.  And since this gate is reversible, the information here is equal to the information of these  when these two inputs are input.  But what we can use is something that's well known in information theory.  It's the chain rule for mutual information to break this information term into two parts,  okay.  So it's very important for the polar coding idea, okay.  And this chain rule, it's suggesting that we can actually think about two different  channels.  There's a channel from the bit U1 to the two outputs, and a different channel from the  bit U2 to the two outputs with the bit U1 as side information, okay.  So to give a picture of this, this first channel is a bit channel from U1 to the two outputs  where this is acting as noise.  It's not known to the receiver, okay.  I'll call that W minus.  Maybe think it'd be a worse channel than the other one where U1 is available as side information,  right.  So I'm just taking this, this channel here is a bit channel from U2 to these outputs,  U1 and the two quantum outputs.  And what's happening is that this U1 is available as side information, okay.  So when you look at these pictures, maybe it's already hinting at how a decoder could  work in decoding these bits, okay.  And what we came up with is an extension of Arikhan's ideas.  We call it a quantum successive cancellation decoder.  Okay, that's a name that comes from information theory.  But the idea is that the decoder would first decode U1, assuming this is noise, and the  receiver would do this by doing a simple quantum hypothesis test, right.  While on U1, there's some state that's prepared at the output.  I could call it say, or signal 1.  And the receiver would just do what's called a helstrum measurement, project onto the positive  eigenspace of the difference of these two operators that are prepared at the outputs,  okay.  And then, assuming that the decoder corrected U1, that the decoder decoded U1 correctly,  it's then available as side information to do a second quantum hypothesis test to determine  U2, okay.  So that's the idea behind the decoder.  But what you do is you continue this construction recursively, okay.  Because we're going to need many copies of the channel to make some interesting statements,  okay.  So what I'm doing here is I'm taking, I had this channel, this channel W2, right, this  block here, and I take copies of it, and this recursive construction, right.  So I'm placing them here and here.  This operation, which it just places all of the odd indices, U1 and U3 first, it's putting  them here, and it's taking the even indices and putting them next.  So in this case, it just amounts to a swap of the middle two bits.  And then I do a C knot on every pair of bits coming at the input, okay.  So the idea is just a bunch of C knots, swap things around, C knots, swap things around,  and it happens recursively and it builds it up, okay.  And you can use the same idea of the chain rule, this information preserving condition,  four times the original information of the channel using the chain rule will distribute  in this way, such that I can think of four different channels now.  The channel where the receiver is trying to get U1 first, conditional on that, getting  U2 and so on and so forth.  So a picture of that again, just to have that point home, the decoder is trying to get U1,  these bits are random.  Assuming it gets this correctly, he's U2, and these are random, so on and so forth it  continues, right.  So finally I have this picture here.  Okay.  So you continue this construction recursively many times, and the chain rule recursively  will be this, just where you're trying to get the bit I, conditional on the previous  I bits, or the previous I minus 1 bits.  And this is the important statement of channel polarization, okay.  So we're thinking about these induced channels from bit I to the channel outputs, right.  And the statement of channel polarization is that a fraction of the channels will be  completely perfect.  Okay.  So we can prove this, and the complementary fraction will be totally useless, okay.  And the fraction of channels that are perfect is equal to the capacity of the original channel,  and the fraction of channels that are imperfect, the complementary number, okay.  So you can prove this result using martingale theory, that's what Arikhan did, and we used  quantum generalizations of Arikhan's inequalities to prove this result, okay.  So I'll go into that in a little detail to give you some idea of how it works.  There's a different parameter we can think about that we'll call the fidelity of the  two output states.  Now keep in mind we're not considering quantum communication here, we're considering classical  communication.  So the interpretation of fidelity is a little different.  We interpret it as a distinguished ability measure, okay.  So how well can I distinguish row zero from row one?  And quantumly we know it's this Hilbert Schmidt norm of these two states.  And so the fidelity actually is zero if the states are orthogonal, if they're perfectly  distinguishable by some measurement, and it's equal to one if the states are completely  indistinguishable, okay.  So since it's classical transmission it's a different interpretation, okay.  And this generalizes the classical fidelity, which in the classical world they call it  the Botticharia parameter, okay.  And sort of an operational interpretation of this quantity, this is a parameter of the  channel, the CQ channel.  If I'm trying to do a quantum hypothesis test to distinguish the bits from each other,  then the fidelity serves as an upper bound on this error probability.  And we use this in the proof to show that the scheme works well, okay.  So you would expect these parameters to be related, right.  In particular, if the channel is good for sending classical data, you'd expect the states  to be distinguishable, right.  So if the information is one, if the channel is perfect, the states should be totally distinguishable.  And if the information is zero, if the channel is useless, you'd expect the states to be  completely indistinguishable, okay.  And you can make this precise with these bounds here, right.  So if the fidelity is zero, this term here will lower bound the information, which you  can show as one.  And if the fidelity is one, if the states are not distinguishable, then the information  will be zero, okay.  So we can prove these bounds using prior results of Halebo and some recent results of  Rogga and others.  Okay, and what's nice about this is you can prove things about fidelity, and that will  imply similar things about the information quantity by these bounds, okay.  So recall this recursive channel construction that we had before, we do this many times.  And I'm going to call the channel induced from the ith bit, so say i is two, we'd be  thinking about u2, and the nth recursion level, so here the recursion level is two.  There's some bit channel there.  And what you can show in this recursive construction is that the information of the ith bit there  and the next iteration of the recursion will spread away from the middle, okay.  So there will be two places in the circuit that will sort of spring forth from the ith  bit channel.  And what happens is they move away from the center in this construction, okay.  So this is actually how the polarization effect takes hold.  These information quantities are moving away from the middle of the interval between zero  and one, and they're being pushed towards an extreme, towards zero or one, okay.  So that's what this is showing, and a complementary sequence set of inequalities holds for the  fidelity parameter, okay.  And there's some other inequalities that you need to show this, but this is the basic idea,  okay, and we can prove the generalizations of Arikhan's ideas.  Okay, so then we're thinking of this splitting process, the way that the channels get created  under this recursive encoding, and you can actually model the channel splitting process  as a random birth process, okay.  So I take the ith bit in the nth recursion level, and I represent it as a binary sequence,  and this tells you where I'm going in this tree, right.  So I model this as a random process, and what you can show is the fidelity of the ith channel  where I is a random parameter, right, it's this binary sequence.  This process is a martingale, and you can use a martingale convergence result, and  the inequalities in the previous slides to show that this random variable will converge  to a zero one valued random variable.  So that's the polarization effect, okay.  And what you can show is that the probability that this ith channel is zero, the fraction  of channel is good, is equal to the capacity.  So that's the basic idea that we were able to show in the quantum case.  So once you have this, it immediately leads to your coding scheme, right, I mean it's  pretty obvious from there.  If you know which channels are the good ones, so this is sort of the existence part, right,  we're using this probabilistic argument to say that this effect will take hold.  So if you know which channels are the good ones, you send your information bits through  those, and if you know the good ones, you'll know the bad ones, so you'll just send a pre-agreed  upon values for the uncillibits through those other channels, okay.  And then the decoder is just this quantum successive cancellation decoder, so you perform  the sequence of conditional hypothesis tests to figure out your bitstream, okay.  And the key tool that we use to analyze the error process show that the scheme is in fact  capacity achieving is a recent bound of Pernab-Senn found in the context of quantum information  theory.  I call this bound the non-commutative union bound, I've said it at a different conference,  I think this bound is really important and can be used in many different contexts.  It generalizes the union bound from probability theory and this is used all the time in many  probabilistic arguments.  And so the reason this is like a union bound, is there a, let me actually go to the board,  sorry here real quick, just to show how it generalizes the union bound.  So the union bound from probability theory, just to remind you, if I'm interested in computing  a correct, the probability for a correct sequence of events, I can think about, oh I'm  thinking, I want the intersection of a correct sequence of events, right.  So I can instead analyze the complement of that, that's what this first term here corresponds  to, right.  So when I do so I apply the Morgan's law, right, and I'll get the union of the complements  of the events.  So once in the union bound this is bounded by the sum of the complements of the individual  events, right.  So that's what this is doing, right, except with projectors.  So the sequence of projectors corresponds to a correct sequence of events and one minus  that is the complement and then it's upper bounded by the complement of each individual  event, the complement of these projectors with the exception that there's a two square  root in front and that comes from the non-communitivity.  If the projectors commute you can remove the two square root and get the union bound.  But if they don't, in general, you need this two square root, you can find counter examples  where you can demonstrate that this is needed.  Okay.  So the idea is we can bound each of these events, the events for the individual channels  by an exponentially decreasing term and there's a linear number of them so there's an exponential  finding the linear term and the exponential always wins.  So that's the basic idea behind proving the scheme that achieves the capacity.  Proving that it achieves the classical capacity.  So now I realize that this is not the PEC conference, the conference for private classical  communications.  This is the step that we need to finally get to the QEC.  So we have, this is in relation to what David Kribs was talking about, relations between  sending private data and sending that to the conference.  So assume that we have a quantum wire tap channel, it's a classical wire tap channel,  there's some classical binary input, it leads to a state of the output that's shared between  Bob and Eve.  So we can think about the channel to Bob just by tracing over Eve and we can think about  the channel to Eve just by tracing over Bob.  I'm going to call the channel to Bob W and we want to Eve W star and what's known is  that if the channel is degradable, meaning that Bob can simulate Eve by applying some  channel to his output.  So in a sense, his output is not as noisy as Eve's, then you can prove that the private  capacity is equal to this information difference.  So the idea is just that the amount of private information you can send is just the difference  between what Bob gets and what Eve gets.  And so what happens in this setting, we have two different channels, right, and each polarize  in their own way.  There's going to be channels that are good for Bob and bad for Bob and ones that are  good for Eve and bad for Eve.  So overall, the channel will polarize in four different ways.  There will be those that are good for Bob and good for Eve as well.  And we don't want Eve to get any information, so we won't be sending information bits through  those, but since they're good for Eve, we want to randomize what she's getting.  So we send random bits through those.  And this all is important because we're going to make coherent versions of this on the fourth  one in slides.  Ones that are good for Bob and bad for Eve, well, that's where we can put our private  data because Eve won't be able to get the information there, but Bob will.  And so we just send the information bits into those.  And finally, well, not finally yet, but there are ones that are bad for Bob and good for  Eve.  And we can't guarantee that Bob will be able to decode the bits put in there, but Eve might  be able to.  So we need to randomize her.  So we need something that Bob will have access to, so he can decode faithfully.  We also need to randomize Eve.  So the best thing we can put in there is halves of secret key bits.  So don't start flinging tomatoes yet.  We can show that the amount needed here, the consumption rate of secret key, goes to zero  for certain channels.  And then finally, there are channels that are bad for Bob and bad for Eve.  And since Eve can't get those, we'll just put the unsold bits there that Bob knows,  such that it can help them decode the information that's sent through.  And what we can show is that the channel is degradable, such that the map to the environment  is classical.  So there's some density operator for Eve, row zero, row one.  And if it's diagonal on some basis, this is what I call a channel that's degradable with  classical environment.  And we can show that the scheme provably achieves the wire tap capacity using this successive  cancellation decoder.  There are actually many channels that have this property, amplitude damping channels,  defasing channels, cloning channels, the racer channels, et cetera.  So this is a useful scheme.  And what we can also show is that this rate of secret key required goes to zero, an asymptotic  limit.  Okay, so now finally, we're at the QEC slide.  The basic idea is to run the wire tap code in superposition.  These are ideas that were used by Dev Attack to prove that the coherent information is  an achievable rate for quantum communication.  And so what we're doing instead is using a coherent version of the same encoder.  The encoder is just going to be C knot gates and swaps.  And when you consider the channel, you know, they're probably saying any channel will have  an extension to an environment as well as Bob's, so the overall channel is unitary.  So this induces a wire tap channel.  So then there will be channels that polarize in four different ways, just like we had for  the wire tap phase.  So there will be channels that are good for Bob and good for Eve.  Remember from before, we put random bits into those to randomize Eve.  Now we're just going to put the coherent version of a random bit, which is a plus state, into  those channels.  There are channels that are good for Bob and bad for Eve.  We put information qubits into those.  There were those channels that were bad for Bob and good for Eve, so remember they're  bad for Bob, so we need something there that can help them decode.  While we want to randomize Eve, we put a secret qubit there before.  Here the version of a secret bit is an ebit, an entangled bit, bell state.  But remember for certain channels, we can show that this entanglement consumption rate goes  to zero.  And then finally, there were these channels that are bad for Bob and bad for Eve.  And since they're bad for Eve, we can put something that's agreed upon for Bob to help  them decode and we put an encilic qubit there.  So the decoder in this case is going to consist of two steps.  Remember we had a measurement, this quantum successive cancellation decoder that worked  well for getting the private information.  So we're going to run a coherent version of that.  Any measurement you can do sort of as a controlled operation.  So we'll be doing that.  And so that's the first step.  And finally the second step is a controlled decoupling unitary.  It's guaranteed by Oman's theorem.  This part is not efficient.  The first part is not either, but it's explicit.  And there's a linear number of quantum hypothesis tests.  For Pauly channels, Renner and others were able to show that it is efficient.  So in analyzing the proof that this scheme achieves the capacity, we just use the fact  that the decoding measurement is reliable and also that it's secure to guarantee that  the quantum data can be decoded well.  So the decoding circuit would look something like this.  This is the encoder consisting of all these C-nauts and permutations and outcomes something  for Bob and something for Eve.  This part right here without this is just the measurement that was this quantum successive  cancellation decoder.  And then running it coherently, I'm taking the outcomes and putting them in these two  registers coherently.  And then finally this is the controlled decoupling unitary.  So this was the first scheme that we have in this paper.  Then recently, within the past two weeks, I've been working with Joe Renez and we can use  some of his ideas from his scheme to come up with a slightly different scheme, but there  are relations between the schemes.  So Joe Renez has written all these papers about how sending quantum data is like sending  classical information in complementary bases in like 10 papers in this topic.  And so we're using this idea except in this explicit context where we have this polar  code construction.  So the way he thinks about quantum information I've had to learn recently is if we have a  quantum channel, we can think about a classical quantum channel where we're sending some bit  into the amplitude basis, which is just the eigenbasis of the V-operator.  And then if we're able to decode that successfully coherently, we can think of the next channel  in line as this phase encoded channel where a Bell state is available at the decoder.  This comes about from the decoding process.  It sort of creates these Bell states that have phase information encoded onto them.  So this is this phase encoded channel.  And his coding scheme is, well, channels that are good.  The channels that are both good for amplitude and good for phase, there's a section which  will be able to decode these channels because decoding quantum data is like decoding classical  data well in complementary bases.  And the channels that are good for amplitude but bad for phase will need some phase bits  there to help Bob decode the phase channel because those are bad in this right here.  And ones that are bad for both bases will need halves of e-bits there because in a sense,  if you have an e-bit and Alice does a measurement locally from the Zeoggan basis, Bob will be  able to predict the outcome of that measurement.  And the same happens in the phase basis.  If Alice does a phase measurement, if she does a measurement of the X-operator locally,  then Bob will be able to predict the outcome of that measurement.  And related to that is why we need e-bits here because these e-bits will help decode  the channels that are bad for both bases.  And then finally, there are channels that are bad for the amplitude basis but good for  the phase basis and Bob will need information in the amplitude basis to help him decode  these bad channels.  So we really wanted this archive number here because it's really symmetrical and pretty.  We're going to wait for a while to get this nice pretty number here.  There's no two, two, two, two, two.  So the way that this works, we have these amplitude channels, channels in the amplitude  basis and we know from the polarization results that this number of channels will be good  for the amplitude basis.  And then from the phase results, the C system here is the half that's available to Bob for  helping decoding the phase information so we know that this number will be good.  And then what you can show is that the net rate, when you just consider the sizes of  these sets and sort of some basic set theoretic operations and the sizes of sets, shows that  the net rate of quantum communication will be the sum of these two minus one.  And so we're subtracting off the e-bits that were used to communicate.  And what you can show, what Joe has done in previous papers, all these papers he wrote,  this rate will be equal to the coherent information.  And so this is a picture I lifted from one of Joe's papers.  This is how the decoder would work.  First you're decoding the amplitude information and then coherently copying it to this Anciller  register.  And then this process is what induces that phase channel that I had in the previous slide  where the bell state was available with phase information encoded onto it because you're  getting a coherent copy of the amplitude information in this register.  So then the phase measurement run coherently, acts on these two systems and copies it to  this register.  And finally doing a whole linear number of controlled phase gates, you can decouple the  environment.  This isn't dynamical decoupling, but this is a decoupling operation.  And so using a linear number of those, you can decouple the environment and get the quantum  data that Alice was trying to transmit to Bob.  What's nice about this is that this is explicit, this is explicit, and this is explicit.  This is a linear number of coherent quantum hypothesis tests run in succession.  This is the same type of thing.  So this work reduces the problem of the decoder for general channels to figure out how to  make these two things efficient.  And this is known to be efficient.  So this is an improvement over the previous scheme that I had in the slide.  Now what's sort of the cool statement we can make is that this scheme will achieve super  activation for the channels that Graham Smith and John Yar gave in the examples, the channels  that could exhibit this for me.  So the two channels that they gave were this four dimensional input PPT channel, positive  partial transpose channel, that has zero capacity.  The other channel by Graham's no cloning theorem argument was an eraser channel and  that has a 50% eraser channel and that has zero quantum capacity.  But put together, these have non-zero capacity and the result is a 16 dimensional channel.  So we can factor these 16 dimensions as a tensor product of four qubit input spaces and  we can use this qubit polar coding scheme to achieve the coherent information.  And the way this works is you coherently decode these amplitude and phase variables in this  order.  So first you decode the amplitude variable for the first qubit channel, and then using  that aside information in this coherency decoder, you decode the second amplitude variable  for the second channel in the four fold tensor product.  You keep doing this.  So after four rounds you'll get all the amplitude variables, then you can use those as side  information coherently, quantum side information to decode the phase variables.  This scheme will achieve the coherent information.  One thing we can't show is for these channels how to make the entanglement consumption rate  go to zero.  Because before we needed this condition that the channels were degradable.  But this doesn't hold for these examples.  So one thing I should say why we consider this a super activation is if the quantum  capacity is zero, then also the catalytic quantum capacity is zero.  That's maybe not obvious.  The catalytic quantum capacity is your entanglement to be consumed, but then the net rate of communication  is how many qubits you can get out minus the entanglement consumption rate.  So what you can show is that if the quantum capacity is zero, the catalytic quantum capacity  is also zero.  So that's why I consider this a super activation because we can super activate this catalytic  quantum capacity.  So that's all I have for now.  The polar coding scheme is nice.  What's known is the encoder, the decoder.  The encoder is efficient.  You can do it with O of N log N operations, sort of a butterfly like Fourier transform,  FFT type operation.  You can decompose it that way.  The decoder is a linear number of quantum hypothesis tests.  We're still working on that.  There has been progress.  Joe and Renato and Frederic Dupuis had this paper on the archives where they showed that  the decoder can be made efficient if the channel is packed.  Maybe this would be useful in addressing some of Daniel Goddison's questions from the previous  talk.  So this is the most important problem to make this decoder efficient for general channels.  And then the other one, of course, is figuring out which channels are the good ones.  This would make the scheme totally explosive.  So there's been progress in the classical information theory community on this problem  using approximation algorithms to compute which channels are the good ones.  And then we may want to extend this to other scenarios like compression or lossy data compression,  et cetera.  Okay.  Thank you very much.  Questions?  In the classical case to achieve good polarization, you need very long codes like 2 to the 20.  Is this the case in quantum case as well, I guess?  I would think so.  That's another bad aspect of polarization.  It's very long.  In your scheme, you were using the e-bit or half of an e-bit when both channels were  bad, but it didn't show up in your diagram.  So where is the other half?  That was just sort of supposed to be a figurative diagram.  You could draw a different diagram.  Sorry about that.  But where are they?  Are they still at the same?  Well, they're shared between Alice and Bob beforehand.  You're assuming you know the indices of the channels that are good or bad for amplitude  and bad for phase.  So the other half is already with Bob?  It's already available for Bob.  Yeah.  That's needed to show it works.  But there was some work in the classical world on these schemes for private communication  over a classical wiretap channel.  And when they evaluated in practice how many secret key bits were needed, they were able  to show in some cases that they were not needed.  Also for Joe Renes for Polly channels, they were able to show numerically that they were  not needed for a certain Polly channel in the classical world.  One last question.  You describe the recursive construction of these induced channels.  I was wondering, is it possible to say beforehand which one of these two to the n induced channels  you're going to get for a fixed channel to begin with?  Or you start with a fixed channel into the construction.  Is it possible to say which ones are going to be the good ones?  Which ones are going to be the bad ones?  That's who we don't know.  I believe if it's your channel, you can actually compute efficiently which ones will be the  good ones and the bad ones.  But in general, there was work, these approximation algorithms who addressed this question.  Related question is how quickly the effect actually kicks in that relates to Alexei's  question.  Is it understood from the...  It's understood.  Well, I think it's fairly...  It's understood that the block has to be long.  Like he was saying, two to the 18 in practice.  Let's thank Mark again.
Polar_codes_0_527.png Polar_codes_528_1019.png Polar_codes_1020_1079.png Polar_codes_1080_1499.png Polar_codes_1500_1571.png Polar_codes_1572_1895.png Polar_codes_1896_2939.png Polar_codes_2940_3011.png Polar_codes_3012_26471.png Polar_codes_26472_27035.png Polar_codes_27036_27671.png Polar_codes_27672_54911.png Polar_codes_54912_54983.png Polar_codes_54984_55247.png Polar_codes_55248_55379.png Polar_codes_55380_55559.png Polar_codes_55560_55607.png Polar_codes_55608_56771.png Polar_codes_56772_57287.png Polar_codes_57288_57335.png Polar_codes_57336_57467.png Polar_codes_57468_58715.png Polar_codes_58716_58967.png Polar_codes_58968_59162.png
Okay. Okay, Mark Wilde, Policodes. Okay, so sorry about that. Thanks for having me at this conference. And in light of the panel discussion last night, I've opened the panelists won't start throwing tomatoes at me, but my talk is about codes for quantum communication, not necessarily fault tolerance. We're trying to find codes that can achieve the capacity of a quantum channel for communication. The fact that I'm so interested in this, you can partially blame on Todd Brunn. He never made me take a note to preserve, protect, and defend the quantum computer. So in the classical world, in the past, since about 2008, there's been some work on codes called polar codes, which have pretty remarkable properties. And we've been going to these information theory conferences for the past few years, and so we decided recently it would be a good idea to see how to make these codes work in the quantum domain. In parallel, Renato Renner and his group in Zurich turns out that Renato Renner lives in the same apartment complex as the chief editor of the IEEE Transactions on Information Theory, and they have these birthday parties for their kids, you know, these information theory people have birthday parties. And Renato Renner asked the chief editor what he thought the biggest advance in coding theory in the past 10 years was, and the chief editor said, well, without a doubt, it would be polar codes. So their group started pursuing it, and about the same time we had papers appear on the archive. So we did these, Saikaku and I did these two papers here, and recently one of the co-authors on that paper, Joe Renas, we put our heads together and we came up with polar codes that can achieve this exotic super activation effect that Grim Smith was talking about, where two zero capacity channels, you can put them together, have non-zero capacity, except this is a near-explicit code construction for doing that. Okay, so just a little motivation. From quantum Shannon Theory, quantum information theory, we have a pretty good idea of capacities of channels for sending classical data or private classical data or quantum data. Only for certain channels we have this idea, but there's still some open problems. And there's been a fair amount of work on quantum turbo codes by David Poulon and others in an attempt to achieve the capacity of a quantum channel, and also quantum LDPC codes. These are explicit constructions, but you can't actually put these codes or capacity achieving. And there's actually very little work on codes for sending classical or private data, even though this is an important problem where you can actually demonstrate a quantum supremacy, as was said last night, turns out for a bosonic channel, if you have your detector perform a joint collective quantum measurement, there can be a significant increase in the amount of classical data you can send over this channel when there's a low photon number. And so, as I was saying, these polar codes are promising in the classical world, and from what I hear, they're being incorporated into standards for communication, so we thought why not explore their quantum generalization. And the result we found is a scheme that's near explicit, there's still some work that needs to be done in this direction. We can prove that their capacity achieving for certain channels. Okay, so I'll start by describing this channel polarization phenomenon, and we'll do it for the quantum case. And in particular, I realize this is not a CEC conference, but I'm going to start out with the classical case to build up to the quantum case, and eventually I'll get to QEC in the talk. Okay, so we'll begin with a channel that is a classical quantum channel, a CQ channel, I'll call it W. It has a classical binary input X, and conditional on that some state rho X is prepared at the output, and it doesn't matter if we mention the state. So if you put in zero outcomes, rho zero, put in one outcomes, rho one. An important channel parameter is something I'll call the information of W. In more detail, we'll call it the symmetric Halevo information. And it's just the mutual information, the correlations you can establish between the input and the output when you select the input uniformly at random. Okay, so that's why it's called symmetric Halevo information. If you have formula, it'll work out to this. And I could evaluate this information quantity with respect to this classical quantum state, which corresponds to an ensemble I can prepare using this channel at the output. And just to give you some idea, this parameter is equal to one if the channel is perfect, and it's zero if the channel is totally useless. So the useless case is when the cable is cut, like when Graham Smith was saying in his talk. Okay, so this is an important channel parameter. And the inventor of polar codes is a professor named Ari Kahn, and his idea was to take two copies of this channel and just do a classical C knot, okay, at the input. And what you can observe is this information preservation condition, okay. So if I compute twice the information of the original channel, it'll be this quantity when you work it out. And this is an information evaluated with respect to these two inputs. And since this gate is reversible, the information here is equal to the information of these when these two inputs are input. But what we can use is something that's well known in information theory. It's the chain rule for mutual information to break this information term into two parts, okay. So it's very important for the polar coding idea, okay. And this chain rule, it's suggesting that we can actually think about two different channels. There's a channel from the bit U1 to the two outputs, and a different channel from the bit U2 to the two outputs with the bit U1 as side information, okay. So to give a picture of this, this first channel is a bit channel from U1 to the two outputs where this is acting as noise. It's not known to the receiver, okay. I'll call that W minus. Maybe think it'd be a worse channel than the other one where U1 is available as side information, right. So I'm just taking this, this channel here is a bit channel from U2 to these outputs, U1 and the two quantum outputs. And what's happening is that this U1 is available as side information, okay. So when you look at these pictures, maybe it's already hinting at how a decoder could work in decoding these bits, okay. And what we came up with is an extension of Arikhan's ideas. We call it a quantum successive cancellation decoder. Okay, that's a name that comes from information theory. But the idea is that the decoder would first decode U1, assuming this is noise, and the receiver would do this by doing a simple quantum hypothesis test, right. While on U1, there's some state that's prepared at the output. I could call it say, or signal 1. And the receiver would just do what's called a helstrum measurement, project onto the positive eigenspace of the difference of these two operators that are prepared at the outputs, okay. And then, assuming that the decoder corrected U1, that the decoder decoded U1 correctly, it's then available as side information to do a second quantum hypothesis test to determine U2, okay. So that's the idea behind the decoder. But what you do is you continue this construction recursively, okay. Because we're going to need many copies of the channel to make some interesting statements, okay. So what I'm doing here is I'm taking, I had this channel, this channel W2, right, this block here, and I take copies of it, and this recursive construction, right. So I'm placing them here and here. This operation, which it just places all of the odd indices, U1 and U3 first, it's putting them here, and it's taking the even indices and putting them next. So in this case, it just amounts to a swap of the middle two bits. And then I do a C knot on every pair of bits coming at the input, okay. So the idea is just a bunch of C knots, swap things around, C knots, swap things around, and it happens recursively and it builds it up, okay. And you can use the same idea of the chain rule, this information preserving condition, four times the original information of the channel using the chain rule will distribute in this way, such that I can think of four different channels now. The channel where the receiver is trying to get U1 first, conditional on that, getting U2 and so on and so forth. So a picture of that again, just to have that point home, the decoder is trying to get U1, these bits are random. Assuming it gets this correctly, he's U2, and these are random, so on and so forth it continues, right. So finally I have this picture here. Okay. So you continue this construction recursively many times, and the chain rule recursively will be this, just where you're trying to get the bit I, conditional on the previous I bits, or the previous I minus 1 bits. And this is the important statement of channel polarization, okay. So we're thinking about these induced channels from bit I to the channel outputs, right. And the statement of channel polarization is that a fraction of the channels will be completely perfect. Okay. So we can prove this, and the complementary fraction will be totally useless, okay. And the fraction of channels that are perfect is equal to the capacity of the original channel, and the fraction of channels that are imperfect, the complementary number, okay. So you can prove this result using martingale theory, that's what Arikhan did, and we used quantum generalizations of Arikhan's inequalities to prove this result, okay. So I'll go into that in a little detail to give you some idea of how it works. There's a different parameter we can think about that we'll call the fidelity of the two output states. Now keep in mind we're not considering quantum communication here, we're considering classical communication. So the interpretation of fidelity is a little different. We interpret it as a distinguished ability measure, okay. So how well can I distinguish row zero from row one? And quantumly we know it's this Hilbert Schmidt norm of these two states. And so the fidelity actually is zero if the states are orthogonal, if they're perfectly distinguishable by some measurement, and it's equal to one if the states are completely indistinguishable, okay. So since it's classical transmission it's a different interpretation, okay. And this generalizes the classical fidelity, which in the classical world they call it the Botticharia parameter, okay. And sort of an operational interpretation of this quantity, this is a parameter of the channel, the CQ channel. If I'm trying to do a quantum hypothesis test to distinguish the bits from each other, then the fidelity serves as an upper bound on this error probability. And we use this in the proof to show that the scheme works well, okay. So you would expect these parameters to be related, right. In particular, if the channel is good for sending classical data, you'd expect the states to be distinguishable, right. So if the information is one, if the channel is perfect, the states should be totally distinguishable. And if the information is zero, if the channel is useless, you'd expect the states to be completely indistinguishable, okay. And you can make this precise with these bounds here, right. So if the fidelity is zero, this term here will lower bound the information, which you can show as one. And if the fidelity is one, if the states are not distinguishable, then the information will be zero, okay. So we can prove these bounds using prior results of Halebo and some recent results of Rogga and others. Okay, and what's nice about this is you can prove things about fidelity, and that will imply similar things about the information quantity by these bounds, okay. So recall this recursive channel construction that we had before, we do this many times. And I'm going to call the channel induced from the ith bit, so say i is two, we'd be thinking about u2, and the nth recursion level, so here the recursion level is two. There's some bit channel there. And what you can show in this recursive construction is that the information of the ith bit there and the next iteration of the recursion will spread away from the middle, okay. So there will be two places in the circuit that will sort of spring forth from the ith bit channel. And what happens is they move away from the center in this construction, okay. So this is actually how the polarization effect takes hold. These information quantities are moving away from the middle of the interval between zero and one, and they're being pushed towards an extreme, towards zero or one, okay. So that's what this is showing, and a complementary sequence set of inequalities holds for the fidelity parameter, okay. And there's some other inequalities that you need to show this, but this is the basic idea, okay, and we can prove the generalizations of Arikhan's ideas. Okay, so then we're thinking of this splitting process, the way that the channels get created under this recursive encoding, and you can actually model the channel splitting process as a random birth process, okay. So I take the ith bit in the nth recursion level, and I represent it as a binary sequence, and this tells you where I'm going in this tree, right. So I model this as a random process, and what you can show is the fidelity of the ith channel where I is a random parameter, right, it's this binary sequence. This process is a martingale, and you can use a martingale convergence result, and the inequalities in the previous slides to show that this random variable will converge to a zero one valued random variable. So that's the polarization effect, okay. And what you can show is that the probability that this ith channel is zero, the fraction of channel is good, is equal to the capacity. So that's the basic idea that we were able to show in the quantum case. So once you have this, it immediately leads to your coding scheme, right, I mean it's pretty obvious from there. If you know which channels are the good ones, so this is sort of the existence part, right, we're using this probabilistic argument to say that this effect will take hold. So if you know which channels are the good ones, you send your information bits through those, and if you know the good ones, you'll know the bad ones, so you'll just send a pre-agreed upon values for the uncillibits through those other channels, okay. And then the decoder is just this quantum successive cancellation decoder, so you perform the sequence of conditional hypothesis tests to figure out your bitstream, okay. And the key tool that we use to analyze the error process show that the scheme is in fact capacity achieving is a recent bound of Pernab-Senn found in the context of quantum information theory. I call this bound the non-commutative union bound, I've said it at a different conference, I think this bound is really important and can be used in many different contexts. It generalizes the union bound from probability theory and this is used all the time in many probabilistic arguments. And so the reason this is like a union bound, is there a, let me actually go to the board, sorry here real quick, just to show how it generalizes the union bound. So the union bound from probability theory, just to remind you, if I'm interested in computing a correct, the probability for a correct sequence of events, I can think about, oh I'm thinking, I want the intersection of a correct sequence of events, right. So I can instead analyze the complement of that, that's what this first term here corresponds to, right. So when I do so I apply the Morgan's law, right, and I'll get the union of the complements of the events. So once in the union bound this is bounded by the sum of the complements of the individual events, right. So that's what this is doing, right, except with projectors. So the sequence of projectors corresponds to a correct sequence of events and one minus that is the complement and then it's upper bounded by the complement of each individual event, the complement of these projectors with the exception that there's a two square root in front and that comes from the non-communitivity. If the projectors commute you can remove the two square root and get the union bound. But if they don't, in general, you need this two square root, you can find counter examples where you can demonstrate that this is needed. Okay. So the idea is we can bound each of these events, the events for the individual channels by an exponentially decreasing term and there's a linear number of them so there's an exponential finding the linear term and the exponential always wins. So that's the basic idea behind proving the scheme that achieves the capacity. Proving that it achieves the classical capacity. So now I realize that this is not the PEC conference, the conference for private classical communications. This is the step that we need to finally get to the QEC. So we have, this is in relation to what David Kribs was talking about, relations between sending private data and sending that to the conference. So assume that we have a quantum wire tap channel, it's a classical wire tap channel, there's some classical binary input, it leads to a state of the output that's shared between Bob and Eve. So we can think about the channel to Bob just by tracing over Eve and we can think about the channel to Eve just by tracing over Bob. I'm going to call the channel to Bob W and we want to Eve W star and what's known is that if the channel is degradable, meaning that Bob can simulate Eve by applying some channel to his output. So in a sense, his output is not as noisy as Eve's, then you can prove that the private capacity is equal to this information difference. So the idea is just that the amount of private information you can send is just the difference between what Bob gets and what Eve gets. And so what happens in this setting, we have two different channels, right, and each polarize in their own way. There's going to be channels that are good for Bob and bad for Bob and ones that are good for Eve and bad for Eve. So overall, the channel will polarize in four different ways. There will be those that are good for Bob and good for Eve as well. And we don't want Eve to get any information, so we won't be sending information bits through those, but since they're good for Eve, we want to randomize what she's getting. So we send random bits through those. And this all is important because we're going to make coherent versions of this on the fourth one in slides. Ones that are good for Bob and bad for Eve, well, that's where we can put our private data because Eve won't be able to get the information there, but Bob will. And so we just send the information bits into those. And finally, well, not finally yet, but there are ones that are bad for Bob and good for Eve. And we can't guarantee that Bob will be able to decode the bits put in there, but Eve might be able to. So we need to randomize her. So we need something that Bob will have access to, so he can decode faithfully. We also need to randomize Eve. So the best thing we can put in there is halves of secret key bits. So don't start flinging tomatoes yet. We can show that the amount needed here, the consumption rate of secret key, goes to zero for certain channels. And then finally, there are channels that are bad for Bob and bad for Eve. And since Eve can't get those, we'll just put the unsold bits there that Bob knows, such that it can help them decode the information that's sent through. And what we can show is that the channel is degradable, such that the map to the environment is classical. So there's some density operator for Eve, row zero, row one. And if it's diagonal on some basis, this is what I call a channel that's degradable with classical environment. And we can show that the scheme provably achieves the wire tap capacity using this successive cancellation decoder. There are actually many channels that have this property, amplitude damping channels, defasing channels, cloning channels, the racer channels, et cetera. So this is a useful scheme. And what we can also show is that this rate of secret key required goes to zero, an asymptotic limit. Okay, so now finally, we're at the QEC slide. The basic idea is to run the wire tap code in superposition. These are ideas that were used by Dev Attack to prove that the coherent information is an achievable rate for quantum communication. And so what we're doing instead is using a coherent version of the same encoder. The encoder is just going to be C knot gates and swaps. And when you consider the channel, you know, they're probably saying any channel will have an extension to an environment as well as Bob's, so the overall channel is unitary. So this induces a wire tap channel. So then there will be channels that polarize in four different ways, just like we had for the wire tap phase. So there will be channels that are good for Bob and good for Eve. Remember from before, we put random bits into those to randomize Eve. Now we're just going to put the coherent version of a random bit, which is a plus state, into those channels. There are channels that are good for Bob and bad for Eve. We put information qubits into those. There were those channels that were bad for Bob and good for Eve, so remember they're bad for Bob, so we need something there that can help them decode. While we want to randomize Eve, we put a secret qubit there before. Here the version of a secret bit is an ebit, an entangled bit, bell state. But remember for certain channels, we can show that this entanglement consumption rate goes to zero. And then finally, there were these channels that are bad for Bob and bad for Eve. And since they're bad for Eve, we can put something that's agreed upon for Bob to help them decode and we put an encilic qubit there. So the decoder in this case is going to consist of two steps. Remember we had a measurement, this quantum successive cancellation decoder that worked well for getting the private information. So we're going to run a coherent version of that. Any measurement you can do sort of as a controlled operation. So we'll be doing that. And so that's the first step. And finally the second step is a controlled decoupling unitary. It's guaranteed by Oman's theorem. This part is not efficient. The first part is not either, but it's explicit. And there's a linear number of quantum hypothesis tests. For Pauly channels, Renner and others were able to show that it is efficient. So in analyzing the proof that this scheme achieves the capacity, we just use the fact that the decoding measurement is reliable and also that it's secure to guarantee that the quantum data can be decoded well. So the decoding circuit would look something like this. This is the encoder consisting of all these C-nauts and permutations and outcomes something for Bob and something for Eve. This part right here without this is just the measurement that was this quantum successive cancellation decoder. And then running it coherently, I'm taking the outcomes and putting them in these two registers coherently. And then finally this is the controlled decoupling unitary. So this was the first scheme that we have in this paper. Then recently, within the past two weeks, I've been working with Joe Renez and we can use some of his ideas from his scheme to come up with a slightly different scheme, but there are relations between the schemes. So Joe Renez has written all these papers about how sending quantum data is like sending classical information in complementary bases in like 10 papers in this topic. And so we're using this idea except in this explicit context where we have this polar code construction. So the way he thinks about quantum information I've had to learn recently is if we have a quantum channel, we can think about a classical quantum channel where we're sending some bit into the amplitude basis, which is just the eigenbasis of the V-operator. And then if we're able to decode that successfully coherently, we can think of the next channel in line as this phase encoded channel where a Bell state is available at the decoder. This comes about from the decoding process. It sort of creates these Bell states that have phase information encoded onto them. So this is this phase encoded channel. And his coding scheme is, well, channels that are good. The channels that are both good for amplitude and good for phase, there's a section which will be able to decode these channels because decoding quantum data is like decoding classical data well in complementary bases. And the channels that are good for amplitude but bad for phase will need some phase bits there to help Bob decode the phase channel because those are bad in this right here. And ones that are bad for both bases will need halves of e-bits there because in a sense, if you have an e-bit and Alice does a measurement locally from the Zeoggan basis, Bob will be able to predict the outcome of that measurement. And the same happens in the phase basis. If Alice does a phase measurement, if she does a measurement of the X-operator locally, then Bob will be able to predict the outcome of that measurement. And related to that is why we need e-bits here because these e-bits will help decode the channels that are bad for both bases. And then finally, there are channels that are bad for the amplitude basis but good for the phase basis and Bob will need information in the amplitude basis to help him decode these bad channels. So we really wanted this archive number here because it's really symmetrical and pretty. We're going to wait for a while to get this nice pretty number here. There's no two, two, two, two, two. So the way that this works, we have these amplitude channels, channels in the amplitude basis and we know from the polarization results that this number of channels will be good for the amplitude basis. And then from the phase results, the C system here is the half that's available to Bob for helping decoding the phase information so we know that this number will be good. And then what you can show is that the net rate, when you just consider the sizes of these sets and sort of some basic set theoretic operations and the sizes of sets, shows that the net rate of quantum communication will be the sum of these two minus one. And so we're subtracting off the e-bits that were used to communicate. And what you can show, what Joe has done in previous papers, all these papers he wrote, this rate will be equal to the coherent information. And so this is a picture I lifted from one of Joe's papers. This is how the decoder would work. First you're decoding the amplitude information and then coherently copying it to this Anciller register. And then this process is what induces that phase channel that I had in the previous slide where the bell state was available with phase information encoded onto it because you're getting a coherent copy of the amplitude information in this register. So then the phase measurement run coherently, acts on these two systems and copies it to this register. And finally doing a whole linear number of controlled phase gates, you can decouple the environment. This isn't dynamical decoupling, but this is a decoupling operation. And so using a linear number of those, you can decouple the environment and get the quantum data that Alice was trying to transmit to Bob. What's nice about this is that this is explicit, this is explicit, and this is explicit. This is a linear number of coherent quantum hypothesis tests run in succession. This is the same type of thing. So this work reduces the problem of the decoder for general channels to figure out how to make these two things efficient. And this is known to be efficient. So this is an improvement over the previous scheme that I had in the slide. Now what's sort of the cool statement we can make is that this scheme will achieve super activation for the channels that Graham Smith and John Yar gave in the examples, the channels that could exhibit this for me. So the two channels that they gave were this four dimensional input PPT channel, positive partial transpose channel, that has zero capacity. The other channel by Graham's no cloning theorem argument was an eraser channel and that has a 50% eraser channel and that has zero quantum capacity. But put together, these have non-zero capacity and the result is a 16 dimensional channel. So we can factor these 16 dimensions as a tensor product of four qubit input spaces and we can use this qubit polar coding scheme to achieve the coherent information. And the way this works is you coherently decode these amplitude and phase variables in this order. So first you decode the amplitude variable for the first qubit channel, and then using that aside information in this coherency decoder, you decode the second amplitude variable for the second channel in the four fold tensor product. You keep doing this. So after four rounds you'll get all the amplitude variables, then you can use those as side information coherently, quantum side information to decode the phase variables. This scheme will achieve the coherent information. One thing we can't show is for these channels how to make the entanglement consumption rate go to zero. Because before we needed this condition that the channels were degradable. But this doesn't hold for these examples. So one thing I should say why we consider this a super activation is if the quantum capacity is zero, then also the catalytic quantum capacity is zero. That's maybe not obvious. The catalytic quantum capacity is your entanglement to be consumed, but then the net rate of communication is how many qubits you can get out minus the entanglement consumption rate. So what you can show is that if the quantum capacity is zero, the catalytic quantum capacity is also zero. So that's why I consider this a super activation because we can super activate this catalytic quantum capacity. So that's all I have for now. The polar coding scheme is nice. What's known is the encoder, the decoder. The encoder is efficient. You can do it with O of N log N operations, sort of a butterfly like Fourier transform, FFT type operation. You can decompose it that way. The decoder is a linear number of quantum hypothesis tests. We're still working on that. There has been progress. Joe and Renato and Frederic Dupuis had this paper on the archives where they showed that the decoder can be made efficient if the channel is packed. Maybe this would be useful in addressing some of Daniel Goddison's questions from the previous talk. So this is the most important problem to make this decoder efficient for general channels. And then the other one, of course, is figuring out which channels are the good ones. This would make the scheme totally explosive. So there's been progress in the classical information theory community on this problem using approximation algorithms to compute which channels are the good ones. And then we may want to extend this to other scenarios like compression or lossy data compression, et cetera. Okay. Thank you very much. Questions? In the classical case to achieve good polarization, you need very long codes like 2 to the 20. Is this the case in quantum case as well, I guess? I would think so. That's another bad aspect of polarization. It's very long. In your scheme, you were using the e-bit or half of an e-bit when both channels were bad, but it didn't show up in your diagram. So where is the other half? That was just sort of supposed to be a figurative diagram. You could draw a different diagram. Sorry about that. But where are they? Are they still at the same? Well, they're shared between Alice and Bob beforehand. You're assuming you know the indices of the channels that are good or bad for amplitude and bad for phase. So the other half is already with Bob? It's already available for Bob. Yeah. That's needed to show it works. But there was some work in the classical world on these schemes for private communication over a classical wiretap channel. And when they evaluated in practice how many secret key bits were needed, they were able to show in some cases that they were not needed. Also for Joe Renes for Polly channels, they were able to show numerically that they were not needed for a certain Polly channel in the classical world. One last question. You describe the recursive construction of these induced channels. I was wondering, is it possible to say beforehand which one of these two to the n induced channels you're going to get for a fixed channel to begin with? Or you start with a fixed channel into the construction. Is it possible to say which ones are going to be the good ones? Which ones are going to be the bad ones? That's who we don't know. I believe if it's your channel, you can actually compute efficiently which ones will be the good ones and the bad ones. But in general, there was work, these approximation algorithms who addressed this question. Related question is how quickly the effect actually kicks in that relates to Alexei's question. Is it understood from the... It's understood. Well, I think it's fairly... It's understood that the block has to be long. Like he was saying, two to the 18 in practice. Let's thank Mark again.
can achieve the capacity of a quantum channel for codes, which have pretty remarkable properties. how to make these codes work in the quantum with polar codes that can achieve this exotic classical data or private classical data or describing this channel polarization phenomenon, zero if the channel is totally useless. So the the information of these when these two inputs outputs, U1 and the two quantum outputs. And Arikhan's ideas. We call it a quantum successive polarization is that a fraction of the channels channels that are perfect is equal to the proof to show that the scheme works well, okay. related, right. In particular, if the channel is the polarization effect takes hold. These showing, and a complementary sequence set of inequalities holds for the fidelity parameter, your information bits through those, and if you this bound the non-commutative union bound, I've projectors. So the sequence of projectors examples where you can demonstrate that this is classical binary input, it leads to a state of send the information bits into those. And the channel is degradable, such that the map to call a channel that's degradable with classical this successive cancellation decoder. There are amplitude damping channels, defasing channels, So this is a useful scheme. And what we can also is to run the wire tap code in superposition. achievable rate for quantum communication. And so channel is unitary. So this induces a wire tap analyzing the proof that this scheme achieves the basis and we know from the polarization results environment. This isn't dynamical decoupling, but has zero capacity. The other channel by Graham's achieve the coherent information. One thing we have for now. The polar coding scheme is nice. ones. And then we may want to extend this to world on these schemes for private communication over a classical wiretap channel. And when they