quantum computing talk by Andreas, who gave a talk exactly five years ago, and it's almost exactly five years ago. It's like one year and two or three hours. And he gave a talk at 31C3 about quantum computing titled, Let's Build a Quantum Computer. And I think back then we basically had just found out that Google was planning to partner with the University of California in Santa Barbara to try to build a quantum computer. Of course, now we're five years later. We've had a lot of developments, I think, in the field. We've had some big announcements by Google and other groups. And Andreas has now come back to give us an update. So please welcome him to the stage. Okay. Hi, everyone. So I'm very happy to be here again after five years of giving the first version of this talk. My motivation for giving this talk is quite simple. I was often, so I did my PhD on experimental quantum computing from 2009 to 2012. I left that field afterwards to work in industry. But always people would come to me and would ask, hey, Andreas, did you see this new experiment there? Did you see you can use quantum computers on Amazon's cloud now? Did you see Google has this new quantum thing? Is this really working? Can we use quantum computers yet? Why are you not working on this? And I couldn't really answer the question. So that's why I said, okay, I want to go back to this and find out what happened in the last five years since I finished my PhD, what kind of progress was made in the field, and do we actually have quantum computers today that are working already or are we not yet quite just there? So we want to do it like this. I want to first give you a short introduction to quantum computing, so just that we have a common understanding of how that works and why it's interesting. Then I will show you a small example of experimental quantum speedup, notably the work I did with my colleagues in Saclay during my PhD thesis. Then we will discuss some of the challenges and problems, why we were not able to build a real quantum computer back then, and I will discuss some approaches that have come up since then that would basically allow us to do that eventually. And then we will of course discuss Google's recent experiment in collaboration with the University of Santa Barbara where they showed basically a very impressive quantum computing system with 53 qubits. We will look exactly, try to understand what they did there and see if that's really like a quantum computer in the real sense already or if there's still something missing. And in the end, of course, I will try to give you another small outlook to see what we can expect in the coming years. So in order to talk about quantum computing, we need to first talk about classical computing, just a little bit. You might know that classical computers, they work with bits, so zeros and ones. They store them in so-called registers. This here, for example, is an example of like a bit register. Of course, the bits themselves, they're not very interesting, but we have to do stuff with them so we can compute functions over those bit registers. That's what like a modern CPU is doing in a simplified way, of course. So we take some input bit register values, we compute some function over them, and then we get an output value. So a very simple example would be a search problem. I will discuss this because later we will also see in the experiment how we can use a quantum computer to solve this. So I just want to motivate why this kind of problem can be interesting. And it's a very silly search function so it takes two bits as inputs, and it returns one bit as an output indicating whether the input bits are the solution to our search problem or not. And you could imagine that we have a very, very complicated function here. So, for example, a function that calculates the answer to life, the universe, and everything. Well, not a complete answer, but only the first two bits. So really complicated to implement and very costly to execute. So we might think that it might take like millions of years to run this function once on our inputs. So we want to find the right solution to that function with as few function calls as possible, of course. Overall, there are four possibilities. So four input states, zero, zero, one, one, zero, and one, one that we can apply our function to. And only for one of these states, the zero, one state because the answer is 42. So that's zero times one plus two plus some other stuff. So the first two bits are zero, one. For this value, the function returns a one. For all of the other values, the function returns a zero. Now, let's think about how we can implement a simple search function. And in principle, if we don't know anything about the function, so we can imagine it's so complicated that we can't do any optimizations. We don't know where to look. So we have to really try each of these values in sequence. And for this, we can have a simple algorithm. So we can start initializing our bit register with zero, zero value. Then we can call the function on that register. We can see what the result is. In this case, the result would be zero. If the result would be one, then we know, okay, we have found our solution. So we can stop our algorithm. But in this case, the result is zero. So we can just go back to the left value and to the left step and increase the register value to go to zero, one, and try again. And in the worst case, depending if you're optimistic or not, we have to do this three or four times. So if you want to really be sure that we find the right answers, we have to do it four times in the worst case. And this is, so to say, the time complexity or the computational complexity of the search. If you imagine that in our algorithm, the most expensive operation is really calling this function F, then the calling time or the complexity of calling this function will be what dominates the complexity of our algorithm. And in this case, the complexity is very similar, simple here, because it's linear in the number of the search space. So if you have n states, for example, in our examples, we have four different input states, we also need to evaluate the function four times. And please keep this graph in mind, because we're going to revisit that later a bit to see if we can do better with a different paradigm of computing. And so, classically, this is really the best we can do for the search problem here because we don't know anything else about the function that would allow us to optimize that further. But now the interesting thing is that we might imagine that we don't use classical computing for solving our problem. And in fact, the discipline that we call quantum computing was kind of like inspired by a lecture or like a seminar of Richard Feynman, who thought about how it would be possible to similar and or if it would be possible to simulate quantum systems on a classical computer, a Turing machine, if you want. And he found that because quantum mechanics is so complicated for classical computers that it's not possible to do that efficiently, but that if you would use the laws of quantum mechanics themselves to make a computer, like a quantum computer, then it would be possible to simulate this quantum systems. And this kind of like sparked this whole idea of using quantum mechanics to do computation. And in the following years, they were not only solutions found for simulating quantum systems, which such a quantum computer, but also for solving other not related problems to quantum computing. So like search problems or factorization problems, for example. And quantum computers can do can do computation faster than classical computers because they have several differences in how they work. So one of the key differences here is superposition, which means that if you use a quantum computer instead of a classical computer, we cannot only load a single register value into our bit register. So for example, the first value there with only zeros, but instead we can kind of load all of the possible state values at once. So in parallel. And this is so called quantum state or quantum superposition state where each of these values here has an amplitude which is shown on the left. That is basically a complex number that relates them to the other states. And if you have like, for example, n qubits, then the total number of qubit states can be very large to the power of n. So you can imagine that if you have a large qubit quantum bit register, then your number of quantum states can be really, really large. And this can be very powerful for computation. So in the rest of the talk, we're going to just indicate this by like showing the register as like a small rectangle to indicate that it's not only a single value in there, but that we have a superposition values of all the possible input values to our function, for example. And there's a condition and so called normalization condition that puts some constraints on these amplitudes because the sum of the squares of the absolute values of these amplitudes needs to sum to one, which basically means that the entire the probability of each of all of these states together needs to be 100%. And this is the first ingredient that makes quantum computers interesting for computation because we can basically implement any classical function that we can also run on a classical computer on a quantum computer. The difference is that we cannot only run it for one value at a time, but we can run it then on a superposition of all possible input values. So if you want, you have like this massive parallelization where you run your computation on all possible inputs at once and also calculate then all of the possible output values. And that sounds of course very cool, very useful. There's a catch that we will discuss later. So it's not as easy as that, but this is one step off like the power that makes quantum computing interesting. The next thing that is different is that we can on a quantum computer not only run classical functions, but we can also run so-called quantum gates. And the quantum gates, they're different in respect to the classical functions because they cannot only like classical operations like and or act on like two qubits in a predictable way, but they can kind of like act on the whole qubit state at once and also create so-called entangled states, which are really weird quantum states where we can't really separate the state of one qubit from the state of other qubits. So it's kind of like if we want to try to make a small change to one of the qubits in our system, we're also changing other qubits there. So we can never like separate the bits, the qubits out like we can with a classical computer. And this is another resource that we can use in quantum computing to solve certain problems faster than we could with a classical computer. And now the catch, as I said, is that we of course do not we do not want to only make a computation with our qubits, with our qubit register, but we also want to read out the result of our computation. And if we try that, so we make like a computation and we want to measure the state of our quantum register, we have a small problem because, well, the measurement process is actually quite complicated, but in a very simplified way, you can just imagine that God is trying some dice here. And then if we have a quantum vector, a quantum state vector that has like these amplitudes on the left, so a one to a n, then we will pick he or she will pick a state randomly from the possible states and the probability of getting a given state as a result is proportional, as I said before, to the square of the absolute value of the amplitude. So that means we can perform computation on all of the possible input states of our function. But when we read out the result, we will only get one of the possible results. So, and this kind of like destroys at the first glimpse, the utility of quantum computing, because we can do like computation on all states in parallel, but we cannot read out the result. So not a very interesting computer because we can't learn about the output, so to say, or not easily at least. But it turns out that there's actually a way of still using quantum computing to be faster than a classical computer. And the first kind of practical algorithm for a search problem, notably the search problem that we discussed before, was given by Love Grover, who was a researcher at the who's a researcher at the Bell Labs, and who found the Grover algorithm that's named after him, that's basically a search algorithm which can, as we will see, solve the search problem that we have in a much more efficient way than any classical computer could. And in my opinion, it's still one of the most beautiful quantum algorithms because it's very simple, and it's very powerful. And there's also a proof, unlike for other algorithms, like the factorization algorithms from shore, that the Grover algorithm will be faster always than any classical algorithm. So in my opinion, it's a very nice example of really a quantum algorithm that is more powerful than a classical one. Let's see how it works. So there are three steps again in the algorithm. First, we initialize our qubit register, our state vector to a superposition of the four possible output values, so 0, 0, 0, 1, 1, 0, and 1, 0 again, all with equal probability in this case here, or amplitude. Then we evaluate the function on this input state here, and what the function then does. So we made some special encoding here that basically marks the solution of our problem by changing the sign of the amplitude of the corresponding state. So we can see that in the output state here, the 0, 1 state has a sign which is negative, which means that it's the solution of the problem that we search. Still, if you would do the read out now directly, we wouldn't be able to learn anything about the solution because as you can see, the amplitude is still equal for all of the four states. So if you would make a read out now, we would only get like one of the four possible states at random. So we wouldn't learn anything with 100% probability about the solution of our problem. In order to do that, we need to apply another step to so-called Grover or diffusion operator, which now takes this phase difference or the sign difference between these individual quantum states and applies a quantum operator to that that basically transfers the amplitude from all of the states that are not a solution to our problem to the state that is the solution. And for this case with two qubits here, with four possible values, there's only one step we need. And after executing that, you can see that now the amplitude of our solution state is 1, but the amplitude of the other states is all 0. So that's great because now we can just do a qubit measurement and then we will 100% probability find the solution to our search problem. And that's where kind of like the magic of quantum mechanics shows because you can evaluate this function only once. So remember that in the first step, we only call this function once with all of the values in parallel. So from the computational complexity, we are much lower than here the classical algorithm, but still we are able with 100% precision in this case to see which state is the solution to our search problem. And that's working not only for the case of two qubits, but also with larger qubit registers. So for example, if you would take 10 qubits, you would need to execute a few more of these steps two and three. So instead of one iteration, you would need 25 iterations, for example, here, which is still much better than the 1,024 iterations that you would need if you would really look into every possible solution of the function in the classical algorithm. So the speed up here is very good for, so to say, all of the, like, it's quadratic for the solution space. And if you look at the complexity plot again, we can now compare our classical algorithm with the quantum algorithm, the Grover search. And as you can see, the time complexity or the number of evaluations of f that we need is only square root of n, where n is the size of the search space, which shows that we have really a speed advantage here of the quantum computer versus the classical computer. And nice thing is the larger our search space becomes, the more dramatic our speed up will be. Because for example, for a search space with one million elements, we will only have to evaluate the search function 1,000 times instead of 1 million times. So that's quite, so to say, a speed up in that sense. Now, how can we build a system that realizes this quantum algorithm? Here I show the quantum processor that I built with my colleagues at Saclay during my PhD. So if you want more information about this, you should check out my last talk. I just want to go briefly over the different aspects here. So we use the so-called superconducting qubits, transform qubits for realizing our quantum computer or quantum processor. You can see the chip here on the top. It's about one centimeter across. You can see the two qubits in the middle. The other, like, snake-like structures are coplanar waveguides where we can manipulate the qubits using microwaves. And so we use frequencies that are similar to the ones that are used by mobile phones to manipulate and read out our qubits. And if you look in the middle, you can see the red area, which contains the qubits, each qubit itself. And then there's another zoom in here, which contains the actual qubit structure, which is just some two layers of aluminum that have been placed on top of each other and which create, when they're cooled to very low temperature, a so-called superconducting state, where we can use the superconducting phase between these two values, layers to indicate to realize our qubits. There's also a coupler in the middle, so this green element that you see, which allows us to run quantum gates or operations between the two qubits. To use that in practice, we need to put this in a dilution cryostat, which is really, like, just a very fancy refrigerator, you could say. You cool that down to about 10 millikay, so very low temperature, just above the absolute zero temperature. You can see the sample holder here on the left side with the chip mounted to it, so this whole thing is put in the dilution fridge, then it's cooled down to the temperature, and then we can, as I said, manipulate it by using these microwave transmission lines. And what we did is we implemented the Grover search for the two qubits, so we ran this algorithm that I discussed before. I don't want to go too much into the details. The results are obtained by running this algorithm many times, and as you can see, we have achieved not 100% success probability, but over 50% for the most cases, which is like, yeah, not perfect, of course, but it's good enough to, in our case, show that there was really a quantum speeder possible. And if you ask why, okay, why is not 100% probability possible, or why can't we build larger systems with that, or what kept us from, for example, building a 100 or 1,000 qubit quantum processor? Well, there are several things. There's, of course, that we have, like, we make errors when we manipulate the qubits, so the microwave signals are not perfect, for example, so we introduce small errors when, like, making two qubit and single qubit interactions. We also need a really high degree of connectivity if we want to build a large-scale quantum computer, so if every qubit is connected to every other qubit, for example, that would make one million connections for 1,000 qubit processors, which is just, on the engineering side, very hard to realize. And then, also, our qubits have errors, because they can, the environment that the qubits are in, like the chip and the vicinity there, also introduces noise that will destroy our quantum state and that limits how many operations we can perform on a single qubit. So there's a possible solution, which is the surface code architecture, which was introduced in 2009 already, actually, by David Vincenzo from the Eulish Research Center, and the idea here is that we do not have a quantum processor with full connectivity, so we do not connect every qubit to every other qubit. Instead, we only connect the qubit to its four neighbors via so-called tunable coupler. And this is, of course, much easier, because you don't need so many connections on the chip, but it turns out that you can still run most of the quantum algorithms that you could also run with a fully connected processor. You just have to pay, like, a penalty for the limited connectivity. And the nice thing is also that you can encode a single logical qubit, so a qubit that we want to do calculations with, as, for example, five physical qubits, so all of these qubits here that are on the chip would together form one logical qubit, which would then allow us to do error correction. So we can, if there happens some error with one of the qubits, for example a relaxation or a defacing error, then we can use the other qubits that we prepared in exactly the same way to correct this error and continue doing the calculations. And this is quite important, because in the superconducting qubit systems there are always errors present, errors present, and we will not probably be able to eliminate all of them, so we need to find a way to correct the errors while we perform the computation. Now the Google processor follows the surface code approach. Here I show an image from the Nature article, which was released, I think, one months ago. So it's a very impressive system, I find. It contains 53 superconducting qubits, 86 couplers, tunable couplers between those qubits, and they achieve a fidelity, so the success probability, if you like, for performing one and two qubit gates, which is higher than 99 percent. So this is already pretty very very good and almost enough fidelity to realize quantum error correction as I discussed before. And with the system you can really run quite complex quantum algorithms, much more complex than the ones that we run in 2012. So in the paper, for example, they run sequences with 10 to 20 individual quantum operations or quantum gates. And just to give you an impression of the cryogenic engineering and microwave engineering here, this is, so to say, the delusion cryostat where the qubit chip is mounted, and you can see that it's quite a bit more complex than the system we had in 2012, so it really looks way more like a professional quantum computer, I would say. And if you ask a physicist now, why would you build such a system? The answer would be, of course, well, it's awesome, so why not? But it turns out that if an organization like Google gives like 100 or 200 million US dollars for realizing such research, they also want to see some results. So that's why, and the team, of course, under John Martinis tried to use this quantum processor for something that shows how powerful or that, so to say, it can outperform a classical computer. And this sounds easy, but actually it's not so easy to find a problem that is both doable on this quantum computer, which has like 50 qubits and a bit more than 50 qubits and like 80 couplers, but it's not possible to simulate on a classical computer. So you could think, for example, about the factoring of numbers into prime components, which is, of course, always like the motivation of certain agencies to push for quantum computing because that would allow them to read everyone's email, but unfortunately both the number of qubits that you would require for this and the number of operations is much too high to be able to realize something like this on this processor. The next thing which would be very interesting is the simulation of quantum systems. So if you have like molecules or other quantum systems that have many degrees of freedom, it's very difficult to simulate those on classical computers. On a quantum computer you could do it efficiently, but again, since the Google team did not do this, I assume the quantum computer was just or they didn't have like a feasible problem where they could actually perform such a simulation that would not be not be performable or like calculable on a classical computer. So, but in the near term in the future this might actually be very relevant application of such a processor. The last possibility would be to run for example the search algorithm that we discussed before, but again for the number of qubits that are in the system and the size of the search space, it's still not possible because the algorithm requires too many steps and the limited coherence times of the qubits in this processor make it impossible to to run this kind of like algorithm there, at least to my knowledge. So, what what they did then was therefore to perform a different kind of experiment, one that was doable with the processor, which is so-called randomized benchmarking. And in this case what you do is that you instead of like running an algorithm that does something actually useful like a search algorithm, you run just a random sequence of gates. So, you have for example your 53 qubits and then you run first like some single qubit gates, so you change the qubit values individually, then you run two qubit gates between random qubits to create like a superposition in an entangled state and in the end you just read out the resulting qubit state from your register. And this is also very complex operations, so you really need a very high degree of like control of your quantum processor, which the Martinez Google team was able to achieve here. It's not it's just not solving a really practical problem yet, so to say. But on the other hand it's a system or it's an algorithm that can be run on the quantum computer easily, but which is as we will see very difficult to simulate or reproduce on a classical system. And the reason that it's so difficult to reproduce on a classical system is that if you want to simulate the action of these quantum gates that we run on the quantum computer using a classical machine, a classical computer, then for every qubit that we add roughly the size of our problem space quadruples. So you can imagine if you have like two qubits then it's very easy to simulate that. You can do it on like your iPhone or like your computer for example. If you add more and more qubits though you can see that the problem size becomes really really big really fast. So if you have like 20 qubits, 30 qubits for example, you cannot do it on a personal computer anymore. You will need like a super computer and then if you keep increasing the number of qubits then at some point in this case 50 qubits or 53 qubits it will be impossible even for the fastest super computers that we have right now. And that's what is called a so-called quantum supremacy regime here for this randomized gate sequences which is basically just the area here on the curve that you see that is still doable for this quantum processor that Google realized but is not simulatable or verifiable by any classical computer even like a super computer in a reasonable amount of time. And if we can run something in this regime here it proves that we have a quantum system that is able to do computation which is not classically reproducible. So it's something that really can only be done on a quantum computer and that's why running this kind of experiment is interesting because it really shows us that quantum computers can do things that classical computers cannot do even if there are for the moment not really useful. And the gate sequence that they run looks something like this so we can see again like here five four of the qubits that the Google team has and they run sequences of operations of different lengths then perform a measurement and then just sample the output of their measurements. So what they get as a result is a sequence of long bit strings so zeros and ones for each experiment they run and to reproduce the to check that the quantum computer is actually doing the right thing you have to compare it to the results of a classical simulation of this algorithm. And that's of course a problem now because we just said that we realized the quantum computer or quantum processor which is able to do this computation on 53 qubits and that no classical computer can verify that so the question is now how can they prove or show that what the quantum computer calculates is actually the correct answer that he does not just produce some garbage values and that's a very interesting question actually and the way they did it here is by extrapolation so instead of for example solving the full circuit so that contains all of the connections and all of the gates of the full algorithm they created simplified circuits in two different ways so for example they cut they cut some of the connections between the qubits in the algorithm so that the problem space would become a bit smaller or in the other case with the alited circuit they just change the operations in order to allow for some shortcuts in the classical computation or classical simulation of the algorithm so in both cases they were able to then verify the result of the quantum computation with this classical simulation performed on a supercomputer and then they basically just did this for a larger and larger number of qubits they plotted the resulting curve and they extrapolated that to the supremacy regime to see that okay based on the error models that they developed based on the simulation they can with a certain confidence of course say that probably the quantum computer is doing the right thing even in the supremacy regime even though we can they cannot verify it using their classical simulations and in case the quantum computer did wrong still they have also archived the results so in maybe 10 years when we have better supercomputers we might be able to just go back to them and then verify them against the 53 53 qubit processor here by which time of course they might already have like a larger quantum processor again so the key results of this I would say are that for the first time they show that really quantum computer can beat a classical computer even though it is at a very artificial and probably not very useful problem and what the experiment also shows is that and really I would say an astounding level of control of such a large scale or medium-sized quantum processor because even five years ago or six years ago 2012-2013 the systems that we worked with mostly consisted of three or four qubits and we could barely fabricated chips that manipulate them to get like algorithms running and now if I see like a 53 qubit processor with such a high degree of control and fidelity there I can really say that it's really an amazing progress in the last five years that was achieved especially by the googled Martinez team here and I also think it's a very good milestone on the way to fully work on quantum computer because it nicely shows the limitations of the current system and gives a good direction on new areas of research for example in error correction where we can improve the different aspects of the quantum processor the research has also been criticized from various sides so I just want to like iterate a few of the points here one of the criticisms is of course that it doesn't do anything useful so there's really no applicability of this experiment and while that's true it's of course very difficult to go from like a basic very simple quantum processor with two qubits to a system that can really factorize prime numbers or do anything useful so we will always need to find problems that are both hard enough so that we can solve them in a reasonable time frame a couple of years for example that still prove the progress that we make on the road to quantum computing so in this sense while quantum supremacy does not really show anything useful in terms of computation that is done I think it's still a very good problem as a benchmark for any kind of quantum processor because it requires that you have very good control over your system and that you can run such a number of gates at a very high fidelity which is really currently I would say the state of the art the research they also took the authors also took some shortcuts for example they used like two qubit quantum gates which are not as we call them canonical gates which might be problematic because if you want to run a quantum algorithm on the system you need to implement certain quantum gates that you need for that and since they only have like non-canonical gates here which are still universal by the way they could not do that directly but with some modification of the system it should also be possible and the last criticism might be that okay here you have a problem that was engineered to match a solution which is of course that okay we need some solution as I said some problem that we can realistic itself on a such a system I think though also like the other points if you want to build a large-scale quantum process so you need to define reasonable milestones and having such a benchmark that other groups for example can also run that process against is a very good thing because it makes the progress visible and also makes it easy to compare how different groups or how different companies or organizations are are at competing on the number of qubits and the control they have about them so if you want to make a more kind of Moore's law for quantum computing there would be several possibilities that you could do here I show you for example the number of the qubits that have been realized for superconducting systems over the years this is of course incomplete because you could like the number of qubits alone doesn't tell you much about your system I mean we could do a qubit chip with 1,000 or 10,000 qubits today but if you don't have the connectivity and don't have the controllability of individual qubits then this chip wouldn't be good so there are other things that we also need to take into account here as I said just as like the coupling between individual qubits and the coherence time and the fidelity of the qubit operations so this is really just one one very small aspect of this whole whole problem space but I think it shows nicely that in the last years there was really tremendous progress in terms of the power of these superconducting systems because the original qubit which was developed at NEC in Japan by Professor Nakamura was done in like around 2000 so had very very bad coherence time very bad properties but still it showed for the first time that you could coherently control such a system and then it didn't take long for other groups for example the quatronics group in Sir Clay to pick up on this work and to keep improving it so after a few years we already had qubits with a few hundred or even a microsecond of coherence time which was like three orders of magnitude better than what we had before and there were other advances then made by groups in the US for example in Yale the Shirkopf lab which developed new qubit architectures that allowed us to couple the qubits more efficiently with each other and to again have better control over manipulating them and then there's also groups like the research group at IBM or companies like Rigetti that took again these ideas and that added engineering and their own research on top of that in order to make the systems even better so in 2018 we already had systems with 17 or 18 qubits in them and now with this Google and UC Santa Barbara work we have the first systems with more than 50 qubits after not even 20 years which I think is quite some progress in this area and of course if you ask me how close we are to an actually working quantum computer it's still very difficult to say I find because we prove in a group prove the quantum supremacy for this randomized algorithm but in order to do something applicable or useful with such a quantum system I think we need like at least again 50 maybe to 100 additional qubits and a larger number of qubit operations but it's really hard to say that's why I also say don't believe in this chart because there's also of course a lot of work in the theory of quantum algorithms because up to now we are still discovering new approaches of doing quantum simulations for examples and right now there are a lot of research groups that are looking for ways to make these medium scale quantum computers so quantum computers with 50 or 100 qubits already useful for the use in quantum simulations so it's really an interplay between what the theory can give us in terms of quantum algorithms and what in terms of experimental realization we can build as a quantum processor so in my opinion quantum simulation will definitely be something that where we will see the first applications in the next I would say three to five years other things optimizations I have to admit I'm less an expert in I think they're a bit more complex so we will probably see the first applications in those areas a bit later and the big motivation for like the tree ladder agencies always is of course the factoring the breaking of crypto systems which is the most challenging one though because in order to do that you would both need very large numbers of qubits so at least 8,000 qubits for an 8,000 bits RSA key for example and you would also need a very large amount of qubit operations because you need to run this shore operation and that involves a lot of steps for the quantum processor and this is so to say the most I would say from my perspective unrealistic application of superconducting quantum processes in the next year but I think if somebody would build a quantum computer maybe we would also not just know about it so who knows so to summarize quantum computers or quantum processes are getting really seriously complex and very impressive so we have seen tremendous progress in the last five years I still think that we are like five years away from building really practical quantum computers and there are still some challenges for example in error correction and the quantum gate fidelity and then again general architecture of these systems that we need to overcome and there might also be some challenges which we haven't even identified yet which we might only encounter at a later stage when trying to build really large scale quantum processors and as a last point I just want to stress again that quantum computing research is not only done by Google or by IBM there are a lot of groups in the world involved in this kind of research both in theory and in experiment and as I said before a lot of the breakthroughs that we use today for building quantum processes were done in very different places like Japan Europe USA so it's really I would say global effort and you should also when you look and when you see this marketing or PR that companies like Google and IBM do maybe not believe all of the hype they're creating and keep and down to earth view so to say of the limits and the potential of quantum computing so that's it and I would be happy to take on your questions now and if you have any feedback there's also my Twitter handle there and my email address and I think we also have some time for questions here right now thank you thank you Andreas we have almost 20 minutes for Q&A if you're leaving now please do so very quietly and if you can avoid it just don't do it thank you okay Q&A you know the game there's eight microphones in this room so just queue behind them and we will do our best to get everyone sorted out sequentially we will start with a question from the internet thank you do you have information about the energy consumption of a quantum computer over the calculation power ah yeah that's an interesting point I mean for superconducting quantum computers there are like several costs associated I think right now the biggest cost is probably of keeping the system cooled down so as I said you need very low temperatures 20 or 10 millikelvin in order to achieve that you need the so-called delusion cryostat and these systems they consume a lot of energy and also materials like helium mixtures which are expensive and like maybe not kind of like rare material right now I think that would be the biggest consumption in terms of energy use I honestly don't have so much of an idea I mean the manipulation of the qubit system is done via microwaves and the power that goes into the system is very small compared to any of the power that you use for cooling the system so I would say for the foreseeable future the power consumption should be dominated by like the cooling and the setup cost and the cost of the electronics as well so the classical electronics that controls the qubit which can also be quite extensive for a large system so the qubit chip itself should be very should be really negligible in terms of energy consumption thank you microphone number one please hello I have a question in regards to quantum simulation so I would have thought that with 53 qubits there would already be something interesting to do since I think the border the limit for more or less exact quantum chemistry calculations on classical computers is that there are 10 to 20 particles so is there a more complicated relation from particles to qubits that's missing here or what's the problem yeah so in the paper I couldn't find in the exact reason why they choose this problem I think there are probably two aspects one is that you don't have in the system the like arbitrary qubit control so to say so you cannot run like any Hamiltonian or quantum algorithm that you want you are like limited in terms of connectivity so it's possible that they were not able to run any quantum algorithm for simulation which was not easy to run also on a classical system you know so but I'm really not not sure why they didn't I think just if they would have have had this chance to do a quantum simulation they would probably have done that instead because that's of course more impressive than randomization or randomized algorithm so because they didn't do it I think it was just probably too complicated or not possible to realize on the system yeah okay so it's this but again I don't know for sure yeah thank you yes and also speaking as a sometimes quantum chemist you can't directly map qubits to to atoms they're not two level systems and you don't I mean you usually also simulate electrons and not just the atoms but I'm not a speaker we can discuss later microphone number two please hi thanks can you compare this classic or general quantum computer to the one by d-wave that's one of the quantum computers by aws offered they have 2000 qubits or something they say yeah that's a really interesting question so the d-wave system is the so-called adiabatic quantum computer to my knowledge so this in this case the the computation works a bit differently it's with the normal with this quantum computer that google produced you have a gate sequence that you run on your input qubits and then you get a result that you read out with the d-wave system it's more that you like engineer like in Hamiltonian which is also which also consists of local interactions between different qubits and then you slowly change this Hamiltonian in order to like change the the ground state of the system to a solution of a problem that you're looking for so so it's a different approach to quantum computation they also claimed that they can can achieve or that they achieve a quantum supremacy I think in a different way for like an optimization problem but to my knowledge the proof they have is less rigid probably than what the google group produced here so but again I'm not like an expert on adiabatic quantum computing so I'm more like gate-based person so yeah I think though the proof that here google showed is more convincing in terms of like reproducibility and really like the the proof that you're actually doing something that cannot be done on a classic computer yeah thank you yeah T-Wave will see that differently I think though yeah all right let's go to the back number seven please hello seven you just wave to me hello I was reading that earlier this year IBM released the first commercial iq one system or whatever the name is and you were mentioning before to keep our expectation down to earth so my question is what kind of commercial expectations is IBM actually creating so I spoke to some companies here in Germany that are collaborating with IBM or D-Wave or google as well and ask what they're actually doing with the quantum computers they are the companies offer and I think the answer is that right now a lot of commercially a lot of companies are investigating this as something that could potentially be very useful or very relevant in five to ten years so they want to get some experience and they want to start collaborating I don't think at least I don't know any reproduction use of these systems where the quantum computer would do some calculations that would not be doable on a classical system but again I don't have a full overview of that I think now it's mostly for experimentation and for getting to know these systems I think the companies or most of the customers there probably expect that in five years or ten years the system will systems will really be powerful enough to do some useful computations with them as well thanks all right the internet please with the quantum computer you can calculate things in parallel but there is this reversibility requirement so how much faster is the quantum computer at the end of the day yeah it's true so that if you want to if you want to realize classical algorithm you have to do it in a reversible way but to my knowledge you can from an efficiency perspective implement any classical non-reversible algorithm as a reversible algorithm without loss in complexity so you can have also like for reversible computation you have universal gates like the control not gate that you can use to express any logic function that you require you might need some additional qubits compared to the amount of the classical bits that you need for the computation but in principle there's nothing that keeps you from implementing any classical function on a quantum computer in terms of actual run time of course it depends on how fast you can run individual operations so right now a single qubit operation for example on this Google machine takes about I think 20 to 40 nanoseconds so in that sense the quantum computers are probably much slower than classical computers but the idea is anyway that you do only really the necessary computations that you can't do on a classical machine on a quantum computer and anything else you can do on a normal classical system so the quantum processor in this sense is only like like a co-processor like a GPU in that sense I would say all right microphone number four please on the slide that shows Richard Feynman you said that quantum computers were invented to simulate quantum systems and can you please elaborate on that that you went past yeah so I don't have to link to the lecture here unfortunately the link is broken but you can find that online it's a 1982 lecture from Feynman where he discusses like how you would actually go about simulating a quantum system because as we have shown like if you want to simulate a full quantum system you need to simulate the density matrix of the system and that takes about that takes an exponential amount of memory and computation in terms of like the number of qubits or quantum degrees of freedom that you want to simulate and with a classical or a Turing machine you couldn't do that in an efficient way because every time you add a single qubit you basically quadruple your computational requirement and that's really where the idea came from I think from Feynman to think about a computing system that would use quantum mechanics in order to be able to do these kind of simulations because he saw probably that for large quantum systems it would never be possible to run at least with our current understanding of classical computing it would never be possible to run a quantum simulation of a quantum system on a classical computer in an efficient way does it answer the question okay all right microphone eight please as a physicist who's now doing analog circuit design I'm kind of wondering why all the presentations about quantum computers always use state zero and one and not multiple states is that a fundamental limitation or is that just a simplification for the sake of the presentation so you mean why you don't use like higher qubit states or like multivalued logic or even continuous states so in principle the quantum bits that we're using they don't they're not really two level systems so there is not only the level zero and one but also level two three and so on you could use them of course but the computational power of the system is given as the number of states so like m for example raised to the power of the number of qubits so m to the power of n so in that sense if you add like another state you only change like like a smaller factor than adding another qubit so it's usually not very interesting to add more states what you would do instead is just add more qubits to your system and for continuous variable quantum mechanic quantum computation I think there are some use cases where this might outperform like the digital quantum computers especially if you can engineer your system to like mimic the Hamiltonian of the system that you want to simulate so I think in this sense in these cases it makes a lot of sense for other cases where you say okay you want to run a general quantum computation then like such a digital quantum computer is probably the best solution and you could also just to add that run like a continuous simulation of a quantum system on such a gate-based quantum system just like the linearly the same order of complexity I would say does it answer the question I think I delude myself to have understood that the non-diagonal elements in the density matrix grow much faster than the number of states in any any diagonal matrix element I guess you could say it like that yeah I have to think about it all right number three please what do you have to say about the skepticism of people like Gil Calai that claim that inherent noise it will be a fundamental problem in scaling these quantum computers I mean it's a valid concern I think as of today we don't have even for a single qubit shown error correction there are some first experiments for example by the Schulkopf lab in Yale where they showed some of the elements of error correction for a single qubit system but we haven't even managed today to like keep a single qubit alive indefinitely so that's why I would say it's an open question it's a valid criticism I think the next five years will show if we are actually able to run this quantum errors and if our error models themselves are correct because they're only correct for certain errors or if there's anything else that keeps us from like building a large-scale system yeah so I think it's a totally valid point yeah microphone five please there has been a study on factorizing on adiabatic machines which requires log squared n qubits while show requires n log n but as the adiabatic systems have much higher qubit numbers they were able to factorize on these machines much larger numbers than on the normal devices and that's something that never shows up in the discussion do you want to comment on that have you read the study what do you think are adiabatic machines bogus or is that a worthwhile result I'm not yeah as I said like an expert on adiabatic quantum computing I know that there were some like studies or investigations of the D-Wave system like I haven't read this particular study about factorization I think adiabatic quantum computing is a valid approach as well to quantum computing I just I'm not just just not sure if currently like the results were like shown with the same amount of like rigidity or like rigid proofs like for the gate-based quantum computer but yeah I really would have to look at the study to to see that yeah can you maybe quickly say the authors so it's on the record yeah if your mic is still on number five sorry I don't okay no problem think sorry but yeah I don't think adiabatic quantum computing is like and I think adiabatic quantum computing is a valid choice of a valid approach for doing quantum computation as well yeah so I can give you I can search for the authors later and give it to you okay okay that would be great thank you thank you microphone four please what do you say about IBM's claim that Google's supremacy claim is invalid because the problem was not really hard yeah so basically IBM I think said okay if you do some optimizations on the way you simulate the systems then you can reduce this computation time from 10,000 years to like maybe a few hours or so I think it's of course a valid it might be a valid claim I don't know if it really invalidates the result because as I said like the computational power of like the classical systems they will also it will also increase in the coming years right now okay you could say then maybe if we haven't achieved quantum supremacy in regards to like the 2019 hardware then maybe we should just like look at the 2015 hardware and then we can say okay they're probably we achieved that in any case I think the most what's most impressive about this result for me is not like if we are really in the supremacy regime or maybe not that's really the amount of the degree of controllability of the qubit system that this group has achieved I think that's really the important point here regardless of whether they actually achieve the supremacy or not because it shows that these kind of systems seem to be a good architecture choice for building larger scale quantum processes and this alone is very valuable I think as a to guide the future research direction regardless of whether this is actually of they achieved this or not yeah but yeah I can understand of course the criticism yeah okay one thing the article is called quantum annealing for prime factorization appeared in nature in December 18 authors are John Britt mackersky humble and case okay great thank you have a look at that again thanks all right microphone six do you have a short question yeah hopefully it is known that it is not very easy to understand how large quantum superposition goes into microscopic state so into microscopic physical description so apparently there are a couple of things not understood so is there anything you know about when you go to thousand ten thousand million qubits could you expect the quantum behavior to break down are there any fundamental argument that this will not happen or is this not a problem considered recently okay I'm not sure if I fully understand the question it's mostly about like if you say like quantum mechanics has some like scale variants so that if you go to a certain scale then sometime at some point you have like irreversibility or like something like that yeah I mean I think there are large quantum systems that occur naturally I don't know like Bose-Einstein condensate for example has a lot of degrees of freedoms that are not controlled of course but that are also quantum mechanical and there it seems to work so personally I would think that there's no such limit but I mean who knows it's like experimental physics yeah so we will see as if we reach that but from like the theory of quantum mechanics right now there's no indication that there should be such a limit yeah to my knowledge all right so maybe we will see you again in five years so please thank Andreas once again thanks


