Something very important. This abstract says a lot. Contrary to what you probably heard, quantum computers are not faster than classical computers. So, everyone opens a newspaper, you read about quantum computers and quantum computers are doing this and they're going to revolutionize the world, etc., etc. It's not true, okay? It's simply not true. The power of quantum computing is that the quantum algorithms demand fewer operations than classical algorithms. In other words, what can be done with a classical computer, the algorithms demand less, which means that the center, the core, the most interesting thing is the quantum algorithms, not the machines. The engineers will take care of the machines, don't worry about that. As programmers, as developers, I thought you would be interested in that. Okay, this makes quantum algorithms fundamental in quantum computing. We will introduce a touch of quantum mechanics, three or four slides, and then the basics of quantum computing, three or four slides. With that in hand, we move on to discuss several of the most important quantum algorithms. We conclude with some speculations about the future of quantum computing. So, it's a short talk. Again, quantum mechanics, quantum computing, then here's all the seven algorithms and then the post-quantum world. First, quantum mechanics. So there's two ideas in quantum mechanics that you have to know that are fundamental and they explain why quantum computing is so good, okay? And they have to do with two experiments, and I'll explain the experiments. So this is Feynman, Richard Feynman. He's a famous physicist. He wrote a book called *Lectures on Physics*, volume three is all about quantum mechanics. Page 101, that's the first page in the 400-page book. He says this line: "We choose to examine a phenomenon which is impossible, absolutely impossible to explain in any classical way, and which has in it the heart of quantum mechanics. In reality, it contains the only mystery." So what I'm going to say is literally the center of quantum mechanics. We cannot make the mystery go away by explaining how it works. We will just tell you how it works. Okay, so that's that. And the mystery is called the double-slit. The experiment is called the double-slit experiment. Double-slit experiment. If you've seen it, you've seen it. So basically, you have a light and the light goes through a wall and there's two slits. Okay, there's two slits in the wall. And one of the slits, if you block it, then the other slit, think of lights as waves. The waves go through and the waves are going to make a lot of white over here. It's going to be dark over here. It's going to be dark over here. It's going to be a little gray over here and a little gray over here because the waves go and they come right over there. That's if you have a single slit. What happens if you have a double-slit? In other words, we take away this block. What's going to happen, okay? And what's going to happen is the light's going to go and it's going to go through both slits. And it's like waves, literally like waves in the ocean. And what you're going to have is something like this, okay? And when you have waves, if you throw two pebbles into a pond, some of the waves are going to cancel each other out, okay? Sorry, I got to put this away. And so I have to do a dance, you ready? So sometimes you're going to have waves like this, they're together. And in that case, you're going to have very bright shades over here and over here. But sometimes you're going to have shades like this, up and down, up and down, up and down. They'll cancel each other out. And they cancel each other out means there's not going to be light here. There's not going to be light here. There's going to be a lot of light here, a lot of light here, and a lot of light here. So, this is different than you would expect. You would think, "Oh, there's just a lot of light across from it." No, they cancel each other out. Okay, now that's that just means that light's a wave. But let's go further with this. Light can be thought of as a wave, and the waves from each slit cancel each other out. The interference, so one interference with the other, leads to light and dark patches. Physicists can do this experiment with one photon at a time. If this is done many times, many of the photons will land in light regions. None of the photons will land in dark regions. So, think of a photon as a little light atom and you let it go one at a time. And you want to know, does it, when does it go through here? Does it go through here, okay? And what they say is as follows. If there's only one photon at a time to let go, is if there's only one photon let go at a time, what does the single photon interfere with? You have to see a picture, okay? So here's, here's the light source and it's going through like this. You would expect some light goes here and you're going one photon is going out at a time. You would expect some go here and some go there, but that's not what happens. What happens is this is what's observed. And again, you have some bright patches where lots of light shine up and you have some unlit patches where no light shows up. Now you say to yourself, "I don't understand. If you tell me light is a wave, so fine, the waves cancel each other out. But if you tell me light is a photon, and you let out one photon at a time, who's it canceling out with?" Okay. And we go back here. Here's the answer. And this is the core of quantum mechanics. The photon splits into two and interferes with itself. It does not go through either this slit or that slit. It goes through both slits at one time. Rather than saying it has position, say it has superposition. Now, this is where you say, "I don't believe it." And you're allowed to say you don't believe it. This is where you say, "Oh, this is where it's not true." And a lot of people didn't think it's true. A man named Albert Einstein didn't think it's true, and a man named Schrödinger didn't think it's true, but it's true, okay? The photon goes through both slits at one time. This superposition is what's used in quantum computing. Okay, let me show it to you in a second. In quantum mechanics, many properties, not just position, not just is it going through this slit or that slit, but many other things, things called spin, energy, momentum, do not have a single value. Rather, they have many values. They're in a superposition. When they are measured, when you look at it, they are only seen in a position. Why this happens is called the measurement problem. So, the reason why you don't believe in superposition is because you've never seen it, except if you drink a lot of tequila. Drink a lot of tequila and you can see quantum physics working. Okay? The point is, when you're a conscious human being or a conscious animal, I don't think any animal's ever seen a superposition. It's never seen it. So that's a question: why does that happen? Why is something in a superposition and then when you look at it, it collapses? So that's called the measurement problem, and people argue and discuss it, etc., etc. But it is, but it's a fact. Okay. So, before it's measured, it has many values. It's going through this slit and it's going through that slit, okay? This is the main use in quantum computing. This is the main and so, so I just want to spend a minute here. For example, we're all programmers. We all know how to search for something in an array, right? How do you search for something in an array? Okay, you look at this position in the array, you look at that position in the array, you look at the third position in the array, etc., etc. You go through the array one at a time. Okay, now here's, here's the trick of quantum computing. Rather than looking at one position at a time, go into a superposition and look at all the positions at the same time. Okay, that's what quantum computing is all about. You use this fact that things are in a super- can be put into a superposition in order to get this massive parallelism. Okay. So you have to, so this is what quantum computing is all about, and it is a history about it. I don't want to get to the history. I don't want to get into how the engineers are doing it. I want to get to the algorithms, okay? So one of the things, the main special thing about quantum mechanics that's used for quantum computing is this superposition. There's another thing called entanglement, and I'll show you what that's about, okay? So there are particles, there are things and they spin. Some of them spin. They spin positively or they spin negatively, and some don't spin at all, okay? So, think of a basketball. Some things spin this way. Some things spin that way. Some don't spin at all, okay? And what you could do is as follows. Here's an experiment. You have a thing that lets out photons or you let out any particles going like this. And you put it between two magnets, and you allow the photons to go through. Now the magnets make some type of field, and sometimes you're going to see that some of those particles go straight. That means the magnets don't have any effect on it. So we say those particles don't spin. As opposed to that, sometimes they spin this way, and sometimes they spin that way. They never spin in between. It's either positive, negative, or zero, okay? This is a, this is a fact about particles. Okay. Now sometimes you can have a big particle that can decay. So you have like X-rays, they decay, they fall apart, and they fall apart into two different, smaller particles. And these smaller particles do have spin, okay? Now there's two possibilities. This one can spin positively and this one can be spin negatively. They have to both spin opposite. Why? Because there's something called conservation of spin. You have conservation of mass. No new mass comes. Conservation of energy, conservation of momentum, all these conservation things. What that says is that in the universe things don't change that much. So if you start off with spin zero and one of them spins positively, the other one's got to be spinning negatively, okay? Great. Or this one could be spinning negatively and that one has to spin positively, okay? Now hold up, you ready? Something else can happen here too. Not something can happen, something else happens. Let's say this decays and no one's looking at it. There's no measurement going on. No one's checking it out. Then what's happening? Then what happens is this one particle splits and sometimes this spins positively, sometimes it spins negatively. It spins both positively and negatively. It's in a superposition of spinning. Again, you don't believe in superposition, so I'm trying to get you to believe in this thing, but you don't believe in that. You're a bunch of heathens. Anyways, what it does, it splits, okay? And they spin in superposition. But here's the amazing thing, you ready? Let's say I take this, I take this particle. I put it in a box and I it splits into two other boxes. No one looks at it. And I take this particle and I send it to Alpha Centauri. Alpha Centauri is a star that's millions and millions of light years away. It's the closest star to our star, okay? It's millions of light. And this one I keep here again in a box. Don't look at it. Because if you look at it and you're not drinking tequila, if you look at it and you're not drinking tequila, you'll see it either spinning this way or spinning that way. Okay, I don't want to look at it, okay, good. Now, I have my box, my box with a particle in it. It's spinning this way and that way. That particle is spinning is in a star far, far away and it's spinning this way and that way. Now, one day, a Sunday night, I get bored and I decide to open the box and look. Now, I could see it spinning positively or I could spin, see it spinning negatively, right? But here's the amazing thing. The law of conservation of spin says if this is spinning positively, that one all the way there, millions and millions and millions of light years across the universe has to stop being in a superposition and spin the opposite way of this. Because it has to be like that. That's, as my mother says, "That's the way it is. That's the way the universe is," okay? So this is the amazing thing. The amazing thing is if you look at this one, that one, and it's spinning one way. That one has to spin the exact opposite way even though it's millions of miles away, okay? Now you're shaking your head. You don't believe it because you're a bunch of heathens, okay? I want to tell you something else. Somebody else who didn't believe it, Albert Einstein, okay? He didn't believe it. He used to call it "spooky action at a distance." He said this is spooky. He made fun of this. He said this is spooky action in a distance. He says it doesn't make sense. He invented relativity theory. Thank you, Ma. He invented relativity theory. And relativity theory says things far away don't affect each other. So how could this be? How could it be that, well, I look at this and I see it spinning one way, that's spinning the other way. That stops being in a superposition and go like that. He didn't believe it. But it's true and it's used in quantum computing. Okay. So let's just talk about how it's used. Quantum mechanics entanglement. Entanglement is not just a quirky quantum phenomenon. It's a fundamental resource that allows quantum computers to perform computations in fundamentally different and more powerful ways than classical computers. Because the results of measurements are entangled like this, even though they're far away, it's not really far away, but they're just entangled like that. It is what allows the creation of correlations between qubits. I'll talk about what that is. And to give you a computational advantages, it is what allows for the manipulation of quantum information in ways that lead to exponential speedups in certain algorithms. And we're going to go to those algorithms in a minute, okay? So those two things, superposition and entanglement, that's what gives you the power of quantum computing. Great. So now let's do, let's talk about quantum computers. So we finished our quantum mechanics. You did quantum mechanics in five minutes. Quantum computing is like this: here's a classical bit. This is a computer. It's made out of a lot of bits. What do the bits do? They're either zero or one, okay? Now, then you can get into something called probabilistic bits. Things like fuzzy logic or AI type stuff where things are a little bit zero, a little bit one here and there. Then comes quantum, quantum stuff, and this is called a quantum bit. And what you can be is you can be in, you ready, a superposition of zero and one. Not a little bit zero and a little or a little bit one. You can be in both at the same time, okay? So let me show you how that works. That's, that's using this superposition not for, for on qubits, on bits. So again, I don't want a bit that's either zero or one. I want a bit that's both, in some sense, okay? A bit is either zero or one. Switch on is off. So again, we know what a bit is. We deal with it. Electricity flowing or not flowing through a transistor, a metal ring magnetized one way or another way, okay? So that's what a bit is. A qubit is a little bit zero. I'm sorry. It's zero. This is a complex number and one at the same time. And these complex numbers, C0 and C1, C0 tells you the chances that after measuring in the qubit, it will be found in zero, and C1 tells you the chance that it will be found in one, okay? So again, we're using this concept of superposition on a bit. No more are we going to have a switch either, either on or off. We're going to have a switch that's both on and off at the same time, okay? What happens if you have two, two qubits? Well, if you have two qubits, when you measure them, you have two possibilities of what you're going to see: 00, 01, 10, 11, okay? Great. I want to put two bits in a superposition. So then you have this. You have some complex number telling you what's the chances of being like this. Some complex number telling you what's the chances of it being zero and one. Some complex number telling you what's the chances of it being one and zero and one one again. When you have four, two switches, you have four possibilities of where those switches could be, and we want to be in a superposition of all four at the same time. For a system with N qubits, let's say I have, there's no switches in this room, let's say I have N switches or N bits. Then there are two to the N possible ways that can be found after measurements. So let's go through it. One qubit can be in one of two ways. Two qubits can be one of four ways. Three qubits can be one of eight ways. N qubits can be one of two to the N, okay? To describe N bits, you need to describe N bits, regular bits. You need N bits. I want to say, okay, here's the state of, here's N switches. I want to describe it. I can say 101101. That's N bits that give you the thing. To describe N qubits, I need two to the N complex numbers, because I need the numbers to tell me to what extent it's this, to what extent it's that. So that gets already complicated. Let me tell you why. Okay, this exponential growth, you need two to the N qubits complex numbers, was one of the ideas that Feynman, that got Feynman interested in making quantum computers. Feynman said, "If you want to mimic a quantum system, you better have a quantum computer." The idea is as follows. Every modern computer has at least 64 bits. Every computer is a 64-bit computer. Imagine a 64-qubit computer, okay? That would demand that many complex numbers, okay? This computer, as good as it is, cannot deal with that math. Not even any, no computer in the world can deal with that. So it's hard to mimic a quantum computer with a classical computer, because you need a lot of numbers to deal with it. So you cannot mimic it for anything bigger than 10 qubits or something like that. You cannot mimic it. You need, it needs too much resources. That's more than, that's a lot, okay? Hence, it is impossible to mimic a large quantum computer with a regular computer, okay? Great. This is talking about the states of the system. So, a quantum computer is going to be made out of these qubits. And to describe them, we need a lot of things, but we don't, we want to use them without describing them. Hold on. Okay, great. How about a, how about dynamics? How do computers change? So, here we have a computer and what's inside? We have lots of different logic gates. If you've seen it, you've seen it. If not, not. Most of our computers are made out of NAND gates, okay? Because NAND gates can give you everything else. That's fine. And we build circuits with these NAND gates. We, with these things, we build very nice, nice circuits. And basically, we have bits coming in here, and we make adders, and we say, if he presses control and he presses E at the same time, exclusive OR, not that, etc., etc. We can do that. And basically, programs are like this. You use your ALU. You have your bits coming in and you have your bits coming out. And that's what a computer program is. Great. That's for a classical computer. I'm not interested. I'm interested in quantum computers, okay? In a quantum computer, qubits are manipulated by things called quantum gates. I'll show you what they are in a second. A quantum program is going to be a composition of quantum gates. Show you in a second. Usually, we're going to be start. Okay. So, let me just get to the picture. Okay, I'm going to go through this a little bit faster because my attention deficit disorder is starting to kick in. But basically, what you're going to have is this is going to be a typical quantum program. Okay, an algorithm. Okay, again, the qubits start out over here. Okay, and they go through these. Each one of these boxes tells it a different thing to do. Okay. And at the end, oh, so hold on. These H's, they stand for Hadamard. They put things in a superposition. So what did I say? What's the, what's the, what's the power of quantum computer? The power of quantum computing is you start off, you go into a superposition, and you try to do everything at one time. That's exactly what we're doing here. We start off, and we put everything with these H's, put things in a superposition, and then we do different operations to them. At the end, we have to measure them. So that's a meter where we measure them, which means we have to collapse, we have to collapse the superposition. We need to get results, okay? And so this is what a typical quantum computer would look like. Of course, I have to explain to you what these operations are and how they change the qubits, but this is exactly what it does, okay? And it's, and it's, it's very nice. By the way, you can start doing quantum computing tonight. First thing, go buy this book, okay? It helped me pay my mortgage for a Brooklyn house. Ready? Anyway, so this will help you do it. It's a very good book, etc., etc. But IBM is very much into educating quantum computing, and so they have a thing called Qiskit, quantum information system kit. You can literally type in Qiskit, and you can make your own account, and you can start programming with this. It's not just an online quantum computer. It's, it's, they have videos and they have explanations, etc., etc. And you can with like scratch, you can say, "Okay, I want an H gate over here. I want to put this gate over here. I want to do this or this," okay? And then you can actually run the program, and you're not running a simulation. This is the amazing thing. IBM has, what you do is you set up your, the way your circuit, you want your circuit to be. And you wait a little bit until they have a quantum computer ready. They upload it to them and they actually run it on a quantum computer, not a classical computer, okay? And you can, you can really do this tonight. It's really, it's an amazing thing and you can, you get it. Um, so this is the IBM experience, whatever, it's, it's a very nice trick, okay? Great. Again, I skipped over a lot of details and I'm going to skip over a lot of details because we're not interested in how they build quantum computers. We're interested in the algorithms, okay? So the algorithms, here's a cute algorithm. It's by a guy named David Deutsch, and it was one of the first algorithms. It goes like this: Deutsch's algorithm deals with a function from one bit to one bit, okay? In other words, it inputs zero or one and the output is zero or one. Now, if you think of it, there are four such functions. Let's go through it, you ready? F of zero could be zero and F of one is one. So everything just goes the, the identity. Or zero goes to one, one goes to zero, or everything goes to zero, or everything goes to one. Those are the four functions you have from a bit to a bit, okay? The problem asks whether the following thing. Let's say I give you a box and I say it does, you input a, you input a 0, 1 here, you output a 0, 1 here. And I want to know the following question. Is the function in this box, it's a black box, you can't, you can't look inside, is it constant, which means F of 0 equals F of 1? Both the outputs go to zero or both the outputs go to one, or is it balanced, which means F of 0 is not equal to F of 1? So is it 0 goes to zero and one goes to one, or is it 0 goes to one and one goes to zero? They're not, the outputs are not equal. That's one question I ask. So again, you're given a black box and you want to know is it constant or balanced? Okay, so let's go through it. Classically, this demands two function evaluations. How would you do this? We're all programmers, how would you do it? You have a box, you can plug in zero or one here, and you can get out 0, 1 over there. How do you tell is it constant or balanced? And the answer is very simple. Plug in zero, see what the result is. Plug in one, see what the result is. If the results are equal, bingo, it's constant. If the results are not equal, it's, it's balanced. Finished. Okay. So, you need two function evaluations. I have a pretty picture for this. You start off with no information. You plug in F of zero and you could either get out one, zero or one. You plug in F of one. The next one. And here you say F of 0 is zero. F of one is one. It's a constant. They both go to zero. Here you say F of 0 is zero. F of one is one. It's balanced. Here you say F of 0 is one is one. F it's balanced constant. So there's the four possibilities. And what you say is okay, these two are constant. These are balanced. I can answer the question. But I have to run it twice. I have to put data in twice. Great. With a quantum computer, this problem can be solved with one function evaluation. I don't need to do it twice. I can do it once. That's a speed up. It's not a very interesting speed up, but it's a speed up. Instead of running the algorithm the box twice, I run the algorithm once. Okay. And this is somewhat of the algorithm. Basically, you put things in a super. Oh, how does it work? Very simple. Put it in a superposition. Don't put in into the box zero and then put in one. Put in zero and one together at the same time. Okay? And then you're going to get out some result. And we're going to have to do some, we're going to have to mush some of the results, whatever. But I only have to do it once. And I get out a totally good result and, um, and, and it works. Again, it's not very interesting, but and you'll see we'll, we'll get to the more interesting things to it. Okay, so that was called distinguishing constant and balancing. Now, we're going to do generalized distinguishing. Here's, it's called the Deutsch-Jozsa. Deutsch was a, was a guy and Jozsa is another guy. Same Deutsch, but different Jozsa. Okay, so it's as follows. Instead of dealing with a function from zero to one, deal with a function with N bits go in and one bit goes out. So you have that box and instead of putting in one bit, you put in N bits here. Okay? And you will get out like that. And you ask the same question. Constant, does the same output for all, there's two to the N inputs. There's two to the N strings of length whatever. Okay. Does it, is there one, uh, is it constant or balanced? Anyways, constant and balanced. We'll do this quickly. Classically, this demands two to the N about half of the evaluation. So, you have to do it until you see if there's any differences. If the all, if all the inputs are always outputting zero, then you know it's constant. If all the inputs are always outputting one, you know it's constant. But it could be half and half. And so you might have to do it a lot. Great. Classically, this demands 2 to the N minus one function evaluations. With a quantum computer, this can be done with one function evaluation. So you don't have to do this box 2 to the N thousand time, two to the N times. You can do it with one. Bomb. That's amazing. How do you do it? Put it in a superposition. Put the input in a superposition. You're going to get out an output, etc., etc. Okay. Um, let me, we'll do this quickly. So here's the AND operation. Okay. One, one AND zero is zero. One AND one is one, etc., etc. Zero AND one is one. Okay. Consider the following. Okay. Now look at the parity of this result. Zero or one, even or odds. Okay. I'm going to go through this a little bit quickly. Um, so here's the thing. Take two strings, do the AND of both of them, and then take the parity. What the par basically is telling you is, is it odd or even the amount of times they're both one? That's the question. Okay, good. Let S be a secret binary code. Consider the following black box function. Again, takes in N things and outputs 0, 1, defined as F of X is equal to parity of S of X1. Okay, so there's a secret code and you input X and you do AND of it and then the parity of it, doesn't matter. Okay, here's the problem. Given such a function, find the secret S. Okay, and there's a way of doing it. Okay, here I show you how to do it. You need N function evaluations with a quantum computer. You can do it with one function evaluation. Very nice. Okay, um, I'm going to do Simon's algorithm a little bit faster. Simon's algorithm is another thing that's faster. All of these are strange problems. They're just not interesting problems. You're saying, "Oh, if you can you do this balance, it just doesn't show up often." But here is the interesting problem. Okay, these three are very interesting problems and we'll go through this. Finding a needle in a haystack. This is the main thing. It's called Grover's algorithm and the idea is as follows. What does it mean to find a needle in a haystack? How do you find a needle in a haystack? The phrase, where does it come from? Well, if you have a haystack and you know you lost a needle in it, how do you find it? The only way to do it is a brute force search. Pick up this piece of hay. No, that's hay. Pick up this piece of hay. No, that's hay. Pick up this piece of hay. No, that's hay. Okay, you're going to have to do it over and over and over. It's not very interesting. It's not very effective. Okay, so that's called finding a needle in a haystack. Let's see what a quantum computer can do better. Okay, this is very important. This algorithm, Grover search algorithm, deals with a function. Again, it has 2 to the N possible inputs, N bits. Okay, we are assured, promised that there's exactly one X such that F of X is equal to one. In other words, you have a haystack of two to the N pieces of hay with one needle in it. And what you want to do is go through the things very, very quickly. Okay, go through the things very, very quickly and find that one needle. So you're assured, you're promised that for one of them, one of the inputs, the output will be a one. Everything else, the output will be a zero. So you're actually doing a search algorithm. Again, when I'm searching, I'm searching. There's a person in this room named Anzeroot, right? That's you. I could tell your father's from Memphis. He was a T. He was a great man. Anyways, so I knew that because it was on the list, whatever. But the point is, how do I find this person? Are you Anzeroot? Are you Anzeroot? Are you Anzer? Are you etc., etc., etc., etc. Okay. Until I see a guy who looks like his father. Okay. Anyways, so um, you do it with one. Great. How does Grover's algorithm work? It puts it into a superposition. It doesn't take one output. It doesn't do, you can't do it with one. Classically this demands two to the N function evaluations. With a quantum computer, this can be done with square root of 2 to the N evaluations. That's a tremendous speed up. Not a polynomial, not very good, but that's a tremendous speed up. This algorithm is the one that's used all the time in quantum computers. Okay. Uh, I'm sorry, not all the time, a lot of the time. The point is it's a way of finding things quicker, quickly. So you have some, um, uh, chemical thing, you have some DNA stuff that you want to search for very quickly, you have some folding mechanism, etc., etc. You have some stuff that's working on Wall Street to find some nice database something result. Searching for things is very quick. It does it a lot quicker than anything else. Okay, most quantum algorithms use this algorithm. Notice the speed up does not take an exponential 2 to the N to a polynomial problem. That doesn't happen. But it takes it from, from 2 to the N to square root of 2 to the N which is a tremendous speed up. Um, it's smaller. Okay. Great. Okay. Next most important algorithm is Shor's algorithm. Okay. And I'll tell you why this is important. Okay. It's very easy to multiply large numbers. Here's a large number. Here's a large number. You can multiply them and you get out a large number. In contrast, multiplication of two N, of two N digit numbers and N squared. In contrast, given a large number, how can you factor it? Factor a large number. That's a very hard thing to do. And that's a very good thing. That's a very hard thing to do. I'll tell you why. Because when you put in your credit card information to your Amazon, right? And you put in your, it's hidden with something called RSA. It's hidden with RSA. And the RSA uses that, RSA algorithm uses the fact that it's hard to factor numbers in order to keep things hidden. For example, you have a credit. What's your credit card number? Sometimes that works. Okay. Damn. Okay. No laughing next time. All right. Anyways, you ready? That's what would happen. You take the credit card, the computer manipulates the credit card number so that only Amazon can read it and only they can check it. Okay, so it's hard to factor numbers. Okay, how do you factor numbers? We're programmers. How do you factor numbers? Well, you divide it by two, see if it goes in. Divide it by three, see if it goes in. Divide it by four, see if it goes in. Okay, and you got to do this till square root of N. That's a lot of work. Okay