Memory Compression with Quantum Random-Access Gates (Subhasree Patro)

Hello everyone. I am Subhashri Patra. Sorry about the delay today. I'm going to speak about memory compression using random access gates. This is a joint work with Harry Goodman, Floyence Payman. Come here and then you catch. No, no, this is a result that we got while working on some other problem, actually. So, it's not a very big result, but it's a cute result. Uh, let me start now.

[Music]

I don't know. [Music] Everything that I said in this cycle, memory compression using random access gate. But, uh, before I explain anything in that, I want to first describe the computational model on which we will be looking, uh, to compress things. And after that, I'll be talking about what are sparse algorithms in the computation model. And then I will be discussing some data structures. Uh, for people who are not familiar with quantum things here, don't worry. We have a lot of classical things going on in this. And then we will combine everything to make this technique, this compression technique, using these data structures. And in the end, we will discuss some applications on how to like, why this technique can be used and how it will be used. Okay.

Yeah, the model of computation for us is, uh, one of the definitions of quantum random access machine model, and it's a circuit model which looks like this. So, imagine we have these, uh, yeah, we have some work qubits on the top. Then we have some memory qubits in the bottom. Like, these are all wires. Now, we have single-qubit or double-qubit unitaries on this work qubits. We have oracle access for the input on these work qubits. But whenever you want to access any of these memory qubits, you can only do by using something called a random access gate, which allows you to index into any of these memory qubits in one step of this game. Okay.

But implementing this gate is not going to be simple because it is going to require N order N gates, like elementary gates. But the reason we can assume this is because in a classical setting also, when we assume a random access machine model, we do a similar assumption, like we can access any memory in one step. And this is what the assumption we are doing in the quantum world. Okay.

Now, how the RAG gate looks like is something like this. It just takes this index I and another qubit B, and it will swap the excited qubit with this B qubit. Okay. So, once you use this RAG gate, what you are doing essentially is you are taking this particular if qubit, you are swapping with some ancilla here, and then whatever operation you want to do, you do, and then you can swap it back. Okay. So, this is, this is how the computational model is.

Now, what would the sparse algorithm in this computation model look like? So, the, don't worry about the text and explain everything now. We saw this model QRAM, random access model. Now, we define a circuit here as a tuple. So, imagine you have this input length as N, you have T, you have W that is work qubits, and M memory qubits, and C one to [Music] ordering of these bits in the circuit. And for, um, whenever you have, uh, um, yeah, and I'm gonna count every single gate as one operation in this model.

Now, when we say some algorithm is M-sparse, if at any time step, the state of the algorithm is only supported by, you know, states whose Hamming weight, like the Hamming weight of these states is bounded by some small M. Okay. This is what we define to be an M-sparse algorithm. And we are going to now present techniques that can compress. Because now, if I have my memory qubits as large M, and I know that my state is never going to have any any memory state which is larger than this small M, then maybe there are procedures to not use capital M qubits, but actually use a smaller amount of qubits. So, this is what we are going to discuss on how to compress these algorithms. And I will also show you that these kind of M-sparse algorithms actually exist. Like, which like are very easy to, uh, think of. So, it's not something that we just made up on the go. Like, uh, I will, I will give you evidence of this.

Any questions to know? Yeah, but so what do, can you tell us nutrition-wise, is the good notion of sparseness? Okay. So, in the classical setting also, like, so sometimes when we have these query algorithms and we want to make them time-efficient also, we use interesting data structures to store, uh, the input in such a way that, you know, you can access them efficiently. Now, what happens? Even in the classical setting, you can sometimes use very interesting data structures, but for one algorithm, you're not going to use all the memory space. Okay. And we have some like hashing techniques in the classical setting where you can compress those averages. So, it is like very natural to think what we can do in the quantum setting in this case. And this is why we explored this.

Yeah, is there any restriction and W can be larger than the small M or whatever? Uh, usually W using like log. Yeah, the size of the W is order log capital M, not not too much. And for most of the algorithms that we look at, my the size of this M is going to be actually polynomial in grid line, which is the input size. So, W is not going to be more than order log or polylog N. Okay. So, any other questions? You know, now.