Imagine the government trying to take your kids away because you gave them Tylenol. Hello everyone, Dylan Schumacher, Citadel Defense, and this is not a happy story. This is one I came across a couple days ago here that came out of New Hampshire. And basically, again, I'll try to link the description in the description below here so you can read the full story if you want. But a guy in the great state of New Hampshire, him and his family got coronavirus. They treated it with ivermectin because God bless America and you can do whatever you want. And they went to the doctor because he was concerned that his kid had overdosed on acetaminophen, which is just Tylenol. It's the active ingredient in Tylenol. So he had cold poison control. They told him to go to the doctor. He did while he was there. He was talking to the doctor that, you know, they had COVID. They treated with ivermectin and, you know, everything is all better now. And some do-gooder, little informant rat nurse decided that it wasn't right that this guy treated his family with ivermectin. And that's probably why his kid almost overdosed on acetaminophen. And she called the Child Protective Services on him in order that they would show up at his house, which they did with the police to try to take his kids away. Now, very fortunately, this guy had already sent his kids away. And so they weren't there when the police came there to confiscate his children. They weren't there. And now he's been in some court legal battles and had to go to court in order to let the government say, it's okay, you can keep your kids.   And it's not just like they do things that we don't agree with. It's that reason has left the building. The kids are obviously fine, right? They're obviously being cared for. This guy is obviously loving and caring for his family.  And so therefore, he is a threat to the state and the order of things. And so they don't like that. And so they get mad.  If you ever get coronavirus, never tell anybody because that's not a good thing. Because again, the policemen show up to take your kids away just because, apparently, because they think they have that authority.  That's the time we live in. And they're looking to ruin your life because you do something that they don't agree with. The live and let live idea of America is not the one that we are living under right now. It's not the idea that reigns supreme. But rather, the idea of liberty is seen as something that's dangerous and subversive. And you just wait for it unpatriotic. Think about that. Decide what kind of America you want to live in and stop complying with a nonsense. Two brave deeds, end endure.


