WEBVTT 1 00:00:50.969 --> 00:00:52.704 Professor, I think we lost your audio. 2 00:02:18.745 --> 00:02:20.185 Oh, okay. 3 00:02:21.414 --> 00:02:24.354 So, if people can hear me now, just a second. 4 00:02:25.830 --> 00:02:32.664 Okay, so maybe I'm not. 5 00:02:35.754 --> 00:02:49.675 No, okay because again, I can't have audio feedback if my audio feedback then occurs a second later and drives me crazy. Okay. Finally some quantum computing. 6 00:02:50.995 --> 00:02:54.175 Last six and first, 7 00:02:54.175 --> 00:02:57.145 some quantum computing and the news, 8 00:02:57.775 --> 00:02:59.905 a couple of stories IBM, 9 00:02:59.935 --> 00:03:04.794 which I think is doing a company strategy on quantum computing, 10 00:03:04.794 --> 00:03:06.115 although I don't know that. 11 00:03:07.229 --> 00:03:15.444 So they say they're really booting up. So here's a story. Just came out a couple of days ago you're free to click through and read it. 12 00:03:15.564 --> 00:03:22.735 There's some, it's also being reported in other places slash dog has assorted discussions on it and so on. 13 00:03:23.094 --> 00:03:33.564 So, currently they're at sixty five Cubics and they're moving out quickly and the dilution refrigerator is the thing that gets it down to. 14 00:03:34.884 --> 00:03:40.194 Like, fifty degree, Calvin, the way you get things extremely cold. 15 00:03:41.905 --> 00:03:55.194 Is you need some process some chemical or physical processes that, as it occurs, it absorbs heat and if it's absorbing heat in a closed system, it then lowers the temperature. 16 00:03:55.854 --> 00:04:07.074 And the easy thing is, of course, if you've got something that's boiling. So, getting things down to liquid nitrogen temperatures is easy. Boil that nitrogen to gaseous nitrogen that absorb heat. Get you down to that temperature. 17 00:04:09.534 --> 00:04:20.605 The next big temperature point would be liquid helium helium for and that oils that a couple of degrees. I don't know if four degrees Kelvin give or take. So you can get down to. 18 00:04:22.225 --> 00:04:29.514 The liquid helium, boiling liquid helium temperatures, but that's not nearly good enough. They wanna get another factor of one hundred or two hundred below that. 19 00:04:29.995 --> 00:04:37.675 And so other processes that you can get, which can get really cold are one involves using some farming that excelled. 20 00:04:39.295 --> 00:04:49.194 Some faults that are magnetic, and if you put them in a magnetic field, they align if it's like the crystals and you take them, you kill them analytic field. 21 00:04:49.194 --> 00:05:01.584 They, they go randomly and as a random they absorb some heat. So that's the way. So, when they align you, they get a little harder, you pull them down, then you miss. But that's not cold enough. 22 00:05:01.615 --> 00:05:11.845 What they're using is there mixing helium, three and helium four and is helium three goes in to mix it into the helium four. Then that absorbs heat and it gets the temperature down below. 23 00:05:11.845 --> 00:05:17.785 So that's the solution refrigerator, diluting one isotope of helium into another. 24 00:05:19.795 --> 00:05:29.725 It's all very inefficient terminal, so it takes a lot of energy to get that little thing in the center that cold, but it does remind a point helium. Three is expensive. 25 00:05:30.535 --> 00:05:37.855 So so there's another issue there but any case you can read about that. If you'd like. 26 00:05:44.725 --> 00:05:56.185 And the next okay, one, new store, another one is. 27 00:05:58.524 --> 00:06:09.954 Tech Crunch also is there's a number different startups in quantum computing, and some of them are probably solid and some of them a skeptical person might wonder if they're scams or not. Who knows? 28 00:06:10.464 --> 00:06:20.305 But any case, it's a very dynamic area, and you can look at this, and so quantum desktop computer you can upon looking at that. So, just current things in the news here. 29 00:06:21.504 --> 00:06:27.745 Now, a, my view of quantum computing is, I think the businesses have done it again. 30 00:06:27.745 --> 00:06:42.714 I think what we're seeing is a computing analog to atomic fission in the late thirties, early, nineteen forties led to the bomb and so this is not leading to a bomb, but it's leading to a total paradigm shift this time in computing. I could be wrong. 31 00:06:42.714 --> 00:06:47.514 Everyone says it over generalized, but it's possible. That's what was at the startup. 32 00:06:49.975 --> 00:06:59.454 Next thing useful books I recommended these two books here and by someone in the class and so you're free to look at those if you'd like. 33 00:07:01.134 --> 00:07:12.714 Okay, the next thing is on cloning and no cloning. I talked about it literally last time, but it's I think it's an important topic. 34 00:07:13.074 --> 00:07:19.495 And so I typed in some notes here to help you and if you have any questions, let me just. 35 00:07:21.264 --> 00:07:26.305 Okay, I'm trying to keep the chat window up here in case. Anyone would like to ask questions. 36 00:07:27.240 --> 00:07:27.689 Okay, 37 00:07:27.685 --> 00:07:32.454 so what's happening here and that in the classical world, 38 00:07:32.454 --> 00:07:32.785 you can, 39 00:07:34.074 --> 00:07:34.285 you know, 40 00:07:34.285 --> 00:07:36.295 kinda clone an output bit, 41 00:07:36.295 --> 00:07:41.245 and you get to output bits or ten output bits or whatever but in the quantum world, 42 00:07:41.425 --> 00:07:44.334 you cannot so doing here. 43 00:07:44.634 --> 00:07:48.504 So it's in the book. I took another take on expanded. It is that. 44 00:07:49.915 --> 00:08:04.045 The circuit that in the classical world would clone a bit does not clone a Cupid, but is working to here very quickly again. So we have a two bit system to input bits, X and Y, to output X prime Y, Prime. 45 00:08:04.524 --> 00:08:12.834 It's hard to see the prime sometimes and type script here and now so the obvious way you clone I mean, suppose you were assigned to job was cloning a bit. 46 00:08:13.225 --> 00:08:27.954 And two is, you just say Y, equals X, X, Prime, because X Y, Prime equals X and the clone sex and drops. Why and the truth table for. That is very simple here. X Prime is X. 47 00:08:27.954 --> 00:08:35.904 Y, Prime is also X. now, we've been looking at operations as matrix modifications, and they being multiplied by vector. 48 00:08:35.904 --> 00:08:50.664 Like, we have the up here at the top where if there's an variables, the this sector has two to the N entries, one for each combination of the variables. And so one entry is one and all the other entries. 49 00:08:50.664 --> 00:08:51.325 There is zero. 50 00:08:52.254 --> 00:08:53.965 And so if there's two variables, 51 00:08:53.965 --> 00:08:55.345 that vector will be for long, 52 00:08:55.644 --> 00:09:08.034 and the transformations are matrices to variable before by four and this is the matrix here that will do that classical clothing is matrices and classical operations was quantum. 53 00:09:08.394 --> 00:09:20.514 Okay. So the first thing is, you cannot use this as a quantum computation Matrix, because it's singular. It's got rows that are zero. The determine of this matrix is zero. 54 00:09:20.965 --> 00:09:33.774 So this is a known legal quantum transformation because quantum transformations are convertible except for the measurement things. So, this is not unitary matrix. It's determined zero, so we can't do that. 55 00:09:34.855 --> 00:09:45.835 So, the next thing is, is we take the Toffler gate possibly gate has three variables, three inputs in three outputs and it's a controlled not what it does. 56 00:09:45.955 --> 00:09:59.004 Is it invert the the Z X and Y are both true so that's would be the equations for it right there. I'm not gonna draw the gate. You can find it on page. Well, fifty six. 57 00:09:59.004 --> 00:10:07.134 Well, bringing it up just for fun here. And I'm right there. 58 00:10:07.495 --> 00:10:18.924 That's the standard thing three inputs. The outputs the little solid circle means that that line goes down and control something at the bottom. What controls the knock down there. 59 00:10:19.524 --> 00:10:28.495 Okay and this is the truth table here and this is the made. So, everything's the same except X. and Y, are both one, then it flips the. 60 00:10:30.565 --> 00:10:39.264 This is the matrix here? Three variables. It's an eight by eight matrix and it's mostly an identity matrix. It's at the lower right corner here. Okay. 61 00:10:39.264 --> 00:10:45.955 That's your journal and possibly get to the you mentioned the double control not now to do cloning with it. 62 00:10:46.105 --> 00:11:00.745 If we're classical, what we do is we lock, we lock X to be one and we lock Z to be zero and Y, is a free input and Y, will get cloned and disease on the output for this. If we, the next one. 63 00:11:00.745 --> 00:11:12.804 And Y, zero is that output for axes one Yeltsin for wise wind up with results twice. What it did is that we had a panel, it cloned why? It's in the classical state and this is the matrix here. 64 00:11:14.184 --> 00:11:22.345 So, the question is, what happens if we take this matrix and apply it to a Cupid I mean, it's a legal matrix. It's not singular. 65 00:11:24.085 --> 00:11:35.424 It's in versus it's transpose whatever it's, it meets all the rules being a unified unitary matrix. So this is a completely legal Walter matrix. Well. 66 00:11:36.445 --> 00:11:51.235 And then if we apply it to a, to a quantum, but it was a classical bit fine. But now what happens if we apply to a Cupid, which is actually some superposition of two different states and I'm gonna try it on is down here. Let me just pull up. 67 00:11:52.350 --> 00:12:06.205 Okay. Giving a chance to post for you to post chat questions. Okay. Well, let's pick why this I'm just a superposition of zero bit and one bit it's not even entangled or anything. 68 00:12:06.205 --> 00:12:10.735 It's a superposition to of too few bits way to equally. 69 00:12:11.725 --> 00:12:25.315 And this is why it's and if you combine with X and Z, this should be one possible rotation X one Y, zero zero X one Y, one zero and they're equally weighted. So square two. Okay. 70 00:12:25.315 --> 00:12:35.815 It's gonna have that as the end, but so it's a superposition of two input States and if we write it in that factor of a entries, this is how you would write it here. 71 00:12:36.870 --> 00:12:44.034 Okay, now let's do that. Let's take this vector of hate entries here and multiply by this matrix up here and see what we get. 72 00:12:45.120 --> 00:12:56.815 What we're gonna get is something, which boils down to this. It's a superposition of two states. A mix is still one, but we didn't clone you know, we didn't clone. 73 00:12:56.815 --> 00:13:06.835 Y, what happens is the output is a superposition of two different states and look, what happened is Z Z, doesn't clone Y, Z gets entangled with. Y. 74 00:13:07.855 --> 00:13:22.615 so, if you go and cause the proper cloning, the, the copying this, I know you've got two independent bits that start off with the same value. But there, if they're independent, that's the classical hardware. That's what happens. But in this quantum case, here, this is your output. 75 00:13:23.274 --> 00:13:36.294 So, Y, and Z are entangled their, you know, there, you know, that's the, that's the new thing. So it didn't clone why, you know, these are not separate. 76 00:13:36.325 --> 00:13:46.794 They're not copies of separate bits cause you can't that off you can operate on Y, Prime and Z prime separately. You operate on Y. Y Y, Prime, you now control Z because they're entangled. 77 00:13:47.784 --> 00:13:51.924 So, this is the thing is that you try to use a classical. 78 00:13:53.784 --> 00:14:04.164 Matrix to clone a Cupid and it doesn't work. Now, this is not approve. The cloning is impossible. Okay. That's a separate topic, which I could research if people want it. Okay. 79 00:14:04.735 --> 00:14:13.225 So back to the book up into chapter six now, and I can pull up. 80 00:14:14.580 --> 00:14:18.625 That's my book here, hold on chapter six. 81 00:14:21.384 --> 00:14:27.924 Algorithms order to go here. 82 00:14:29.095 --> 00:14:41.605 Oh, okay. And I've got my take on a summary of the thing here. Okay. So now we've learned how you can build quantum circuits with these quantum gates for a little mathematics and superposition entanglement. 83 00:14:42.024 --> 00:14:50.965 But now, how do we actually solve a problem? How do we do something? So, what this chapter does is it walks us through several algorithms. 84 00:14:51.264 --> 00:14:51.565 Now, 85 00:14:51.595 --> 00:14:52.254 the initial, 86 00:14:52.559 --> 00:14:54.174 the first couple of algorithm, 87 00:14:54.205 --> 00:14:55.764 the little toy things, 88 00:14:56.335 --> 00:14:57.565 they do something, 89 00:14:57.565 --> 00:15:02.245 but they do something extremely simple and they show you some of the ideas, 90 00:15:02.784 --> 00:15:04.434 but later on in the chapter, 91 00:15:04.434 --> 00:15:09.235 we'll get into two algorithm distracts so useful grover's algorithm. 92 00:15:09.264 --> 00:15:09.804 And. 93 00:15:11.274 --> 00:15:12.865 And the algorithm, 94 00:15:12.865 --> 00:15:14.965 the factor algorithm is actually, 95 00:15:17.095 --> 00:15:17.335 you know, 96 00:15:17.335 --> 00:15:18.654 eventually will be what, 97 00:15:18.684 --> 00:15:19.375 the idea, 98 00:15:19.404 --> 00:15:26.365 the way that a lot of public key criticisms could be broken if impact it can be run on bigger examples. 99 00:15:27.115 --> 00:15:35.424 Okay. And so, these quantum algorithms, they're not all like, the classic dog, and they're completely different. 100 00:15:36.054 --> 00:15:36.294 So, 101 00:15:36.325 --> 00:15:41.424 the current research is try to find other allegory, 102 00:15:41.455 --> 00:15:52.554 classical algorithms problems that I can find quantum algorithms to solve these classical problems where the quantum algorithm is faster than the classical method. 103 00:15:52.554 --> 00:16:06.715 And that's current research. Because the what people figure is, you can make something faster on a quantum computer, but not everything. No. Another thing is what, all these algorithms are doing and I got it posted here they're searching algorithm. 104 00:16:07.254 --> 00:16:22.134 They're searching for an answer and the searches difficult, but in most cases, once you have an answer, once you have something that claims to be an answer, it's really easy to validate it. 105 00:16:23.184 --> 00:16:37.345 So let's take the prime. The factoring a number. Yeah, you have a thousand digit number it's currently practically impossible. In fact, at least that's what people believe. Now. 106 00:16:37.884 --> 00:16:39.355 Now there is this, you know. 107 00:16:40.164 --> 00:16:54.325 Past Square, mile, building, outside, salt, Lake City and Utah, and maybe inside that building. They compactor these thousand digit numbers, but they're not talking about it. If they can that the building would be owned by no such agency. Of course. Okay. 108 00:16:56.095 --> 00:17:06.025 They do. Sometimes. It is known that they sometimes lead the public, stated the yard. I'll give you an example. Two decades ago. Ibm proposed a. 109 00:17:07.289 --> 00:17:10.375 Suppose de, crypto system and. 110 00:17:11.845 --> 00:17:23.964 It it had a well, fifty six bit keyboard. Plus eight check fits. So fifty six but that's obviously today but it was a reasonable crypto system for a while. 111 00:17:24.744 --> 00:17:26.125 But the thing was, 112 00:17:26.305 --> 00:17:27.535 this IBM CRP, 113 00:17:27.535 --> 00:17:39.025 the system proposal is after it had some permutation and selection boxes in it that were that were for mute the bits and to Boolean operations on the bits, 114 00:17:39.025 --> 00:17:42.744 and then promote them again and combine them in some random. 115 00:17:42.744 --> 00:17:56.305 Wait. So, these, these permutation boxes, or picked well, no one knew how IBM pick them they published what these, what these boxes of not making these numbers it published what these make. This is horrible. 116 00:17:56.305 --> 00:18:06.565 They didn't say how they decided them now, after a number of years a technique was discovered to crack this class of cypher's. 117 00:18:07.315 --> 00:18:15.744 And people wondered if IBM some, you know, cipher was vulnerable to this class. 118 00:18:16.194 --> 00:18:31.105 As the pricing thing was, the IBM cyber was surprisingly resistant to this class of attacks. I mean, you know, people think there's a secret backdoor vulnerability. 119 00:18:32.035 --> 00:18:34.315 This was a backdoor increased security. 120 00:18:35.069 --> 00:18:39.535 And so the obvious conclusion, or they know that had help with the, from the and designing it. 121 00:18:40.375 --> 00:18:54.535 What people assumed was that the had discovered this new cracking technique many years earlier just not talked about it and had helped design IBM system to be resistant to this attack that was not publicly known 122 00:18:55.345 --> 00:18:56.724 so that's approved sunrise doing things. 123 00:18:56.724 --> 00:19:07.075 Ahead. So, maybe they can track big numbers, big Pactiv, big numbers, but we don't know how to so, that's enough of a search procedure. Oh, okay. So getting back to. 124 00:19:10.375 --> 00:19:22.105 To this end, let me scroll through and use figures from the book mostly either needed. In my hand writing I got the pad in front of me if you want, but okay. Well, maybe I'll draw a little. 125 00:19:22.914 --> 00:19:26.365 Let's see here we have the pad. 126 00:19:27.835 --> 00:19:28.494 Okay. 127 00:19:32.875 --> 00:19:35.035 Review six. 128 00:19:38.940 --> 00:19:44.035 Okay, so this is the, the Jorge algorithm. 129 00:19:45.954 --> 00:19:50.125 Idea is that we have a, this is some box here. 130 00:19:53.035 --> 00:19:55.825 And the thing is. 131 00:19:57.204 --> 00:20:08.545 We cannot look inside, but we can run it. 132 00:20:10.109 --> 00:20:13.704 Okay, a second here. 133 00:20:17.634 --> 00:20:22.525 Okay, okay. 134 00:20:23.785 --> 00:20:29.454 Okay, so we have the black box. We can all look inside it, but but we can run it. 135 00:20:30.325 --> 00:20:42.474 And now what we want to do is what's inside the box now so, you know well, it's not one input. It's one it, you know, we are one cubic. 136 00:20:42.505 --> 00:20:52.644 We initially I'm one, but I'll start classical then I'll get comfortable. So we can say, you know, we can evaluate the so we can evaluate that. 137 00:20:54.684 --> 00:21:02.454 And now, you know, we know if completely okay we just on that one. Okay. 138 00:21:04.914 --> 00:21:16.015 But what we want to do is instead of asking, what is f, a zero and what is f of one we want, I want to ask a different question. 139 00:21:26.755 --> 00:21:31.855 I want to ask basically. 140 00:21:38.605 --> 00:21:40.315 Is f, balanced. 141 00:21:44.154 --> 00:21:51.684 Or is it constant as one bit of info there? Okay, two choices. 142 00:21:52.589 --> 00:22:06.984 That's one bit of info. Okay. To be there. Okay. Balanced means it's one half the time and zero half the time and constant means. 143 00:22:07.494 --> 00:22:21.924 It always gives the same output. Now, we do, we do have one zero. We have one, we can determine that, but that takes two evaluations. So, the classical thing. 144 00:22:24.450 --> 00:22:28.345 It takes two about. 145 00:22:30.444 --> 00:22:35.184 We're gonna see a quantum thing, a quantum thing. 146 00:22:37.944 --> 00:22:45.055 Needs only one. Yeah, so this will be so the dosage algorithm. It's a really simple thing. 147 00:22:45.055 --> 00:22:59.365 This is one bit black box and by evaluating it once we'll know if it always gets the same output or if it gives or it does not. 148 00:22:59.394 --> 00:23:13.585 These two things are exclusionary actually. Exactly. One of them is true. In this one case. So what this will be is an example of an algorithm where the quantum version is faster than the classical version. 149 00:23:13.974 --> 00:23:26.005 The classical version, you have to evaluate this black box twice the quantum version we will have to evaluate it only once whoever with the quantum version we're sending in a cube, but not a bit. 150 00:23:26.335 --> 00:23:28.345 So we're actually at this doing more work, 151 00:23:28.375 --> 00:23:28.855 because, 152 00:23:28.884 --> 00:23:29.154 you know, 153 00:23:29.154 --> 00:23:29.305 it's, 154 00:23:29.934 --> 00:23:30.144 you know, 155 00:23:30.144 --> 00:23:31.494 instead of operating on one pit, 156 00:23:31.494 --> 00:23:33.595 it's operating on a, 157 00:23:34.075 --> 00:23:34.494 you know, 158 00:23:34.884 --> 00:23:35.515 one Cupid, 159 00:23:35.515 --> 00:23:36.055 effectively, 160 00:23:36.444 --> 00:23:37.255 one degree of freedom, 161 00:23:37.255 --> 00:23:42.115 a complex number what to but you normalize it to have a constant magnitude. 162 00:23:42.115 --> 00:23:46.315 So that's one now. Okay, so that's so, that's the point to this. 163 00:23:47.035 --> 00:23:59.964 So now it's very simple, but the point is, when you get up to bigger examples, grover's algorithm cuts, number of evaluations from and down to square root event, and that's worth doing. Oh, okay. 164 00:23:59.964 --> 00:24:03.265 So, let's let me go back to the book and see what it's doing here. 165 00:24:04.194 --> 00:24:11.904 Okay, so there's a one bit algorithm. Oh, they've got this nice little summary up at the top here. How things work this is how they all work. 166 00:24:11.934 --> 00:24:20.545 Basically, you initialize here quantum computer with some unit size cube bits with some classical values. 167 00:24:20.545 --> 00:24:33.595 Each Cupid is zero or one, and then you run the head of Mark Matrix on the inputs, and that mixes them up to now the inputs instead of each and Cupid instead of being a classical zero or one. 168 00:24:33.835 --> 00:24:38.755 It's now a superposition of various of zero and one so it mixes things up. 169 00:24:39.714 --> 00:24:51.144 And we may mix up different que, bits and tangle them. And then we start then we apply a matrix and, I mean, all these operations can be composed into one making. 170 00:24:51.144 --> 00:25:03.835 So we apply one matrix to the state factor, the state Federal Institute of the N entries. We apply one matrix and all the work is, it will upset one matrix and then we measured the output. 171 00:25:04.434 --> 00:25:16.224 Okay so that is your general? No questions. Okay. So this is your general idea here and the question is so all of the complexity is hidden and line three there. 172 00:25:16.494 --> 00:25:19.944 Okay so we're back to this example the one bit Blackbox. 173 00:25:22.134 --> 00:25:36.174 There's four different ones, either four different possibilities outputs. All zero outputs always won. Those will be the constant ones. Are errors the identity, or it's the negation. Those are the balanced ones. 174 00:25:36.984 --> 00:25:40.765 Okay. Just a second here. Oops. 175 00:25:45.150 --> 00:25:45.954 That's weird. 176 00:26:09.805 --> 00:26:10.644 You just cut out. 177 00:28:15.835 --> 00:28:20.994 How's it now? Good. 178 00:28:21.809 --> 00:28:27.894 Okay, thank you. I don't know. This is why people go into theories that I have to work with real computers. 179 00:28:28.680 --> 00:28:32.875 Too much hardware in front of me clashes with itself. Okay. 180 00:28:33.085 --> 00:28:45.295 So what I'm talking about here is the, the problem we got the simple one bit function, and it's got four possible functions, and we're gonna divide in two case of balanced case. 181 00:28:45.954 --> 00:28:59.845 Where will be the two middle ones, identity integration, and yet to outside ones are constant. And what we want to do is which of these two groups of cases, is the function in and what to determine was one of evaluation. 182 00:29:00.595 --> 00:29:14.664 Okay. Talking here away. If you have any function on X, you can make it in verbal convertible by adding control line. Why? So now there's one more input and now this combo is its own inverse. 183 00:29:14.664 --> 00:29:28.315 You apply it a second time and it now, it cancels itself out. Okay. I want to, but I wanted to give you the idea, and I'll skip through the various ways of getting up to the idea. 184 00:29:31.315 --> 00:29:32.184 Okay. 185 00:29:35.305 --> 00:29:38.875 And this is what we're doing. 186 00:29:43.315 --> 00:29:45.595 What we're doing is that. 187 00:29:53.424 --> 00:30:01.134 I don't want to get to the answer here and okay, so here's the final answer. 188 00:30:04.944 --> 00:30:15.144 This is our black box function here with one more input added so it's a controlled to each function. So you got two inputs the bit. 189 00:30:15.174 --> 00:30:21.684 That is the input to the function and and then one more control bit. 190 00:30:22.795 --> 00:30:30.174 So we start off with the two bits being classically zero and one, we rotate each of them once I had a mark function. 191 00:30:30.174 --> 00:30:30.295 So, 192 00:30:30.295 --> 00:30:30.474 again, 193 00:30:30.474 --> 00:30:31.224 with that with the H, 194 00:30:31.224 --> 00:30:32.214 Matrix does, 195 00:30:32.849 --> 00:30:38.815 is it who did it takes this bit, 196 00:30:38.815 --> 00:30:47.154 which is just zero state and rotated to be a superposition of the zero and the one state with equal probabilities and for the second. 197 00:30:47.154 --> 00:30:53.035 But then we apply it to the to the black box control control, 198 00:30:53.424 --> 00:30:54.835 black box and again, 199 00:30:54.835 --> 00:31:04.045 the control bit does complicated things when it's a Cupid and then we take the X output and we rotate it again. 200 00:31:04.375 --> 00:31:15.984 And it was matrix. And then we measure and this measurement here well, it'll give us one bit of information and it will tell us what type of Blackbox we have inside. 201 00:31:17.545 --> 00:31:24.085 I'll go through the details more on on Monday. I so I'll do today is I'll hit you with an executive summary. 202 00:31:24.505 --> 00:31:34.404 So this so this is the quantum algorithm that tests that was one evaluation of half will tell you if is constant or not. 203 00:31:35.339 --> 00:31:38.275 So, I'll go through the math. 204 00:31:39.115 --> 00:31:42.805 What we're showing here is various states here, 205 00:31:42.805 --> 00:31:44.664 the initial state of the system, 206 00:31:46.255 --> 00:31:54.835 and then the initial status size zero after the two had in mind agency side one after the controlled f function here. 207 00:31:54.835 --> 00:31:57.384 And then we rotate again. 208 00:31:57.384 --> 00:32:11.065 We get to so what's happening it is this and initially we said what this line here, it says zero and why one and if we go back here, that's what we wanted one. Okay. 209 00:32:11.700 --> 00:32:20.605 And besides zero is zero inside one. And then we apply the had a margin matrix here. 210 00:32:21.295 --> 00:32:30.654 The two of them, the syntax here is a touch, take some thinking actually. So he has a column and here, it's an order pair of those two. 211 00:32:32.125 --> 00:32:46.224 What we have here is a combo, the two, the first head of our matrix applies to the first cubic. The second header Martin matrix applies to the second to bed here. 212 00:32:46.224 --> 00:32:52.914 So these are, you're applying to the two different Cubics and the second head of mind matrix. 213 00:32:52.914 --> 00:33:03.115 Has a minus there so you apply this up here at line six, thirty, and you get equation six thirty two which is this so we've now. 214 00:33:04.644 --> 00:33:12.835 We've now mixed up the, for each of the foreign put States all with the same probability of one quarter. Okay. That's after. Mixing them up. 215 00:33:15.085 --> 00:33:20.035 Now, what we do is that we apply the controlled f box. 216 00:33:21.474 --> 00:33:24.984 And there's some work going on that I skipped over, 217 00:33:24.984 --> 00:33:28.164 which says a control f boxes essentially doing that, 218 00:33:28.704 --> 00:33:37.585 and we apply it and I'm waving my hands and skipping through stuff. 219 00:33:40.795 --> 00:33:41.785 We will get this. 220 00:33:43.525 --> 00:33:53.845 So, now, how what happened now, is that this is after the control f, Box, is that we've now separated out the two cases, the two outputs. 221 00:33:56.154 --> 00:34:00.085 Differ depending on a path is constant balance and that's nice. 222 00:34:02.244 --> 00:34:14.755 Now we take the top Cupid and we can, we apply the head of our matrix again and we'll get this and these two are. 223 00:34:17.940 --> 00:34:29.364 These two what happens is that if it's constant, you know, put bid is a zero. If it's one, the output bed is so is the one. 224 00:34:30.264 --> 00:34:41.034 So so we've done is we've got a system now, which with one evaluation of half will tell if it's constant or. 225 00:34:42.355 --> 00:34:45.474 Balanced so it's a simple little. 226 00:34:46.349 --> 00:35:00.894 Problem what's inside that black box, but we now have a quantum algorithm and it's faster than the classical algorithm classical took two balanced in this case means that it gives zero half the time and one half the time. 227 00:35:01.704 --> 00:35:08.454 So it means said it's the identity in this particular case. It's not constant. So. 228 00:35:20.034 --> 00:35:30.655 Balance means zero half the time and one half the time for outputs. So so I ways my hands didn't go through the details of the math. 229 00:35:30.655 --> 00:35:43.195 I may hit the math and I touched more detail on Monday or your free over the weekend since I, since I hope by now, you understand what it's doing you can run through the the details and see how it's doing it. 230 00:35:45.625 --> 00:35:58.735 Any questions for? No, and one way, you could think how it works is, it's the app is operating on a cubic not a classical bit, so it's a lot more work there. Okay. 231 00:35:59.664 --> 00:36:06.744 Next one is an extension of this called Josh. Let me pop up my notes here. 232 00:36:07.679 --> 00:36:15.775 Okay, so Josh, we have N, two bits input. 233 00:36:16.945 --> 00:36:20.304 And one output, so it's a function on in bits. 234 00:36:21.655 --> 00:36:35.155 Classical, your Cupid quantum leap and in this case we are told that f is either constant or balanced here is a third possibility. It could be nicer, but we're told no, so constant means f, gives the same output. 235 00:36:35.724 --> 00:36:43.375 Regardless of the input balanced means it is eight zero, half the time and a one half the time. 236 00:36:45.655 --> 00:36:55.135 So, and if it gives a zero more than half the time or less than half the time, but not all the time, and that's not allowed. So well, these two case constants and now. 237 00:36:56.335 --> 00:37:05.394 Okay, so how often do we how many times do we have to evaluate app to determine which it is? We're told it's one of those two. 238 00:37:06.264 --> 00:37:16.764 Well, if we evaluated and over to plus one, we can tell, because if it's constant those, then over two, plus one valves have to be the same. 239 00:37:18.565 --> 00:37:29.065 If they're not the same then we know it's balance because that's the only only other possibility. So, classically we need an over two plus one evaluations of half. 240 00:37:30.059 --> 00:37:44.664 quantumly, how you tell me what adverb you want me to use here? quantumly we need only one evaluation of that and some other works. 241 00:37:44.664 --> 00:37:50.005 So the Jocelyn algorithm it's and then over to speed up. 242 00:38:08.755 --> 00:38:09.534 In any case. 243 00:38:12.954 --> 00:38:20.364 So, what we're going to do is up here, we've got X as and bits. We add a control bit. Why. 244 00:38:21.715 --> 00:38:30.144 And so, now, this use of f box, it's f, wrapped around with the control bed and this is what the output is. So it's in vertable. 245 00:38:32.094 --> 00:38:39.594 But, classically, we got to run it in over two times. quantumly. We'll run it ten times. One time. 246 00:38:41.485 --> 00:38:55.315 Oh, here's an example of a balanced function. It's got two inputs, so there's four here and so it gives us zero twice in a one twice here. 247 00:38:56.094 --> 00:39:08.094 Well, this is okay and we can represent it with this matrix. What we did is we added the control bit. Here is now we've got three inputs and outputs. So this is a matrix here. 248 00:39:09.594 --> 00:39:22.824 That would be a balanced function and another balanced one. Okay. I'll skip through the details to show you what the answer is. Oh, okay. Let me just do the matrix here. This is here. 249 00:39:24.445 --> 00:39:35.605 Two by two. You can build up four by four and eight by you by any of those if you're into image processing, you know, this thing start looking, like, discreet Co, signs image compression and all that fun stuff. 250 00:39:36.565 --> 00:39:49.105 And well, it's the same actually, just in a different domain. So, two by two, and you recurs your four by four by eight and so on, and just some interesting rules for there. 251 00:39:49.105 --> 00:39:53.755 So proof by induction in whatever K. 252 00:39:56.335 --> 00:39:56.545 Is it. 253 00:40:00.059 --> 00:40:04.045 Okay, so that's what it looks like. 254 00:40:08.065 --> 00:40:12.025 And what it will do, is it well. 255 00:40:13.224 --> 00:40:22.704 Stuff up, and now with the derivation here so what the, the textbook is doing is, it's going through the thing piece by piece. 256 00:40:23.695 --> 00:40:29.184 Simple thing that doesn't work just mix up the control bit with with H. 257 00:40:31.525 --> 00:40:38.425 It's not gonna be enough and goes through the math that's mix up the and inputs that we care about with H, 258 00:40:38.425 --> 00:40:39.085 like this, 259 00:40:39.594 --> 00:40:47.394 and then mid age and do the same thing on the output here and go through the math. 260 00:40:49.315 --> 00:40:55.315 And and it turns out that the first pitch. 261 00:40:56.304 --> 00:41:01.315 Of the output, so the output existent and bits if we look at the first bit of that. 262 00:41:02.635 --> 00:41:12.175 Is our answer, I mean, measure to collapses down to one bit, and it will be different, depending on his balance. So. 263 00:41:13.644 --> 00:41:19.914 I may crunch through some math on Monday, maybe, but but basically the executive summary. 264 00:41:21.565 --> 00:41:24.835 Is that we had this end bid back box function? 265 00:41:26.244 --> 00:41:32.364 It was restricted to be either constant or balance, but we don't know which that's one bit of information. We want to know. 266 00:41:32.364 --> 00:41:36.505 Is it constant or bounce one bit of information and with this, 267 00:41:36.534 --> 00:41:36.894 we, 268 00:41:37.135 --> 00:41:49.405 we determine that one bit of information with one evaluation of that and the way we do it is we wrap it with a control bit and then we rotate the and inputs. 269 00:41:49.675 --> 00:41:54.414 We rotate to control, but we, we run the control Daft. We rotate the. 270 00:41:56.005 --> 00:42:09.565 And but output, we don't care about the output of the control bit, and we measure the first bit and that measurement will tell us. Is it constant or balanced? So I'll crunch the math on Monday and you can also look at that. Okay. 271 00:42:10.344 --> 00:42:11.364 So that is. 272 00:42:13.525 --> 00:42:16.824 That's a second algorithm for I know. 273 00:42:19.405 --> 00:42:29.125 Okay, next thing is, I want to hit you with again executive summary. I'll hit some math the executive summaries today says I started late and Matt on. 274 00:42:32.065 --> 00:42:41.034 Math on Monday, third, one, Simon's curiosity algorithm. Now this is getting a little more complicated. 275 00:42:41.034 --> 00:42:49.375 Now, this is doing something that would be useful and factoring large numbers figure out how later. So we got a function. 276 00:42:55.405 --> 00:43:04.135 It out this time, now, the thing with f is that if we take the input, there's an unknown secret. 277 00:43:05.545 --> 00:43:09.715 Bit string call it see and we don't know what it is, 278 00:43:09.715 --> 00:43:22.405 but it's built into f and the thing was this bit string is that if we take the input and zower it with the secret string then f thousand the output doesn't change. 279 00:43:23.574 --> 00:43:23.994 Now. Why? 280 00:43:23.994 --> 00:43:24.474 It's called, 281 00:43:26.574 --> 00:43:30.295 is that if we were doing something more complicated, 282 00:43:30.295 --> 00:43:30.474 like, 283 00:43:30.505 --> 00:43:31.764 adding an integer, 284 00:43:32.155 --> 00:43:33.414 if this was the case, 285 00:43:34.105 --> 00:43:39.985 then this would mean f was periodic periodic function like sign of access. 286 00:43:39.985 --> 00:43:42.715 Not the two Pi to X output stays the same. 287 00:43:44.034 --> 00:43:58.315 Well, here, we're not working with real numbers were working to submit string and instead of actually adding, we're doing exclusive boring. So, exclusive or are we exclusively or this secret. 288 00:43:59.699 --> 00:44:02.545 Period to the input and it doesn't affect the output. 289 00:44:04.559 --> 00:44:11.394 Okay, our problem is to determine the period to see. 290 00:44:12.775 --> 00:44:20.664 Okay, now, if you think about how you would solve this classical basically, what would you do? 291 00:44:22.795 --> 00:44:25.554 Well, you value a job enough apps. 292 00:44:26.574 --> 00:44:41.184 Oh, by the way this partitions, the set of inputs into two into two classes actually, this f now is a two to one function after possible outputs occurred twice the other half the possible outputs never occur. 293 00:44:42.085 --> 00:44:45.385 Okay. So now. 294 00:44:47.184 --> 00:44:57.594 If you were given this on or something, and had to solve it well, you might I'm just gonna try f on lots of inputs on zero one, two, three, four, five or something. 295 00:44:57.594 --> 00:45:03.684 And if I ever and remember all the outputs and look for duplicates, and as soon as I get a duplicate bang, I know. 296 00:45:03.684 --> 00:45:15.985 See, and if I try a half, plus one to the N O, over to minus plus one inputs and I never gonna duplicate that. 297 00:45:15.985 --> 00:45:28.255 I know it's not periodic that the content is zero and so okay. That's the classical method. And the quantum method is fine. Okay, this is an example here. 298 00:45:28.644 --> 00:45:32.545 The secret string is one one, one, zero one and. 299 00:45:34.255 --> 00:45:47.514 Hi to all eight inputs is what we get. Excuse me half the inputs occur half the outputs occurred twice. Like, one on one is the result of zero, zero, zero and the result of. 300 00:45:51.534 --> 00:45:59.125 And should be the result on. 301 00:46:06.025 --> 00:46:06.954 Wherever it is. 302 00:46:10.199 --> 00:46:18.264 So, make something weird happening here worry about that later. Oh, okay. 303 00:46:22.585 --> 00:46:24.175 So, we're going to do is. 304 00:46:51.835 --> 00:46:54.264 And to discover, see. 305 00:47:09.835 --> 00:47:16.885 Easy summary of the celebrates, and it has a quantum problem that has a quantum algorithm attached in the classical algorithm. 306 00:47:18.594 --> 00:47:22.014 Okay, and the leader tip, this idea works it's going to factory. 307 00:47:24.894 --> 00:47:32.394 Okay, I want to tell you what grover's search algorithm is and. 308 00:47:42.744 --> 00:47:53.065 Okay here we got a black box f and inputs one output. Another thing is that with f one so there's two to the basically. 309 00:47:55.405 --> 00:48:07.644 The rules are only one input is one and all the rest or zero, and for one particular input put is one otherwise it's zero and the question is determine which input. 310 00:48:08.784 --> 00:48:15.474 So, the rules are you only allowed to have one input, but being one, and then minus one or zero if that's not followed the output is undefined. 311 00:48:16.675 --> 00:48:19.704 Okay, so which input that causes the output to be true. 312 00:48:21.534 --> 00:48:24.804 Classically you gotta test all of the bits and minus one of the. 313 00:48:32.994 --> 00:48:34.164 By putting. 314 00:48:48.625 --> 00:48:51.355 Oh, so button. 315 00:49:02.969 --> 00:49:03.264 You know, 316 00:49:03.264 --> 00:49:04.164 research and all goes 317 00:49:19.284 --> 00:49:20.244 into your algebra. 318 00:49:22.255 --> 00:49:31.074 Suppose you have a matrix and you want and the largest Ivan value Matrix, but sparse or something maybe. 319 00:49:33.085 --> 00:49:37.375 Set a number of eigen values, but it's got a large one. Do you want to find one thing you can do? 320 00:49:38.695 --> 00:49:51.204 As you can take the matrix and look at the, 321 00:49:53.425 --> 00:50:01.795 the more you isolate the largest and what happens here with this algorithm again, 322 00:50:01.795 --> 00:50:03.144 I'm waving my hands, 323 00:50:03.175 --> 00:50:09.804 but they're running a matrix the number of times and everytime you run it. 324 00:50:10.105 --> 00:50:20.304 It increase. It tends to isolate the correct answer more to put. This will be a probabilistic algorithm. We haven't seen the probabilistic algorithm before it will tend to give you the right. 325 00:50:21.715 --> 00:50:22.405 And the more you're. 326 00:51:10.614 --> 00:51:18.684 Oh, okay. 327 00:51:31.914 --> 00:51:32.184 Well. 328 00:51:52.585 --> 00:51:54.804 As a good weekend flow your. 329 00:52:13.079 --> 00:52:22.164 Professor, it's kinda chopping on land your audio. Okay. Yeah. I'm also getting I was worried that was my Internet, but. 330 00:52:24.204 --> 00:52:31.045 A little late, but, yeah, it just it was happening at the variance now. Yeah only the last couple of minutes. 331 00:52:34.199 --> 00:52:38.275 Yeah, alright, thank you. Hello. Okay. 332 00:52:39.534 --> 00:52:43.105 Yeah, thank you. Yeah. 333 00:52:45.355 --> 00:52:53.454 The speak up, you know, it's just technical problem. So this week. 334 00:52:54.960 --> 00:52:57.204 You know, so I just so I can fix them. 335 00:53:03.210 --> 00:53:11.965 Okay, so anyone want to talk to me about research or anything. 336 00:53:19.704 --> 00:53:28.554 If you're curious. What I had is I doing video from a laptop by doing audio from a Bluetooth headset into my phone and calling into WebEx with their phone number. 337 00:53:29.574 --> 00:53:42.295 Which, in theory should have been better quality because even the, it's not even using my WI. Fi. Of course, it's going a straight from the phone up to Bryson. So it's a separate band. 338 00:53:42.894 --> 00:53:45.175 The theory is that being an audio band, it's. 339 00:53:46.590 --> 00:53:50.065 Possible to make it higher quality because it's, you know, fewer bits. 340 00:53:51.445 --> 00:54:03.954 Well, then just Syria in this practice. So, I mean, yeah, it's clear right now. So I guess it's just, I don't know what I did. Oh, okay. I picked up the phone and held it. I held the phone up. 341 00:54:06.505 --> 00:54:16.704 Now. Horizon says, you know, there's a couple of bars. Okay. That's saying, I'll try to get closer to the base WI, Fi, base station or something. 342 00:54:19.349 --> 00:54:32.244 Okay questions or no, well, if anyone, you know, other than that, like I said, have a good weekend, I'll stay around for a few minutes in case. People have questions. So.