Okay. Um, now we saw that in our sparse algorithms, we have our states on vectors whose Hamming weight was bounded by some small M. Okay. Now, if I give you a task that we have some vector which has, you know, a lot of sparsity in it, that means it has a lot of zero entries and has like values. Now, instead of using this capital M memory size to denote that vector, obviously we would like to think of more succinct representations for that vector. Right? One simple way would be that, okay, don't, don't store the entire string which is of M bits, but just store the indices that have that one. And when we have very few of these indices, then we might have like actually much lesser memory usage. Right? So, for example, when we have like, you know, um, this small M is actually less than M by log M itself, we already have an improvement because you can just use those bits to store this. Okay.

But now the challenge is, see, suppose I have this, this set S_v corresponding to this v, but I have to have a unique representation for S_v, right? Because if I, if I want to have a quantum state which is S_v, which is like corresponding to v, and if any algorithm that works on that state v has to have something analogous, and if we want the amplitude and the interference to matter, then we want this S_v also to have a unique representation. Okay. But there will be some other restrictions that people need because of the compression technique, which I will slowly explore.

So, now, uh, the broad idea is to represent this state v instead of this, uh, sorry, represent the state as S_v instead of the state v. But now, another challenge is, we have to ensure that every instruction, the every gate that I had applied in my original M-sparse algorithm has an analogous implementation in my new compressed algorithm, otherwise I'm, I'm not giving you a compressed algorithm, right? So, yeah, first thing that we need is that we need the representation to be unique. Then, oh, yeah, another thing, we also need the present representation to be history-independent. I will get to that. History independence is nothing but when you create the set S and, uh, the data structure, you cannot differentiate. By looking at the elements in the data structure, you should not be able to tell what is the last element added. So, the data structure should be like, should mask out all the history information. And, yeah, like I said, now for every instruction in this original algorithm, we would like that there is an efficient analogous operation C-dash_i in my new algorithm. Only then I will have a nice analogous sparse algorithm. And to this, like, to actually give this compression technique, we use a lot of data structures as building blocks, which I will now slowly get into. Okay.

Yeah, the first data structure that we're going to look at is something called a radix tree. Now, radix, like, again, don't get boggled by the text here. I'm going to explain clearly. Now, a radix tree is a rooted binary tree. And, uh, like, let me directly jump to the example here. So, yes, now look at this, uh, set where we have these four elements that we want to store in this data structure. We have, what we do is, whenever you want to say, create a radix tree pertaining to the set S, you first find the longest prefix to all the strings. Whatever the longest prefix would be. Suppose they don't have a common prefix, it is possible that they don't have a common prefix. Then you bifurcate into the sets which have a common prefix and which do not. Like, say, in this case, we have, uh, one string starting with zero and all the other strings start with one. So, we clearly know that one of them has to be bifurcated by the other from the root node. Okay. So, zero. But again, you repeat the process. Now, you have, uh, these three strings and you have one here. And then, like, you keep doing this. Okay.

Now, so this, this data structure has some very interesting properties. Now, imagine you want to add a new element, which is also of like four bits, right? The maximum, like, checkings you are going to do is going to be of four bits. So, if you are storing numbers from between one to some capital N, then at most you will be doing log N operations to store that index, to find the position of where that element has to go. Same thing is with deletion, and same thing is also with lookup. And these are the three operations that we actually are going to care for.

But now, what about the storage of this data structure? How do we store this data structure in the memory? So, see, one thing is clear, for any set S, my radix tree corresponding to that set S is going to be unique. Because if I, if I tell you that, okay, the first, the right or the left side has to be always with a zero and the right child always has to be with one, then you can see that for any set S, I will always have a unique random string that represents that set S. But what is still not guaranteed is how is this radix tree going to be represented in the memory of my computer? Right? Ultimately, what is going to happen in the classical circuit is, we care about the memory location on where these nodes and these cells go. So, we still have a challenge. We still don't have a unique memory representation of the radix tree on the computer.

