Transcription
From IQC Debbie Leon, thank you. Um, so, can you hear me okay? Uh, so, um, this is on rate distortion theory for mixed-state quantum data compression. Oh, so I forgot to say that, uh, thanks to the organizers. I love the meeting and thanks for inviting me to be part of it. Um, so, very happy to be here and having very good interaction. This is my first meeting, uh, post-pandemic. So, got the, um, so, um, this is joint work with Sarah Canyon and Kodako Iwa. That's the bulk of the work that I would describe. And I will mention some small amounts of work from something earlier with Annual Andrew and David. In fact, I was planning to talk about this result four years ago, but I did that in the end because I did not make the slides. So, finally, it's good, the full circle that I managed to do it. And a little bit of warning in advance, I told one of the participants that this has been something I have been working on. The feedback I heard was that, oh, rate distortion theory is boring. So, this is how I'll make an analogy. Um, this is a little like running instead of playing soccer. Soccer is exciting and fun. Um, this kind of work, it's a little like running. So, it's very good for you, it can be a little boring. And, um, when you're tired, you should go to the store. So, if I, if I'm slow, if I'm too fast, there's something that you just didn't hear me, or there's something that is missing because it's a big gap between this audience and the kind of information theory community. Please, you ask questions. Just like one thing, there is no fixed distance I had to go through. So, I can keep my talk flexible length. So, make sure that you ask questions if something doesn't make sense. On the ball, so then I'll start with the first concept of an ensemble quantum state. It's a very natural idea that you have some fixed set of states. By the way, everything is finite dimensional in the talk. Um, matrices, uh, the same. Like, there's no subtlety. No, this is algebra, not not that. Anywhere, everything is finite dimensional. So, um, and so, without loss of generality, you can even think about this as a finite set. Um, and for all purposes, uh, these guys live in system A. Um, these are density matrices that I'm writing down, and these are the classical labels. Then the experiment goes by someone drawing one of these labels X at random, and the label X occurs with probability Px. So, these are just probabilities. And then afterwards, if that's a good experimentalist, they will write it down in system X and also they will prepare the density matrix, the state row X in system A. So, this person can be a student of one of my experimental colleagues, like you see one of Christmas with them, for example. Any question on this physical process? Draw a classical random variable according to a fixed distribution. So, Px is known upfront. This list is known upfront. Then draw the random variable, prepare the same transmitted in the end. But let's write down physically what is the state corresponding to this. My apology for using row for a state and sometimes they are not the same state. When I use the same label row, I hope the context will make it clear. When I add the subscript, the subscript would clarify the context of what that is referring to. So, um, I'll write at the state on the system X and A combined is sum over X, have the label in system X. I use the bracket notation most of the time. Tensor row X living on system A. So, now this is what we want to do. I will repeat this N times. So, then you get this particular state because this, um, when we draw it N times independently and identically, the probability to get a string of outcome X1, X2, X3, XN is the product distribution, the product probability Px1 times Px2 and so on. And correspondingly, you have this N density matrices, this N states on the N quantum systems. I just call them A1 through AN, so that I, I remember which one is which. And the overall state is row N. So, with quantum data compression, what we want to do is imagine a situation in which the referee is holding the recollection and what state has been prepared. The standard Alice is given the quantum states, the row one or X1 or X2 through XN in system A1 through AN. We will discuss whether she knows this label, so not later, but for now, she doesn't. She only has these quantum states. The goal is for Bob at the end of the day to be the one holding those things. So, it's just sending those row one, row is one, row X2 from Alice to Bob. And just for, for the sake of trying to be careful, I will label the system as B1 through BN. So, let's go. We will also need to discuss what approximations are allowed. So, any question on the setup so far? Noticeable. I'll use a different color for the method. So, roughly speaking, Alice is allowed to encode the input. Of course, the encoding map has to depend on the block length. That this number N is called the block length. She would then transmit a message to Bob. So, this is a, this is a TCP map spitting out a quantum system M, the message system. And but we decode the rate. The communication rate is 1 over N log base 2. In this talk, the dimension of M. So, sure, I'll use this symbol for the dimension of a quantum system. And the goal is to perform this task while minimizing the communication rate. So, now there are varieties to this basic setup. It is ordinary usage, it's not mathematical usage. So, the first one is, you can allow side information for Alice. But this comes in the form of another N system that she is allowed to use for her, um, for her encoding map. And let me write down what that is. So, um, they will be in some state. So, for every label X, they correspond to a particular J of X in the side information system. Alice can use to do the encoding. And so, these are also just following the label we have in experiment. What label has been drawn? And there are two extreme cases of side information that has been happily studied. The first one is called visible compression. In that case, JX equals to XC. So, Alice, in visible compression, is told what state she is compressing. In the opposite extreme, in what we call blind compression, she has no information on the state being compressed. So, they, they're two extremes. And what we have been doing in our work is to use a more general setup that includes both. But we'll describe, um, it's, you know, special results when we need to make a distinction. Then the second variety you can consider is entanglement. So, ever symbol cache entanglement in advance. I'll call this system A0 and this system B0. In some settings, they may regenerate the entanglement in the end. The entanglement rate. So, we'll have to distinguish between these two rates. Now, is 1 over N log. So, there are three settings you can consider again. Um, two extremes are the fact that it's free. So, you don't limit the slice of A0. Then we call this assisted. Or there's no entanglement allowed. So, A0 has dimension one. Unassisted. And then you can consider anything in between. You just have two rates. I hope. So, any questions so far? Square root of A star A, right? Or top maps, right? No, this is the dimension. Okay. The other condition also makes sense. It's just here. Yeah. What depends on which community you're in. I was actually preparing the whole talk with the dimension there. But then when you write functions of the dimension, they become a mess. It's fine. So, now, after all that, you may want to see an example of how this can even be done. Um, so, let me introduce an even more complex, ambitious task, very heavily related to data compression, but it is a little fancier. It's called quantum state redistribution. That's due to Death Attack and yeah, 2008. So, in this particular setting, there are three parties, Alice and Bob, sharing some mixed state. There is a referee holding the purification to the next day. It's in the ID sense that there are N copies of a certain state. And the point is that Alice initially has two systems, T and Z. At the end of the day, C has to go to Bob. She's still holding T. And Bob still, um, Bob has a system right at the beginning, and he's still having the same system Y in the end. State redistribution going to a book. If anything from this talk, I think this may be the most interesting part. But because this is a very important modern result, let's give rise to a lot of useful development. So, now this is again, the white part is the goal of the task, quantum state redistribution. And I'm going to use orange to show you the protocol that will do it. Um, Alice again has an encoding map that includes. So, the important thing is that they share entanglement, A0. So, Alice makes an encoding map on three systems. Again, a message, message system will come out and be sent to Bob. So, at that point, Bob has three systems: his entangled system, his, original system, and the message. So, he puts a decoding map that picks all three and spits out the thing that he already has and the thing that he should have at the end. And in this framework, just as a side, they can in principle recycle entanglement. So, Alice will output an A1, Bob will output a B1. And so, they can in principle have at the end of the day some good entanglement in the end. And the goal is that this should be in this state. So, they, the result they have is that this process will have global error in the most stringent sense, trace distance between the output and the input. If possible, the, um, is the communication rate at least half the mutual information between the reference Z and the communicative system C, conditioned on Y. And if the communication plus entanglement rate, I should say communication rate plus entanglement rate, is at least the conditional entropy of C given Y. Now, I won't bother defining the conditional mutual information and entropy because when I want to use this setup for data, data compression, Bob has nothing in front. So, Y is sugar for my problem. So, I, I don't want to waste time on that. So, um, so then it's just the ordinary contribution information between Z. Is okay? Any question on quantum state redistribution? Just, just one. Reverse of all that's, of course, a simple model for, for one-way quantum communication, right? That's a general feature. And then you are requiring that you achieve that rate, or you know that you can that I don't understand. I'm sorry. I should, you want that rate to achieve, or you win, or I don't. I just go. So, what they prove is that, um, this task can be performed with vanishing error if and only if the communication rate is at least this big. And then the combined communication and entanglement rate is at least this way. So, that's the statement of the results. It's a really nice result. Um, in particular, it is reversible. That's another really nice thing about it. But what we need it for is something much simpler because, what Bob has nothing with him. Upper, I have some plan to get the Bob's right. But I get really intimidated after a few people. It's not that it's actually not so easy. I'll try to lift those three up for a while. When they're working pure cleaning, they found a protocol which verifies that. Or again, they found a protocol or some configuration which I mean, the down-up implication means you have to somewhat construct the channel, right? It is constructive. Yes, the way they prove. So, they're two sides to prove that you have a problem with that would do it. And then you cannot. And then you have to show the what we call the converse, that you can't do better. Of course, if what you mean is whether it is a randomized construction or not. Uh, yes. Um, I suppose some form of derandomization should be fairly straightforward. Let's reduce embezzlement. No, no. So, um, yes, one thing to mention that is understand the EPR pairs. And I think I think roughly speaking, it involves, um, applying a random unitary at some point. According to how measure that in the minimal can be derandomized to a true design. So, which is a, it's smaller than a random Clifford. But whether it can be further derandomized or not, I lost track. So, um, so, uh, examples of quantum data compression. So, the example one is to use the camera. Just take state with distribution Y. Um, now, one small thing we need to do before we apply that result should have pushed the board up. We still have a mixed state description here. So, we need to purify the system. This A1 through AN is in this row, row X1, row X2, and so on. These things are mixed. That's the whole point about our work. So, we purify each, um, row X on A is purified to some side X on R A. So, that's what we do here. So, we have R1 through RN to do the purification for the state itself. And then this label, classical label, is also a mixed state. So, you need to purify that too. And the purification doesn't look too bad. Maybe I'll try again. Into your Z, right? What you're adding now? That's right. That's right. Um, so, yes, you can start matching how you want to use it. But the purification first has a form sum over X. So, I'm purifying row here, just one copy for now. Um, and then you can do the handset yourself. So, we sum over X. We have an amplitude now instead of the probability. We have an X on X, pi X on X, J X on J, phi X on A, R. And when we trace out on the side, then you get that row X. And so, the way we can just apply quantum state redistribution is to identify the pieces. T is J. There's no Y. C is A. And then, um, Z is X, pi X, R. So, we can do it with rate no more than half the mutual information between, you can call it A, you can call it B, you can call this C. They're going to be all the same at this rate. And then there's an entanglement rate. Throughout the talk, I'm not too concerned about entanglement. Just assume it's free if you want to. The second example, um, is the original Schumacher compression. In that case, it is on the system. There's no entanglement given. There's no side information. And the communication rate is that of the piece that has to be communicated. And that is sum over X, DX, row X. So, you take the, oh, you take the ensemble of states. You make the, you look at the average state. Look at the entropy. That is your rate to use Schumacher compression. I mean, historically, that's wrong. I mean, he did it first. It's a very nice protocol. But I, I need to define both. So, I, I'll just define one this way. Now, the point is that this rate is optimal if these states are pure. And surely, it is not optimal when the states are mixed. Just an example. So, to see that this doesn't work for mixed states, take your favorite ensemble. Say, equal probability. Attach garbage. The maximally mixed AI over D has nothing to do with the state. It's just there. It's just there to pump up your entropy. So, this ensemble, you should be able to compress it down to one, one qubit per copy. But the log D is there to cause your problem with that rate that was written down. Okay. So, we know that this expression does not work for mixed states. So, in a slightly more refined way to understand what's wrong with the expression, consider these two states. Actually, I don't even need to make correction. It's so unreadable that it looks like a five-two. So, if you look at these two states that Alice has to compress, there's never any reason to send the omegas because if you have the first system, you can generate a condition on one new generation Omega 1. Condition on zero, you can generate Omega 0. So, in the least, Alice should remove, discard this last system before trying to compress. So, they are named for this. This is called the classical part. The middle one is the quantum part. And this last part is the redundant part. So, in around 2001, Courage and Immortal developed a method to reward any ensemble into this form. It's an algorithm that you can run on your, on your ensemble. So, that you can maximize this decomposition that you cannot refine it further. So, you have maxed out how much is redundant. You can also extract everything that is classical. And the rest, you can't compress. Sure that they are the quantum parts. And it's a well-defined process. And then the optimal rate that here. So, the way that the optimal thing to do is to send the first piece through a classical channel. You do data compression of the classical message. Then the middle, middle one, so, using Schumacher compression. Away the last one, that's optimal. Now, if you don't have separate consequent and quantum channel, you only look at one combined communication rate. You have no choice. You send the classical data to quantum channel as well. There's no saving there. There's no time when you come to super dance school thing. So, so you see the first example of a theme here. It looks like we can do better. But the best thing we can do is not a lot better than what we already have. Um, what we have done is to remove an obvious problem. So, we distort. So, at the encoding level, Alice turns her ensemble to a new ensemble which has less cost, which has a less smaller rate. And then perform standard data compression on the new ensemble. And then the optimization involves finding the, the new ensemble that has the least rate. Um, so, just a two-step process. Distort the ensemble. It has to be something that Alice can do. In this case, that's discarding the redundant part. And then perform that thing has vanishing error. You know, the rate. And then optimize the distortion. I'll do one more example of the standard results. Um, so, when you don't have entanglement, but you have side information that is complete in the, in the visible scenario, how well can you do? If the states are pure, you can't do better. Just state it verbally. But if you have a mixed state, there is a small little trick that seems to be useful. So, so Alice, that knows X, what should we do is that she's just, so, away the state given to her. It's not very useful anyways. And then she replaced that row X by what we call an extension of the space. So, a state is an extension if you have this relation that you can trace a time sigma X on A, A prime gives you back row X on A. It's a little counterintuitive. She's supposed to send X, row X in system A, and instead she sends something bigger. She sends a sigma X on two systems, A and A prime. But remember that later on, we do chemical compression that looks at the entropy of the average state of the ensemble. Now, why would getting a bigger stick reduce your entropy? It's not so surprising because if you have a mixed state, you look at the purification, which is an extension. You have low entropy. When you look at the purification, of course, in the end, you still have to mix up the state in the ensemble. So, it's not so clear how to play it. But in principle, you can. And so, um, it is known that I should say that the extension has a particular form which would be useful for you. You can think about it as taking the original state row X and then you purify it. So, I'll just call it the purification of row X, A, Q, A, A prime, A prime. And then you apply a channel from A prime time to A time. Then you get an extension. And all extension can be written in the form. So, the optimization offered extension can be thought of as optimizing this channel. And so, it is sufficient to communicate with this rate. You minimize over these channels, one for each X, the entropy of average extensions. So, this is clear. The professional. Unfortunately, we do not know because if you regularize, which means that you take the state row X1, row X2, through row XK, and then you take the extension of that thing. This thing lives on A1, A2, through AK with a single additional system F to extend them. Multiply it to PX1 through PXN. Sum over X1, XN. Look at the entropy of this new big ensemble over click up is with a single extension for each possible state. Divide by K. And then Min over this maps. Min over this. And sum these extensions. I'll say that way. And then take the limit K goes to infinity. This rate is necessary. So, we see the same thing. The distortion here is replacing the initial state by an extension. But it's only optimal if you consider potentially large blocks. Hey, it's okay individually or a priori. The extension is chosen a priori or at every level K individually. At every K individually, then you get the optimality. Yes. The good news is that I'm really done. So, so far, I described three optimal results for vanishing error. The natural question for this talk is, of course, if you allow finite error, you reduce the rate. The quick answer is that if you look at global error, you measure the error for the entire N block. This is if you, you look at this state or N of them. We believe that you cannot reduce the rate. It's heavily proved for pure states. There's a lot of main big progress for mixed states. It's what we call the strong converse. That says that if you reduce the rate a little bit, the error will converge to one exponentially in the plus size. If you consider is that per copy error. So, what it means is that at the output, the real output is actually some big state CN. You reduce to the first system B1, you reduce the second system B2, and so on and so forth. Then you come, you look at the state at X1, B1, and potentially the, um, the references. No, we don't look at the references. We have mixed it here. So, we have, no, you just X1 and B1 on here. You compare it with row X and A. That defines a local error. Take your favorite international. It can be trace distance. It can be one minus fidelity and so on. You look at that local error and you do it for every copy from one through N. Take the average. If you look at that average local error, then the answer is yes. You can reduce the rate by a certain amount. So, let me write down the, um, the error definition. And you want to keep this too. So, this is the error that we're looking at. Except you can be quite, um, general in choosing their function. These only need to be continuous. In it is also funny because I write it as if there are three inputs. This one is fixed. So, there's only one input to your function. If it is continuous in CPX, the other one I need is convex. And the last one is that it has to be, it has to vanish for Z equals to row. I actually need the last condition that your error has to be zero if you actually have done the right job. Otherwise, we can't, our optimization will not be feasible. And you won't be the problem. We need to add that condition there. So, with that, then we got the point. We saw before that, let me give credit to the people who have done this first. The previous day case has been first proposed by Howard Barnum in year 2000. And then there was a very, um, crucial result that goes before ours by the Angela data means winter in 2013 on the pure state case. And I won't repeat the result here because the expression looks really similar to ours. They are actually different, but it has the same form. It has the same theme. Um, so, let's see. Maybe the fun stuff first before the boring stuff. There is something actually fun. Um, so, this is the result with another and Dave. It's recorded. So, what happened was that we look at the problem without noticing what Karachi and the motor did. So, that was kind of funny. But we found, but the results are in conventional in some regard. Exactly. But because of that, we actually look into, uh, few distributions. So, these even these aren't even quantum states. These are diagonal decimations, two of them on D dimensions. What we find is that if the error, it's about 1 over D to the fourth, then I need the rate at least not the minus seven. B is supposed to be large. So, you can't compress much. If you take error, which is roughly 1 over D to the power gamma over two, gamma is supposed to be a small positive number. Take it as one percent. Then the rate is the protocol that we wrote down that will do it for roughly speaking, gamma log D bits. Um, we've studied the assisted settings. But this is an assisted. This is a system. So, to maximize the gap. So, if you tune your error as a function of the dimension, changing the power from four to gamma over two, change the rate from maximum to something that is a small as you wish. So, we really want to understand how it happens. And therefore, we were doing this, what is the social studies? So, then I'll write down the expression that we got. Just to tell you, in the end, I still do not know how that. So, what I want to know is the error as a function of the dimension. You can write down some POS like feasibility result. But I do not know the best trade-off. And you'll see why after I write down the expressions. So, by now, I think. So, the best rate assisted with error no bigger than this. We use the capitalized alphabet to emphasize that this is not small. It's Nim over something that I'll describe. Huh. The mutual information between C and X, X prime, R. This refers to the thing that I just erased. Initially, the state has an X and an A. And a J. A is purified by R. And X is purified by. We have the initial state psi X prime. Then take A and J. Run the channel over it. I'll put C and this is this data. Then take the state. Evaluate the machine information between C and X, X prime, R, divided by half. And that's the rate that you can achieve. If and it is. So, first of all, this is achievable because of condensate redistribution. Just Alice literally just performed this on every topic. Change the example if you're willing to. Then minimize over these channels. And from A J to C, you get the optimal rate. Now, this is a minimization that's constraint. You have to require that when you apply this map on row AJX is something that is close enough to I'll call AX. So, AJ goes and the channel N takes AJ to C. I should call this CX here. But it is a stated initiative defines the example. So, the error of this cannot be bigger than D. You have a constraint on what kind of distortion is allowed. The kind of nothing here cannot create too much local error. It should not create more error than you allowed. But you can go up to that era. And then from that point, once you minimize over that channel, to minimize the rate. And that is the optimal rate with the rate distortion theory. We recover that thing that we thought transmit the most boring method is optimal in this setting. I'm still slower than I thought. So, well, maybe I just verbally say some of the rest of the result that I want to show for the, this is the assisted case because we can do problem state with distribution without entanglement for free. We need to go through something similar to this. If it is visible, you have everything the same way, except you also allow the extension to suffer through a distortion. So, that when Bob discussed math, the average distortion of the K block, it's no bigger than the, if you do that, you, you do all that regularization, you get the optimal rate. You see, this is boring, right? It's almost. So, what I want to mention is that, so, what have we done? What, what did it take us so long to to finish this? Are there a lot of continuity problems when we try to prove that you can't do better than this? Here, I don't even show the optimization. I'll use this to explain where the problem is. If you look at this optimization, you think about it as a function of the, this function happened to be convex and continuous for the assisted case. So, then our proof will go through. What they understand the case, we can then define an optimization function that has a K in it. And then you take the limit of those functions to be the actual rate distortion function. So, there the continuity become a real pain to proof. They happen to be continuous after one or two pages and a couple of weeks. No, not quite a week crying over Rudy. And it can be proved. For distortion bigger than zero, if the distortion itself is zero, we can prove that for the special case when it is blind. We do not know what happened with general side information. So, if someone has a good idea or better skill between the analysis, we would like to know if we have continuity of the unassisted rate at zero distortion for general side information. This we do not. We actually say that in a comment in the paper that we have not been able to do that. It ought to be, but we can't prove it. So, then there we, after all these foreign, for example, we know that your redundant part of the ensemble does not affect your rate distortion function. So, even with the rate distortion theory going on, the redundant part does not appear in any of the rate. Which is reassuring. But it's not easy to prove without these expressions. So, we did that. The earlier work that I did not mention. So, I should say briefly. Look very similar. But then, there is no out because the states are pure and the error definition is a little different. They include X prime in the error definition. So, we do not know if those rates are the same as ours. It is possible because they have different error definition. You think if you use two different methods, just calculate the same thing, you should get the same result. But no, these are two different things that we're calculating. So, what else? So, um, with all this work, I try to make my student calculate this trade-off using the optimization there that's convex. They assist the one. So, I should say one other thing. This function is convex. The constraint is a reasonable one that you write right down. It's a convex optimization. So, the assisted rate distortion trade-off is retractable in principle. He did not give me an answer. So, I suppose it's not so easy. The unassisted one with the starter version of the head, promise me is useless. You have an expression. You may be able to prove something about it. But I don't think it is feasible to even compute much because it's not a tractable optimization for any sizable dimension. So, then I want to end with an open pop-up, like a general discussion of a problem that I think is kind of sit at the heart of what we cannot resolve in the end. So, suppose I have the same system. Will have set up. I have a list of states. I know that there is a channel M that approximately preserve all of them. Epsilon is not so small. What do we know about the triangle? This is not a boring question, but it is a very hard question. That's right. The way we prove this result is to choose the distribution so that we can know something about it. We choose that heavily constrained the channel. You do exponential cardiology. It has to be close to identity, right? I mean, the standard perturbation argument. This is not vanishing. Yeah, but for fixed epsilon, I mean, less than one, I guess, right? The, the rich part is to let the, the error if someone depends on the dimension. But that still, I mean, if, if the class of the raw eyes is somehow unit a net somewhere, then you can say something. That's right. But if not, then it's, I think they even analysis problems. There are three more questions possible to answer. I sound like bad news. But yes, I think, um, just back to this example. Food distribution on D dimension. It's not a particularly complex set of state. Just two distribution on D dimension. We still do not know what happened here. Um, I mean, these are two, two nice things that we manage on the paper. Yeah. If anyone has has a student who want to think about, well, actually, yeah, I, I start here.