Welcome to part 3 of the lecture on machine code generation. Today, we will continue with our discussion on Sethe-Ullman algorithm for optimal code generation and also look at the dynamic programming ways and tree pattern matching based algorithms. So, to do a bit of recap, the Sethe-Ullman algorithm is one of the probably optimal algorithm. So, in other words, it generates the shortest sequence of instructions possible for a given basic block. Of course, the limitation of this algorithm is that it works only for expression trees and it does not work for DAGs. So, if there is a DAG given to us, you know then we will have to break it into trees and apply the Sethe-Ullman algorithm on individual trees. The machine model is that all computations are carried out only in registers. So, and the instructions are of the form op r comma r or op m comma r. So, the point here is the left you know operand should always be in a register. So, it computes the left subtree into a register and reuses it immediately. So, in this type of instruction, this register is the left operand and the memory could be the right operand. It cannot be the other way it must always have the left operand in a register. So, it has two phases one is the labeling phase and the other is the code generation phase. The labeling phase is quite simple. So, let me do the recap with the example itself. So, assuming that this is the expression tree given, the operators in the nodes are not very important to us. So, we have just named them as n 1, n 2, n 3, n 4, n 5. The labeling algorithm labels the leftmost leaf of its parent as 1 and all other leaves of the parent as 0. So, this is a 1 and this is a 0. The same thing is true for n 2 and n 3 as well. When we go to the internal nodes n 1, n 2 and n 3, since the left subtree has a label of 1 and the right subtree has a label of 0, which implies that the two labels are not equal, we take the max and assign it to the parent. So, this becomes 1. Similarly, this becomes 1 and this also becomes 1. Now, we have a situation where n 1, n 2 have labels of 1 and n 3 is the parent with children which have equal labels. So, we take increment the label value and take it as a label value for the parent. So, this becomes 2. So, now, we have 2 and 1 here. So, n 5 automatically becomes the max of these two, which is 2. How do we evaluate such a tree with two registers? So, there are two possibilities. Let us examine both of them. One of them, you know, gives us the correct evaluation, the other one does not. So, let me look at the incorrect evaluation first. So, let us assume that we evaluate n 4 into, you know, n 4 first and then n 3. So, the subtree at n 4 first and then the subtree at n 3. So, if we have to evaluate this, we must obviously evaluate both its operands. So, the left operand must be in the register. So, we must load it into a register or one, let us say and then we evaluate the parent n 4, which an operator n 4. So, which permits the right operand to be a memory operand. So, this gets evaluated and the result will always be in a register. So, that let us say that is R 1. So, if we have finished this now, this evaluation has been finished now and it says yes it can be done with one register, which we have satisfied. Now, the remember that the result is held in the register R 1. So, when we go to n 3, the min drag value says it is 2. So, without 2 registers, it will not be possible to evaluate this 3 without storing the intermediate values into memory location. Let us see why. Of course, this is n 1 is very similar to n 4. So, it can be evaluated into R 0, but then we do not have R 1 free, it holds the value of n 4. So, now unless we store R 0 into a memory location, which is not permitted by the algorithm, because there exists a better order with which we can do the evaluation. So, this you know evaluation fails. So, suppose we start with the evaluation of n 3 and then go to n 4. Now, we have a happy situation, we evaluate n 1 into R 0 as before. Now, R 1 is still free. So, we can evaluate n 2 into R 1. So, this is the second register that we are using and now n 3 can be evaluated into R 0 with its two operands being in registers. After that, value of n 3 is held in R 0 and R 1 is freed. This R 1 can be used to evaluate n 4 and then we can evaluate n 5. So, the basic principle in the algorithm is take the sub tree at a particular node, try to evaluate the sub tree with requires more number of registers and then the sub tree with requires less number of registers, but there are details. So, we will come to those details very soon. Here is the procedure gen code, which is the main procedure to generate code for the sub tree rooted at the node n. The procedure uses two stacks, one is the R stack which is the stack of registers starting with R 0 to R R minus 1.  T stack is a stack of temporaries. So, we generally assume that there are enough number of temporaries and that there is no scarcity of supply. That is the reason why the bottom of the stack is not mentioned, it would be a fairly large number. The top of the stack is T 0. So, these are the various temporaries that are generated. So, whenever we want a register, you know we can use the registers from the stack of registers and then whenever we want a temporary, we can use it from the stack of temporaries. But, we must remember that we should use the top of the stacks, both register stack and temporary and then go into the deeper parts of the stacks. So, a call to gen code n generates code to evaluate a tree T rooted at the node n into the register, which is at the top of the R stack. So, top of R stack and the rest of the R stack remains in the same state as the one before the call. So, this is a very important consideration to prove the correctness and optimality of the algorithm. So, we must make sure that the result is always at the top of the stack in the register located at the top of the R stack and that the rest of the R stack is in exactly the same state as the one before the call to gen code was made. So, these are two very important things. So, incidentally somewhere in the middle of the algorithm, we will also have a situation to swap the top two registers of R stack. So, this becomes necessary to ensure that a node is evaluated into the same register as it is left child. So, we will see this as we go on. So, let us look at the details of the algorithm. There are many cases 0 through 4, case 0 we are looking at a leaf node n. So, n is a leaf representing the operand n and is the left most child of its parent. So, this means it has a label of 1. So, if it were to be not the left most child then it would have had a label of 0. So, this has a label of 1 that means you know you can evaluate it with one register which is very trivial. We just generate the load instruction load n comma top of R stack. So, automatically this implies the value of n will be put into the register which is at the top of R stack at the time of evaluation that is the execution. So, this is a trivial case. Now, case 1 similar, but not the left child, but the right child is the leaf node. So, the left child is the root of a sub tree that is n 1 and the right child of n is a leaf node. So, if because this is the right child it will have its value as label as 0. So, n is an interior node with operator of left child n 1 and right child n 2 and the label of n 2 is 0 that means it is a right child. So, then let n be the operand for n 2. So, this is the memory location corresponding to n. So, we first generate the code for n 1 you know we can use the memory operand as it is. So, let us finish the code generation for the root for the trees rooted at n 1. So, that requires a certain number of registers label of n 1. So, once we have finished code generation n code prints out the code for that tree rooted at n 1. Now, it is time to generate the code for n. So, that is what we print out. So, code print op n comma top of r stack. So, i top of r stack top of r stack contains the result of the tree n 1 right. So, that is the left most child and we are now reusing the left most child value immediately in the parent. So, and the result will also be now left in the same register as the left that of the left most child. So, that is top of r stack. So, remember gen code n 1 will you know make sure that the top of r stack the register will contain the value of the tree at execution time. So, this is correct print op n comma top of r stack will that is an instruction when execute which when executed will leave the result in the top of r stack again. So, for this entire tree we have satisfied the rules of the game that is the rules of the algorithm the value of the entire tree is available in top of r stack and the rest of the r stack below the top is in the same condition as it was when we call the procedure. The next case. So, we have both n 1 and n 2 you know as roots of sub trees, but the case is the tree n 1 requires less than r number of registers r is the number of available registers and the sub tree rooted at n 2 requires more than what n 1 requires. So, it is not more than r not necessarily, but it definitely requires more than what n 1 requires. So, the thing is the both of them you know are sub trees. So, we will have to generate code for them it is not that we can use an operand as it is. So, 1 less than or equal to label of n 1 less than label n 2. So, that is what we have written here and label of n 1 is less than r. So, because n 2 requires more than the more registers than n 1 that is what the label means and n 1 requires less than r number of registers. So, when we evaluate n 1 we do not require any stores into memory we really cannot say much about n 2 because the condition says label of n 2 greater than label of n 1 it does not say it is greater than or equal to r. So, now since we are evaluating the right sub tree and suppose we evaluate it as it is then the top of r stack will contain the result of n 2. So, this would get us into some trouble because the left sub tree must leave it is result in the top of r stack and that will be reused immediately by the root. So, to take care of this we do an r swap on the r stack. So, that the swap function swaps the top 2 registers of the stack it ensures that a node is evaluated into the same register as it is left side. So, once it is swapped the second register from the top will become the top most register now we call the encode on the n 2. So, the second register which is at the top now will contain the value of the entire tree. In other words it generates the instructions which evaluate this tree and place its value in the top of r stack which is the second register from the top after the swap operation. Now, pop the r stack and remove that register remember which register it is that is r. Now, we have you know the original top of r stack at the top. So, we call gen code n 1 now it leaves the value in the top of r stack. So, this code sequence when evaluated will leave the value in the top of r stack the register at the top of r stack. So, and r now holds the result of n 2. So, remember n 1 is in the top of r stack register and n 2 is in r now we are in a position to generate the code for the root n. So, we say op r comma top of r stack. So, this is correct this top of r stack right now is the original top of r stack before the swap. So, now r is of no use to us because the top of r stack will contain the result of the entire tree after evaluation. So, we push the register into the r stack now the top of r stack originally you know now becomes the second one. So, we swap it brings it to the top. So, the invariant of the algorithm remains true the top of r stack now contains the value of the entire register and the rest of the r stack is in the same state as it was before the call. So, this is the reason we require a swap in this part in this particular case. So, we are evaluating the right node the right sub tree and to make sure that the left sub tree leaves its result at the top of r stack we do a swap then the next case. So, again you know it is the case similar to the previous one the right sub tree requires less than r number of registers and the left sub tree requires greater than what the right sub tree requires. And of course, we also say a label of N 2 is less than r. So, this can be evaluated with no intermediate source, but there is no guarantee about N 1. So, now we have a very simple case because N 1 requires more registers than N 2 according to the label we simply call gen code N 1 which evaluates after the when the code is executed the result will be left in the top of r stack register. So, remove that register pop by pop operation now gen code for N 2. So, the code for N 2 will now be emitted or holds the result of N 1 and the top of r stack after this pop operation will hold the result of N 2. Now, generate the code for the root. So, op of print op top r stack comma r. So, now the top of r stack you know is the register currently at the top, but r was at the top of r stack before the algorithm on the procedure as called. So, now r will hold the value of the entire sub tree. So, push r stack comma r. So, now r becomes the top of r stack and thereby the invariant of the algorithm is maintained r is the top of r stack and it contains the result of the entire tree. So, this is the last case in this algorithm. So, both the sub trees N 1 and N 2 require more than r more than r equal to r number of registers. So, in such a case it is not possible to generate code without storing some of the intermediate results into memory. So, in such a case since both of them require source into memory it really does not matter which one we take up, but since we need to leave the result of N 1 in the top of r stack and then reuse it immediately for the parent. Obviously, we must generate the code for N 2. So, we generate the code for N 2. So, if we had generated code for N 1 we would have had to put it into a temporary and load it back from the temporary at the time of you know evaluating N. So, this would mean inefficiency. So, whereas if the result of N 2 is kept in a temporary it can be reused as a memory operand in the instruction while evaluating N. So, this is the reason we generate the code for N 2. So, that is the gen code N 2 then pop the pop a temporary from the stack and generate an instruction to place the top of r stack value into the temporary. So, now all the registers are free again. So, generate code for N 1 otherwise we would have held back one the registers which is not correct. So, generate code for N 1 then print op t comma top of r stack. So, we now have you know the value of the entire tree in the top of r stack register. Of course, the temporary is not required anymore. So, push it back into the t stack. So, again the invariant of the algorithm is satisfied. So, this is the detailed you know description of the algorithm. So, now let us look at two examples one in which the number of registers is two and we do not require more than two registers and the other would be we have one register and we require more than one register. So, obviously the algorithm is very simply applied starting from N 5. So, the min reg values are all mentioned here. So, this is one and this is two and this is two this is one this is one. So, now we start with N 5 and we have two registers available. This requires one register and this requires two registers. So, we call gen code on this right. So, once we call gen code on this the task is to evaluate these two right. So, both have one register requirement and it is less than the number of available registers. So, we can simply go to left sub tree and that requires loading from memory location.  So, this will evaluation of this would be completed by this stage. Then we go to N 2 generate the code for loading c into r 1. So, r 0 holds the value of this now r 1 is still free.   So, that completes N 3 as well now r 1 is free. So, we can generate the code for N 4 that requires loading e into r 1.  So, without storing any result into any temporary location we are able to generate the code for this.  So, this is the sequence of instructions for this particular tree. So, let us look at another example the number of registers is just 1 whereas, we require 2 registers here and also here. So, when we start code generation at this point this requires 2 and this requires 1, but both of them require greater than or equal to number of registers available which is 1. So, as I said we in this case that is here you know. So, we would always go to N 2 both require more than or more than or equal to r number of registers. So, we go to this then this is as usual load e and then op. So, those 2 are done now r 0 contains the result of N 4, but we must free it otherwise we cannot evaluate N 3 at all. So, there are no instructions to operate on with 2 memory operands that is the problem here and. So, we free this register by generating an instruction to load it into a temporary. Now, we go to N 3 and then obviously, there is N 1 and N 2 both require greater than or equal to r number of registers. So, again it is a write by us that we have. So, we go to N 2 then load c and then op N 2. So, these 2 require 2 instructions to generate to code which evaluates N 2 again we must free the register. So, that this can be evaluated. So, load r 0 comma t 1. So, we generate we take another temporary t 1 and move the result into t 1. Now, we are ready to generate code for N 1 which is very similar load and then op.  So, that completes the evaluation of this N 1. Now, left sub tree is in a register right sub tree is in a temporary we can generate code for N 3. So, that would be op N 3 t 1 comma r 0. So, now the result will be in a register r 0 and this evaluation is completed t 1 of course, can be released at this point. Now, we are ready to generate code for N 5 which would be op N 5 t 0 comma r 0. So, that places the result again in r 0 and releases the temporary. So, again so we have generated code for the entire sub tree and we also have the result in a register. So, remember this requires storing result intermediate results into temporary locations. So, now we move on to another optimal code generation algorithm. So, this is the dynamic programming based optimal code generation. Again, it caters to only trees and it is not possible to handle directed acyclic graphs. Unfortunately, DAX you know code generation for DAX is NP complete. So, there is no optimal algorithm that is possible. So, at least there is no optimal algorithm which works in polynomial time that is possible. We will see that later. This dynamic programming based algorithm caters to a slightly broader class of machines. The first requirement is that there are r interchangeable registers r 0 through r r minus 1. Remember this is not a stack anymore. So, it is just a set of registers r 0 through r r minus 1 and the requirement is that there are there is nothing like a special purpose register here. Any register can be used in any instruction. Then the instructions are of the form r i equal to e. Not much restriction is placed on the form of e like in the case of the set Hulman algorithm. The only restriction is if e involves registers r i must be one of them. So, the left operand left operand of the assignment is a register and the right part r h s is an expression. So, if e uses expressions then r i must be one of these sorry if e uses registers then r i must be one of those registers. If all the operands in e are memory locations then r i can be any other register. So, this is the so again the computation is performed in a register. Of course, we definitely require instructions of the form m i equal to r j to store values which are in registers into memory, but all other instructions are of this form. So, here is a sequence of possible rather set of possible instructions. So, assuming that there are many registers available for each one of those registers there is an instruction. So, r i equal to m j of course, m j is any memory address. So, if we have two registers then we would have instructions possible such as r 0 equal to m j and r 1 equal to m j. So, similarly for all the others another possible instruction is r i equal to r i of r j. So, see that r i is used in the expression here. So, r i must be on the l h s also. Similarly, r i equal to r i of m j. So, one of the operands can be a memory. Then we have r i equal to r j. So, of course, we would we may also have r i equal to m i of m j, but in this example we do not have it that is all. So, r i equal to r j which is a copy instruction. So, again this j must be i if this is i then it is of no use.  Whereas, if r i and j are different then it is a copy operation and that is a useful instruction. So, this is this and this are the two variations of this. So, this e involves registers r i must be one of them is not really satisfied here. So, this is the format of instructions that we are going to assume in our examples, but any general instruction with more than two operators is also possible. So, more than one operator rather or one operator with three operands. So, this has two operands we can have you know two operands now, but we can also have three operands. In other words this is a very general purpose machine. So, we may even have complicated instructions such as multiply and accumulate. So, that would be something like two operations in the same instruction, but with a special operator for it mac for example, multiply accumulate. Based on the this is based on what is known as the principle of contiguous evaluation which I am going to explain very soon and it is it produces optimal code for trees. So, again basic block level trees no DAGs are permitted and it can be extended to include a different cost for each instruction. In the Satie Wollman algorithm there was no question of a cost for each instruction. The length of the sequence of instructions generated was the cost of the entire code whereas, here we can attach an you know a cost to each instruction. So, this could have a higher cost compared to r i equal to r i of r j simply because this involves a load from memory right. The same is true for m i equal to r j this involves a store into memory whereas, this is just a copy operation. So, each instruction could have a different type of cost then we still have to explain what is contiguous evaluation. So, consider a tree in which there is an operator op at the root then we have two sub trees T 1 and T 2. How does one evaluate such a tree? Well there are many possibilities right. So, before evaluating op it is certain that we must evaluate both T 1 and T 2, but we can evaluate T 1 first then T 2 and then op or we could evaluate T 2 first then T 1 and then op these are two possible orders, but then while evaluating T 1 we could evaluate a part of T 1 then jump to T 2 evaluate a part of T 2 continue with the evaluation of T 1 then again hop to T 2 etcetera etcetera. So, and finally, once the evaluations of T 1 and T 2 once they are completed we can evaluate the tree T, but the principle of contiguous evaluation allows only two possible orders one is evaluate T 1 completely or evaluate T 2 completely. So, one of these must be done first then we can once assume that we have evaluated T 1 first then we must evaluate T 2 and then we can evaluate op otherwise we must do T 2 completely then T 1 and then op. Now, the finer details. So, when we are evaluating T 1 and T 2 there is a rule which says evaluate sub trees of T that need to be evaluated into memory first. So, there may be parts of T 1 which require too many registers. So, what we do is evaluate that small sub tree of T 1 into we using all the registers store it into a memory location. We do that for all parts of T 1 which must be evaluated into you know memory the same is true for T 2. Now, after all these evaluations are done we would be you know we would actually be left with parts of T 1 and parts of T 2 which can be evaluated in using only the registers. In such a case after the evaluations into memory are over we must evaluate the entire T 1 first and then T 2 and then op or entire T 2 first and then T 1 and then op. So, this is called as contiguous evaluation order. Why should we say evaluate sub trees of T that require that can need to be evaluated into memory first and then the rest the problem is when we have something to evaluated something to be evaluated into memory. We might as well use all the registers available load that result into memory and then again go to some other part which requires evaluation into memory use all the registers and then store it into memory and so on and so forth. If we do not do this if we try evaluating other parts of the tree which require registers alone we would be actually left with lesser number of registers to evaluate these small sub trees which have to be evaluated into memory. How does one decide whether to evaluate something into memory or using registers alone that we will learn very soon because there is going to be a cost attached to every type of evaluation. So, what is not permitted in contiguous evaluation well we cannot evaluate assume that everything can be evaluated into in using registers alone right. So, we cannot evaluate parts of T 1 and then parts of T 2 again parts of T 1 again parts of T 2 etcetera etcetera we cannot do that that is permitted only when they need to be evaluated into memory otherwise when we are using only registers we must finish the evaluation of T 1 if we start it and then T 2 and then up or the other way first T 2 then T 1 then up. These decisions are actually driven by the cost considerations and we will see how to do it very soon. Why this contiguous evaluation well the most important part property of contiguous evaluation is that it is optimal. So, the code which is going to do contiguous evaluation is optimal code in what sense the code does not require any higher cost and it does not require more registers than any other optimal evaluation. So, there may be many optimal evaluation possible using the same number of registers and having the same cost. What this contiguous evaluation theorem tells us is generate code for contiguous evaluation then it actually cannot be worse than any other optimal evaluation it is as good. So, the contiguous evaluation you know principle is very simple and it allows us to generate code in a very simple fashion that is having decided that we generate code for T 1 we do not have to jump to T 2 at all we can finish the code generation for T 1 and then go to T 2 generate the code for T 2 and then generate the code for up. If the cost considerations had told us that we must do the other way first T 2 then T 1 then up we finish the code generation for T 2 then T 1 and then up. So, we do not have to consider the operation you know the evaluation orders which require parts of T 1 you know optimal evaluation orders which require parts of T 1 to be evaluated first and then parts of T 2 etcetera. We can we can stick to contiguous evaluation orders and still be certain that we will generate optimal code. So, let us look at the algorithm now there are three steps in the algorithm the first step says compute in a bottom up manner for each node of n an array of cost c this is a very important probably the most important part of the algorithm. What does the array c contain c of i is the minimum cost of computing the complete subtree rooted at n assuming i registers to be available. So, if there are three registers available then this c will have four locations c of 0 cost of minimum cost of computing the entire subtree assuming 0 registers similarly c 1 would be with 1 registers c 2 contains the cost with 2 registers and c 3 contains the cost with 3 registers. So, 2 and 3 registers right then consider each machine instruction that matches at n. So, this is the way we compute c i and consider all possible contiguous evaluation orders using dynamic programming at the node n. So, and then add the cost of the instruction that matched at node n. So, this is the way to compute c i. So, we consider all possible orders then take the minimum and assign it to c i. So, we assume 1 register 2 register 3 registers etcetera say r registers which are available and then to compute the cost using you know into memory the cost of computing a tree into memory would be cost of computing the tree using all registers plus 1 which is the store cost. So, we do not have to do anything special compute the cost using 1 register 2 register etcetera of 2 r registers then fill up the cost of computing into memory by saying cost of computing the tree we using all registers plus 1. So, as I said this is the way we do it then once we do this when see store is over all the registers can be freed. Then using c determine the sub trees that must be computed into memory. So, that I mentioned then you know travesty and emit code. So, memory computations first and then the rest later in the order needed to obtain optimal cost. So, this is you know fairly straight forward as I am going to explain now the most important step is to compute this c. So, the sub trees with that must be computed into memory must be of the lowest cost otherwise we will compute it into registers rather than into memory. One trivial possibility here is the leaves which are already in memory the operands corresponding to the leaves will be in memory. So, computing something into memory in that case would be of cost 0. Whereas, computing it into a register means loading it into a register which is of higher cost here is an example. So, this is our tree right. So, there is a plus there is a minus there is a star there is a slash and these are the operands a b c d e which are in memory. So, as I already said the cost of computing a into memory will be 0 because it is already a memory operand the same is true for all the leaves b c d and d. So, remember the computation of c proceeds in a bottom up fashion. So, we do this then this then this then we do this we do this we do this then with this then this and finally this. So, that is the post order traversal of the tree that is the way we would do it. So, let us assume that there are two registers and it is a very elaborate to present the whole example. So, let us take node 2 and beat it to death find out all the details regarding the evaluation. So, node number 2 is here and in our instruction set that instructions which match at node number 2 would be r i equal to r i minus m with i equal to 0 and i equal to 1. So, that means, this right operand can be in memory, but the left operand must be in a register. We do not have instructions with both operands as in memory whereas, we definitely have instructions in which both operands are in registers. So, r i equal to r i minus r j i j both can be either 0 or 1. So, both of them can be in registers or left can be in register and right can be in memory. So, these are the only two types of instructions which match at node number 2. Obviously, this is the same for this as well now. So, we are going to compute c let us say let us call it as c 2. So, that we know that it is the cost at node number 2 with one register at two registers and then compute the cost of computing it into memory by saying it is 1 plus c 2 of 2 that is cost of 1 plus cost of computing it with two registers. Let us see how to compute node number 2 with one register. So, if we want to do that since the left operand is always in a register. So, we must look at the possibility of c 4 that is node number 4 with one register c 5 with 0 number of registers plus the cost of computing the root that is 1. This is the only possibility we cannot say c 4 of 0 because there is no pattern which matches here and once we have done c 4 of 1 we are left with 0 number of registers. So, saying c 5 of 1 has no meaning. So, it will be c 5 of 0 always of course, 1 is for the root itself. So, c 4 of 1 means it is a leaf node it is in memory. So, loading into a register will require cost 1 and that is trivial. So, that is so if we have a cost of 1 for an instruction of the type r i equal to m j then it would be 1. If we have a higher cost then that is the number which we are going to put here. So, this is what I meant when I said different instructions could have different costs as well. So, c 4 1 in this case is 1 it could have in 2 or 3 based on the machine. C 5 was 0 computing something into memory when it is already in memory is obviously 0 and we are assuming that minus requires 1 cost has cost 1. So, that would be plus 1 again. So, the whole cost is 2 it is more interesting to look at c 2 of 2 with 2 registers there are many possibilities. So, we have finished c 2 with 1 registers now we are looking at c 2 with 2 registers. So, we could evaluate this with 2 registers of course, evaluating this with 2 registers has no meaning you know 1 register is enough. So, the other would be just left as it is. So, whether we have 1 register or 2 registers the value will be moved into only 1 register. So, the cost will always be 1 with 1 register or 2 registers for this particular node 4. So, after c 4 of 2 we will be left with 1 register 1 register being used for node 4. So, c 5 can be evaluated with 1 register and then we have 1. So, c 5 of 1 means move it into a register and then 1 for the root this is common always right. Other possibility is c 4 with 2 registers c 5 with 0 number of registers just because we have a free register it does not mean we must use it. So, c 5 with 0 registers plus 1. So, these are the 2 possibilities with 2 registers now we look at the possibilities with c 4 using 1 register. So, c 4 1 then obviously, we would have c 5 2 plus 1 then c 4 1 plus c 5 1 plus 1 c 4 1 plus c 5 0 plus 1. So, these are all the possible ways of evaluating the tree with 2 registers right. So, the costs are this is cost 1 very obvious this would also be cost 1 because we want to move it into a register plus 1. So, 1 plus 1 plus 1 this is cost 1 this is cost 0 this is cost 1. So, 1 plus 0 plus 1 again this would be cost 1 this would be 1 this would be 1. So, 3 this would be 1 and this would be 1 and this would be 1 again 3 and the last one this would be 1 this would be 0 this would be 1. So, this is 1 plus 0 plus 1. So, the minimum of this would be really 2. So, cost of evaluating node 2 with 2 registers is also 2 it was 2 with 1 register and it is 2 with 2 registers also minimum cost well that is very intuitive because whether we use 1 register or 2 registers this requires only 1 register. So, and this is best in memory there is no point in loading it into a register and then using it. So, this cost is all is 2 even with 2 registers. If you want to store it back into memory then we need another extra cost. So, that would become 3. So, the triple for this node C 0 C 1 C 2 would be 3 comma 2 comma 2 and for the leaves it was 0 comma 1 comma 1 simply because it is already in memory. So, cost 0 whether we use 1 register or 2 registers it is always 1. So, all the leaves have the same triples this is very similar to 2. So, this also has the same triple then let us look at node number 3 this has 5 5 4. So, remember the cost here is 0 1 1 whereas, the cost here is 3 2 2. So, we could computing node with 3 with 2 registers let us look at that that is the most complicated case. So, we could do with left subtree with 2 right with 0 left subtree with 2 right with 1 left subtree with 1 right with 0 similarly, left subtree with 1 right with 1 left subtree with 1 and right with 2. So, in all these cases we can you know compute the cost. So, with 2 registers this would be 1 with 0 registers for node 7 it was 3 right. So, that is 3 and the root would be 1. So, this is 5 this would be again just a load. So, this would be 1 and this would be with 1 register that would be 2 here. So, this is 2 and then we have 1. So, this would be 4. So, similarly 1 and 0 would mean 1 plus 3 plus 1 this is next one would be 1 plus 2 plus 1 etcetera. The minimum value is 4 cost of computing with 1 register is very simple. So, this is 1 and 0. So, I have avoided writing it again. So, that would be 5 cost of computing into memory would be cost of computing with 2 registers that is 4 plus 1 that is 5. So, the triple will now turn out to be 5 comma 5 comma 4. So, it is more advantageous to evaluate subtree with node 3 into 2 with 2 registers rather than with either 1 or 0 registers. So, this is at the entire tree. So, annotated with the triples right. Finally, when we finished this route we would be left with the triple 8 comma 8 comma 7 and all others have already been evaluated. Now, the way we generate code we pick the component of the triple which requires minimum cost. So, in this case it happens to be the cost with 2 registers right. So, while computing the triple I must mention that we must keep track of the instruction pattern which actually uses that cost as well otherwise it is not possible to generate code. So, with this particular cost 7 the instruction pattern would have been r i equal to r j plus r i something like that. So, we can instantiate that with any registers assuming that there are 2 registers we have instantiated it as r 0 equal to r 1 plus r 0. So, the result this implies. So, this is the pattern which matches here and that is the least cost pattern it implies that the r s t would be computed into r 0 and l s t would be computed into r 1. The cost information should also be born in mind. So, this would be with l s t would be with you know the least cost would be again with 1 register and here the least cost would be with 2 registers. So, that is what is mentioned here then we go down. So, for node number 3 this is the one which requires higher number of registers. So, 2 registers so that is the one which should be dealt with first.  So, this is the least cost and l s t would be into r 0 then we go down further. For 7 we compute r s t into memory already available and l s t into r 1. So, the code generated would be in the other order.  So, once we have annotated the tree with all these instructions you know code generation would be very easy. So, annotation requires a top down traversal of the tree starting from the top pick the minimum cost then it will also tell you the pattern it will also tell you which particular register is to be used for the l s t and the r s t. So, there we again pick the number of available registers with minimum cost and the sorry the cost of evaluating the register the sub trees with minimum cost and so on pick that and go on doing that for the rest of the tree. So, the basic idea is when we start at the root we always follow the direction which you know the sub tree which requires more number of registers will be dealt with first. So, this information of which pattern matches there and what is the number of registers that is required for this pattern etcetera will have to be kept track of. So, remember that we have that information here you know c 4 with 2 registers c 5 with 1 register etcetera etcetera. So, we have one pattern for each of these that is possible and that pattern and the number of registers required for l s t and r s t will have to be maintained in separate data structures. So, that we can generate code you know we can cover the tree with the appropriate code during this pass and once that is over we could simply do a post order traversal and generate the code itself. So, the code that is generated is listed here. So, r 0 equal to so remember this is not the order in which we do it it is post order all right, but we will have to do the right sub tree first and then the right left sub tree and so on and so forth. So, r 0 equal to c so we have to follow the order in which we have generated code and that is the way in which we finally emit the sequence. So, we will stop here and continue in the next lecture. Thank you.