So, then we, uh, like explore on the literature of what exists here. And let me say that, okay, now suppose you have this radix tree and you have M leaves on this radix tree, or you have the set S, which you know that is going to be at most M size, then the radix tree will have at most M leaves. Because all the elements in the set has to be leaves in your radix tree. Now, because this is a binary tree, and it is, it need not be a complete binary tree, but it is a binary tree, so the total number of nodes that you will end up in this radix tree is going to be at most 2M. Right? Because you will have M leaves and, like, you know, two, two can be paired for one parent and so on, but you are not going to have more than 2M nodes. So, you can represent this large radix tree by an array of size 2M blocks. Okay.

Now, for every node here, what you will have, yeah, is two children at most and one parent. And by just that information and the label, the the value on this edges, the label on the edges, you can give it every node. And so, with an array of size 2M blocks, you can represent a radix tree. Now, uh, so you can think of this radix tree as a binary string of this quantity, which is just basically number of blocks and the size required for each block.

Now, what, uh, we could now think of the memory representation is, now you can imagine an injective function that takes any of these blocks of radix tree and puts it in one of these empty blocks in the array. Now, that will be one particular memory representation for the radix tree. But there could be several. It's possible that, you know, the root, and what I'm going to fix is just that the root node is always going to be at position one, otherwise we will not know how to traverse the tree. Right?

Now, the, uh, like with the more, uh, exploration of literature, we stumbled upon something called quantum radix tree. And this was in Stacy Jeffrey's PhD thesis, and it was first introduced by Bernstein, Jeffrey, and John Morris in 2013. And what the, the cool idea was, now, yes, it is a challenge to have a unique representation of the memory and of the radix tree. So, what we can instead do is, we have a superposition of all possible memory representations. So, if you have this injective function, you just take a normalized state of all possible, you know, this, uh, injected representation of this radix tree. And, but it is still not done because how do you, how do you do any of these data structure operations quickly if you have such a uniform superposition? And that is not very obvious. So, for that, we had to then, uh, think of something. Though it was answered in Stacy's thesis, it wasn't completely clear. So, we gave an alternate way of doing this, of how to efficiently have a query, query of operations that are efficient on this quantum radix tree.

But before I go that, we have to now talk about some other data structure operation that's called a prefix sum tree, which we extensively use. Now, this prefix sum tree is a little easier data structure. It is now a complete binary tree with each leaf node labeled by an array of zero or one. Okay. And what we are going to track is the number of leaf nodes that have descended from any node. I will explain with the figure. So, now, suppose I want to store elements between one to N. Right? Now, one bad way of doing of storing this one element, yes, have in my memory of the computer, have specific locations, you know, reserved for element one, two, that is doable, right? And that would take a lot of memory, like this L size. Okay.

And if you have an element, say, say your set contains an element three, then you can toggle this bit to be one. Okay. And then all its corresponding parents will have, we will update the value of these counts by plus one. So, what the root ends up containing in this tree is how many children I have which are one. So, that way, I can efficiently. Okay, thanks. So, I can much do this loop operation in log N depth. See, otherwise, imagine I just had this array, I just had this array at the bottom, which, like, whenever I had to insert an element, I just toggle that element to one. Now, the problem with that is, I cannot find the Kth one element. I can, I cannot find or say whether the element exists or not with, sorry, element exists or not, I can find quickly. But if I want to find the Kth one element, I can't do it fast. But by having this prefix tree above it, I can have easy access because, see, if the count is say 10, and I want to find the seventh one, then I don't have to go on this side. I will just go on the set, and every time I'm halving the space by every level. So, in log N operations, I can just look up. I can do this insert because insert, you just toggle this and update all the parent nodes. Delete also, you do the same thing, right?

So, using this prefix tree, uh, okay, let's recap the memory again. I know it's, it's like a lot of data structures that we have done. What are we trying to do? We are trying to have a quantum radix tree, which is a radix tree over all possible memory allocations to that radix tree. Right? It's a classical data structure, but we are going to have all possible memory allocations. Now, we will now use this prefix tree as a tense, as another state with this quantum radix tree, so that that can keep track of what are all the empty cells that are left. So, whenever we want to insert something, we can actually traverse through the prefix tree, find an empty spot there, create a uniform superposition for the empty spots, and then put the element there. That is, that is the idea here. And our injective map is going to be just the same injective map, but it is going to be a complement of, basically, we are going to have the set F as the set which contains the elements, the spaces that are free, instead of what are full.

Okay. To redefine this quantum radix tree, it is exactly the same. It is just that we have this radix tree, which is a classical data structure, and we have inserted it with this prefix tree that contains the value of all the cells that are empty. So, that whenever I need to insert something, by, I just have to insert it here by finding what are the free positions from this prefix tree. That is the idea.

But now, how is that going to help? Now, okay, we discussed that any, any operation, any operations of our desire, that is insertion, deletion, or lookup, takes above order log M. In the station, it takes about the same order log M in this prefix tree also. So, in this much time, we are able to actually insert anything we want in order log M, because by linearity, we can make this argument. So, so lookup, lookup operation is nothing but you want to know if there is an element in the set S. And the, the, the thing like the unity that we would like is, it takes some element E, it takes our quantum radix tree, it takes another ancilla, and on the ancilla, it just toggles the bit if the element is present, and otherwise doesn't do anything if the element is not present.

Now, this toggle operation, ah, now this is just a technical part to it. Like, in classical computation, we don't care about reversibility. Right? So, if I give you a state S and I say, okay, insert E to S, now the classical operation is still going to go through, even if E was already present in S. But we have to be careful here when we look at quantum ones, because what happens, like, what is insert operation in quantum checking? What if the E is already present? So, we define another kind of operation, just that is the toggle, which says if E is already present, then remove it. If E is not present, then add it. This is what the toggle operation does. Okay.

Now, the third operation that we want to implement is a swap operation. Now, this is tailor-made to our requirement because what we want is, um, okay, now we started all this thing as a process to compress these M-sparse algorithms. Okay. They were, and the RAG gates were the only gates that were actually accessing the wires from one to N. Everything else was only on the work qubits. Right? So, now, if I'm having a compressed algorithm and I'm saying that my new algorithm is not going to use that many wires, I need some operation equivalent to RAG that I can do on this new algorithm. This is the swap operation that we actually use as, like, instead of this RAG operation. And interestingly, we can implement this use of operation by this U_swap, C_toggle, and U_lookup, which C_toggle is nothing but just conditional on a particular value. So, this entire thing can be again done in order log N time because, uh, each of these operations just take for a long time.

So, and, yeah, then I will discuss the simulation process. Here, what we do is, again, we are back to the original model where we have, see the circuit as from C1 to CT, and it is computing some relation F. Now, for, we want to construct a new compressed circuit which does the same, like, which evaluates the same function, but the time is not too much blown up, and the space constraint is much lesser. This is the requirement that we want. So, for every instruction here which is not a RAG gate, we just do the same thing in this circuit. Okay. Which means the number of work qubits is going to be at least this much for us.

Now, for, oh, and so that's the easy part. For the next part, yeah, for each of these instruction that was indeed a RAG gate, we have shown that we can actually use the U_swap operation, and that we will do, uh, instead of the RAG gates. Okay. In this way, what we have done is, we start with an all-zero state, right? In both of the settings, we start with an all-zero state. For every state here, we have an isomorphism to a state here, and the functionality is still going to be the same at every step. So, we end up getting a new circuit which uses much less memory because now this M-dash is going to be just the size of this quantum radix tree, which is not going to, which is not, which is going to be just M log M instead of capital M. And the, this additional W-dash that comes is because of this RAG operation. We need sometimes ancilla to, you know, do an operation, reversibly. So, it is to account for that that we use this.

And to informally state the theorem, if you have any M-sparse quantum algorithm that uses time T and M qubits, we can simulate that in almost the same time using M log M qubits, which is a big improvement when we look at where M is polynomial in N. And, like, yes, the reason all this even came up for us is because of the applications that I'm going to discuss now.

I'm not going to discuss all the applications, but I'm going to discuss one of them, which has the same flavor for all the rest. So, we can use our these main theorem to simplify actually presentation of three results. That is, like, combining quantum work algorithm for solving element distinctness. It is another one is Aaron Sun et al. quantum algorithm for closest pair problem. And third one is, uh, actually our own paper, which gave, you know, which led to this result, actually on finding complexity via quantum walk. Let me get into the detail of how this can be this technique can be actually applied.

Now, Aminus, like in 2004, gave an interesting quantum work algorithm for solving this K-element distinctness problem for this K, N. It is a simple problem. We have a list of N integers in some domain, and all we want to know is there are K elements that are equal. That is, that is the problem. Now, this, um, this algorithm has, like, the Aminus gave this algorithm has a quantum query complexity of this order, and our K5. And he also gave a method to make this query algorithm time-efficient. And to do that, he used some very complicated data structures that are based on hash tables and skiplists, and which is also like not error-free. It uses some family of hash functions that induces N. So, now, but we, we noticed that we could actually solve this, this K-element distinctness problem in much simpler data structures, but by blowing out the size horribly.

Let me look at the data structure. Now, okay, one of the assumptions that these algorithms allow you to make is that all the inputs to your K-element distinctness problem are bound, are in some N power P range of polynomial. So, imagine you have this prefix tree data structure again. Now, in this data structure, you, whenever you have an input X_i, which is, uh, like your input to the K-element distinctness problem, you go to that particular cell X_i, you just toggle that one. And corresponding to that, you have like another bit vector that just checks what was the index this X_i came from. Because remember, in element distinctness, you're going to check if there are K indices that have the same value. So, if any of my blocks like this have K ones in it, then I'm done. Then I know that, okay, I have a solution to this element distinctness problem.

So, now, how do you, how do you ensure that the solution is reflected on the root node? You, like, the moment this count of any of this value becomes at least K, this flag becomes one, and the parent, and if a child flag is one, then the parent flag becomes one, and you go on up to the root node. So, in log N steps, you can actually [Music] like, you know, insert an element or delete an element or see if an element exists. And by just looking at the flag value on this root node, you can see if you have a solution to your K-element distinctness problem or not. But now, this doesn't have error. This is a, what is a unique representation of a set? It has history-independent property. It has all these properties that this, uh, Aminus data structure is required for the algorithm to work. But the sad part is, it uses a lot of memory. Right? We are using like N^3 memory here, that is under the promise that my inputs come from minus N^3 to N^3. We are ending up using another additional N memory here. So, in total, we are using N^4 memory, which is not desirable, given that we can't even make, you know, 70 qubits stable. Right?

So, then, yeah, clearly we can use this, uh, walk algorithm. So, what we propose is, yes, think of these data structures, think of an algorithm, and then use our theorem as a black box to simplify this algorithm into a compressed form. And, um, so Aminus walk algorithm actually stores this set as, like, it's stores these R-size sets in these data structures. So, we now know that, oh, using Aminus algorithms on this data structure, we will create a new algorithm which is very bad on the memory, but is guaranteed to be R-sparse. And then you use the theorem in a black box way, and you conclude this result. So, this also shows that the same algorithm, same complexity, we have another simpler algorithm to conclude. We also do this for some other problem, this called closest pair problem, which has a similar flavor. It also uses quantum walk, uses some smart data structure, but we use again prefix sum tree data structure smartly. Like, they are smart techniques, but our prefix tree, and we combine this thing.

And we do the same thing for our on paper on fiber and complexity. So, yeah, to conclude, theorem can be used in this black box way to simplify presentation of several papers. We are still looking for candidates that we can help solve, you know, upfront, not like, you know, simplify any result, but actually solve something new. Um, broadly speaking, if we have a space-efficient, like, uh, okay, we can always construct a space-inefficient algorithm using these prefix tree kind of thing and use our black box theorem to specify them to compress.

Um, yeah, this work will appear in the proceedings of DQC this year. And, uh, to access the full paper, you can just check out arXiv from this number. Okay. Thank you for your attention.

Yeah, there's this notion of the compressed our technique like for the quantum renova. Have you seen it somehow? Yeah, this type of Zander things have you seen if your technique can improve something there? No, I, like, I know that it worked on some random hash functions. So, we also know that, like, we can use same this classical family of hash functions and also do that, but that is going to induce error. But this technique doesn't induce errors because of the hashing thing. But there is another, uh, reason why there will be little error, that is, like, whenever you're creating this radix tree, right, and you're having this prefix sum tree to insert any new element, you first need to know what all places are empty in the prefix tree, so that you can insert in that in superposition. And for that, you need to create uniform superposition of one to K for any K, and there you will have a little error because we don't know their cases.

In our case, uh, in our case, yeah, in their case, they don't need to do this uniform supervision thing, but they have to use hashing techniques because otherwise, how are you going to compress? But the question is, can you use your data structure to improve their, like, the compressor oracle, to have faster or, I don't know. I haven't tried that thing yet. I didn't look. [Music] But if there's no time complexity, why do we need to compress it to start with? Like, the others, something that you want to tell myself. You can speak about this paper. Yeah, there is no compression at all. So, that more framework, but is not, in fact, if you don't care about time complexity, you, so if you have something efficient, sometimes you want to simulate it, right? And for the simulation, you need. But I'm not sure we can see it offline. Okay. I will have to check. I, I don't know if it improves their thing a lot. More questions.

What is this closest pair problem? Oh, so the closest pair problem is a computational geometry problem. You have a list of N points and, um, in some dimension RD, and you want to know the, like, you want to output the pair that is closest to each other. Distance? Yes, I think it can, like, you can define this in under any distance measure, but we usually, we care about the Euclidean distance. So, for, um, [Music] for this problem, with, uh, yeah, so the algorithm that we give is a constant dimension case, and you can actually use quantum walk algorithm again, and, like, in the same way that you do for element distinctness or three-sum or any of these problems, and you can get a query algorithm for N power two by three. So, so what are you querying here? Where the point is like a binary description? Yeah. So, yeah, yeah, you can, like, because you have limited space anyway to store your point, you can discretize it. You can just imagine that they are in some LD. Yeah, you basically query the point. What is the value of this point? Yeah. To make the algorithm time-efficient, we could again use prefix tree. So, for.

Like, there's something else that is there in the paper. I can always, yeah. And so, what is the time to look at also? Also, but this was already proven. We just simplified it. [Music] So, okay, so I have probably two questions. So, first, I'm very happy you did this work because now I can use it as much like, but it was always a mess for time efficiency. [Music] And coming back to, uh, at some point, you compared to the work of several people in 2017, 2017, yes, Stacy and yourself. Yeah. So, I'm just going to just, what is the difference? So, they have a solution which was not good enough for some reason. No, so, so, um, okay, the quantum radix tree idea was from Stacy, the 2013 thing. So, they actually talk about this classical radix tree, but using over all these memory representations, exactly what we defined. But what they don't clearly talk about is how are you going to do any of these data structure operations on the, yeah, like, they, they gloss over it, but they don't actually, uh, define things properly. So, we just clean. Yeah.

So, it looks like, uh, imagine for some reason my memory is classical. Yeah. And I have a quantum algorithm that accesses to a classical memory. The memory is always classical. Yeah. It looks like somehow you quantize it because you need these things. So, I don't know how much interesting in this. But you're not sure of what interesting is. My question is such as, do you really need to contact me? Is there a noble seal? Then if you don't contact us. Yeah, we need to see the whole. I see why you need it. Assuming again, the memory is classical. Classically, of course, you don't quantize. But then you have a memory which is history, it's not unique, depends on the history. And see, the thing, can you ask more than what you need? So, maybe if I understand your question correctly, uh, in classical algorithms, we don't need this memory representation to be unique. Yeah, because we don't have this concept of interference. Like, see, basically, what happens is, in the quantum algorithms, whenever the resultant state goes to the same set S, we want the amplitude to connect or interference to happen. Now, in the classical setting, we don't have that concept. Assume that when the memory is classical, yeah, that's a controller. But the algorithm is controlled. Oh, no, yeah. Okay. Because there's a small register that can, the workspace can be confirmed. Okay.

So, one question. [Music] Assume that the memory, what you do here is classical for some reason. How do you, why can, what if you're entangled to this register? How do you address that? I don't know. No, I mean, for some, okay, smart questions. So, it's, and then if you apply your technique here, then the memory becomes quantum because you need to do the superposition over all. Just for a fixed element in the quotation basis, as far as understanding, for that one, they need a superposition. And on top of that, you have the logical gate, right? The logical state. Yes. His point was that, you know, usually when you have a classical memory, you can just take all the reads that you needed at first and then use it. But that takes memory, you know. And then somehow you don't want to use this quantum memory for nothing during the whole computation. So, you have these classical memories at your disposal. And then maybe your question is that, yeah, if you have just this classical memory and you want to take reads at it at some points, but you know, not store it in a quantum way because you have limited memory. Is this kind of, is this kind of approach feasible? But so, I try to make sense again. I want to remove this superposition of all the possible. I try to make sense of this. So, you know, you can imagine, you know, this notion of a quantum classical hub. So, this is basically this. Let's say you have a big hub, which is basically a big data, and you have your algorithm working with this hub. So, maybe sometimes you update your hub, whatever it doesn't make sense. It's possible. But just try to understand mathematically. There is a way to remove the superposition of all possible. I don't know. Maybe it doesn't make sense. I don't know.

I think there's one restriction that you can have an algorithm which is that you just read out of the memory. So, you never toggle a bit depending on, you know, your state of the column circuit. And then in some sense, you are always in a product state with with the memory. And the memory can, and then I don't think that you're just swapping of history because you're always in a product state. That's cool. That's cool. Somehow, if you're ready to do a partial measurements or stuff like that, you could also write stuff in the memory at some point, you know, if you are in some very special state, then you make this kind of partial measurement. Yes. So, with this kind of stuff, maybe you, you can have a classical memory and talk to it with read and write during your whole computation, you know, which are very limited summary. So, this kind of setting like is actually useful. But I, I, I don't see how this approach relates to that because because actually this approach is all like the whole point is to make a quantum memory go into a smaller quantum one. So, maybe just the classical approach. [Music]

I understand. You know, in your time complexity in the end, you say it goes from T to equal to T. But in fact, it's only the, uh, the RAG operations, but that is building. So, like, if you, if you take the time, the time complexity is something like T plus A, where T are the operations of the normal, and A of the axis. It's just T plus, uh, A log A, in fact, or no, A log of something. Yeah. The problem is this, uh, simulation of this RAG operation, the you swap that we interchange it with that also uses RAGs in its, uh, click working. So, what do you mean, like, in your simulations, not just we replace RAG by swap? Yeah, it does. So, yes, I replace RAG by swap. Yeah. But the complexity of this U_swap, yeah, which has like, oh, till like all, uh, order M log, uh, M operations, sorry, order that is counting the RAG operations in that also. Oh, yeah. So, so, yeah, so you're making more RAG operations. Yeah. My mind was just that, you know, it's not exactly a log N increase over the whole stuff. It's just a very local logarithmically. So, yeah, yeah, yeah. Very easy. Very often, it's actually even more efficient that what we could think when looking at the simulation. Like, uh, yes, yes. Actually, like, you're right, it comes more as an additive term on the number of RAG gates that we, uh, use rather than on a product on the outside.