WEBVTT 1 00:03:28.530 --> 00:03:33.120 Silence. 2 00:03:33.120 --> 00:03:36.569 Silence. 3 00:03:36.569 --> 00:03:40.229 Silence. 4 00:03:43.650 --> 00:03:46.919 Silence. 5 00:03:49.919 --> 00:03:55.979 So, good afternoon class. 6 00:03:55.979 --> 00:03:59.159 The quantum computing class 24. 7 00:03:59.159 --> 00:04:04.050 April 22nd 1. 8 00:04:04.050 --> 00:04:08.490 And I kind of see where the chat windows go. 9 00:04:12.990 --> 00:04:21.060 Okay, now you issue all question can you hear me. 10 00:04:21.060 --> 00:04:27.778 And see my screen. 11 00:04:27.778 --> 00:04:34.348 Thank you Jack. Okay. 12 00:04:34.348 --> 00:04:41.098 So, I can't use the headset because I want to show videos and then it gets a little messy doing. 13 00:04:41.098 --> 00:04:47.939 Audio can hear, but no screen yet either. Okay. 14 00:04:47.939 --> 00:04:51.119 Um. 15 00:04:51.119 --> 00:04:59.608 Try sharing just a window instead of the whole screen. Sometimes. I think it's Webex is overloading. Actually. 16 00:04:59.608 --> 00:05:11.189 How does that work? 17 00:05:11.189 --> 00:05:14.278 Okay, I'm sharing just the 1 screen. 18 00:05:14.278 --> 00:05:17.369 So. 19 00:05:17.369 --> 00:05:27.028 Some deliverables for the course I've been having homeworks throughout the semester, had great scope things to submit the 1st few, but not the last few. So. 20 00:05:27.028 --> 00:05:36.538 I've added great scope. I've added great scope things so that you can submit the other homeworks. 21 00:05:36.538 --> 00:05:44.759 Project presentations last 3 classes. Please email me with your preferred dates. 22 00:05:44.759 --> 00:05:48.209 And based on past history. 23 00:05:48.209 --> 00:05:52.048 Probably everyone gets their 1st choice, but, um. 24 00:05:52.048 --> 00:05:57.689 If you don't do it by Monday after the Monday class, I'll just assign dates. So. 25 00:05:57.689 --> 00:06:10.108 And Monday, I progress report is due since I didn't email, I didn't actually supposed to ask you to email me your names and titles last time in your report, include your names and titles. 26 00:06:10.108 --> 00:06:22.738 Okay, so what's happening today is mostly talking about algorithms and so on shore's factoring algorithm which factors. 27 00:06:22.738 --> 00:06:34.254 An editor, this is the thing that made quantum computing, I guess, catch people's attention, because that's the basis of a large class of public systems. 28 00:06:34.913 --> 00:06:48.084 So I've got some I'll show you some. It's a very difficult topic. I mean, I don't completely understand it myself, but I'll show you some, I'll give you a sense of it was shore himself for 2 minutes. 29 00:06:50.363 --> 00:07:04.043 Is an excellent speaker. It's a 25 minute thing. I'll show it unless everyone asks me to stop it at some point in the middle. I think it's worth watching it doesn't even give the whole topic, but it will give you a deep sense of how the thing operates. 30 00:07:05.218 --> 00:07:10.649 Now, I have a longer 1 for Abraham asked file from IBM Yorktown. 31 00:07:10.649 --> 00:07:19.348 I'm not going to show it, but it's it's a series age and this is number 7 in the series and IBM is as part of their. 32 00:07:19.348 --> 00:07:28.168 Quantum computing kit and so I will not show this. I'll show another thing show some other stuff. 33 00:07:28.168 --> 00:07:36.509 Right, I guess I'll show you some of it perhaps depending and then and point you to the rest of it. 34 00:07:37.343 --> 00:07:47.153 And actually know that I won't trust not enough time and then another algorithm is solving system engineer equations. 35 00:07:47.483 --> 00:07:55.134 And I'll give you a sense of it just a quick 5 minute introduction to it and not show you the longer thing. So. 36 00:07:55.408 --> 00:08:07.168 I'll go back to my quantum summary page with some stuff added talking about some different technologies. Um, some of the 3 major technologies, we may not get to all of this today. In fact, we probably will not. 37 00:08:07.168 --> 00:08:10.288 But this will. 38 00:08:10.288 --> 00:08:13.798 Let us see here, start. 39 00:08:13.798 --> 00:08:21.983 But it'll give you a sense of some algorithms and some technologies, and we'll continue on on Monday you have progress reports written. 40 00:08:21.983 --> 00:08:33.443 It's not thing I'll introduce you to a TV show you how to use quantum simulator, submit jobs and talk about some middle Ware for quantum computing and so on. 41 00:08:33.719 --> 00:08:38.489 And then Friday, to the extent, it's not taken up by talks to them. 42 00:08:38.489 --> 00:08:42.028 1015 minute time saying. 43 00:08:42.028 --> 00:08:46.739 You know, 5 talks a class is reasonable. I think. 44 00:08:46.739 --> 00:08:51.089 So, the question is, does this. 45 00:08:51.089 --> 00:08:56.339 This the sharing. 46 00:08:57.599 --> 00:09:01.048 It is apparently okay, so. 47 00:09:02.129 --> 00:09:11.038 I want to make this full screen, which means that it's just see if I can call up a, um. 48 00:09:11.038 --> 00:09:15.479 Something else on the iPad. 49 00:09:15.479 --> 00:09:19.589 Okay, just a 2nd here and we'll see it. 50 00:09:32.729 --> 00:09:35.729 Okay. 51 00:09:49.408 --> 00:09:53.788 Let's see, it's not working. 52 00:09:57.058 --> 00:10:02.548 Yeah. 53 00:10:06.808 --> 00:10:18.899 Sure. 54 00:10:18.899 --> 00:10:23.278 If this works okay. 55 00:10:33.803 --> 00:10:45.114 It's such a stupid thing, but if I run, if I use my iPad to connect to Webex, also, I cannot mute. The sound volume in the 2 devices is tied together. 56 00:10:45.114 --> 00:10:50.303 It's not possible for me to mute the sound in the iPad and not the sound. 57 00:10:50.609 --> 00:11:01.769 On my laptop, they'll figure really the volumes link together in any case. So I make this full screen. I can't see the chat window so it is a problem then unmute yourself. 58 00:11:01.769 --> 00:11:11.428 Okay, so we'll see 2 minutes on chores summary it's good to see the people involved. And then the longer thing on. 59 00:11:11.428 --> 00:11:18.089 Give you, which will be at the very long thing, 25 minutes or so getting into shore in more detail. 60 00:11:19.198 --> 00:11:24.239 Let us see here. 61 00:11:26.399 --> 00:11:41.339 Yeah, sharing stopped. 62 00:11:41.339 --> 00:11:44.999 Is that how it completely changed? 63 00:12:23.068 --> 00:12:25.673 Uh, professor, I don't think we can see the screen yet. 64 00:13:04.254 --> 00:13:06.083 It seems like you're muted as well. 65 00:14:15.538 --> 00:14:22.019 Professor, we can hear you. Yeah, I. 66 00:14:23.214 --> 00:14:24.354 Think he's restarted. 67 00:15:25.948 --> 00:15:34.649 Can you hear me now? Thank you. Okay, that was 1 more thing I had to unmute and do. 68 00:15:37.403 --> 00:16:54.203 Eva. 69 00:16:58.558 --> 00:17:08.278 Okay, I'm on coming in from the iPad now my laptop just locked out and I would have had to go in remotely rebuild it in order to get things um, operating. 70 00:17:08.278 --> 00:17:13.648 So, I can run something from here. 71 00:17:29.608 --> 00:17:35.818 Can you hear me now? No. 72 00:17:35.818 --> 00:17:41.878 Thank you Isaac. Oh, great. Okay. Part 1. now let's see if I can get video going. Um. 73 00:17:59.759 --> 00:18:44.519 Silence. 74 00:19:27.144 --> 00:19:31.044 Okay, um, let's see if you can see the, um. 75 00:19:31.318 --> 00:19:41.009 Screen no audio. 76 00:20:15.659 --> 00:20:24.449 Silence. 77 00:20:31.348 --> 00:20:36.388 Silence. 78 00:20:36.388 --> 00:20:57.538 Silence. 79 00:20:58.979 --> 00:21:08.459 Silence. 80 00:21:15.959 --> 00:21:39.719 Silence. 81 00:21:39.719 --> 00:21:56.578 Silence. 82 00:21:59.429 --> 00:22:13.169 Silence. 83 00:22:21.479 --> 00:22:35.098 Silence. 84 00:22:35.098 --> 00:22:47.729 Silence. 85 00:22:58.439 --> 00:23:11.249 Silence. 86 00:23:11.249 --> 00:23:25.318 Silence. 87 00:23:26.939 --> 00:23:33.148 Silence. 88 00:23:49.558 --> 00:23:56.999 Silence. 89 00:23:56.999 --> 00:24:02.999 Okay, I'm approaching a solution. I'm on another I. 90 00:24:02.999 --> 00:24:06.689 I'm coming in on another laptop, so. 91 00:24:06.689 --> 00:24:10.469 Let's see what happens here. 92 00:24:14.009 --> 00:24:21.209 Silence. 93 00:24:32.338 --> 00:24:36.148 Silence. 94 00:24:39.929 --> 00:24:48.989 Silence. 95 00:24:50.608 --> 00:24:56.098 Silence. 96 00:25:00.179 --> 00:25:06.209 Silence. 97 00:25:15.479 --> 00:25:21.749 Silence. 98 00:25:23.128 --> 00:25:27.058 Time. 99 00:26:19.229 --> 00:26:22.858 Take the number factor, and her. 100 00:26:22.858 --> 00:26:27.989 Is a commentary the problem probably affects the periods of oxygen. 101 00:26:27.989 --> 00:26:31.618 You use. 102 00:26:31.618 --> 00:26:35.038 As competition in the broader. 103 00:26:35.038 --> 00:26:39.148 So try to find. 104 00:26:39.148 --> 00:26:42.989 It gives you a pattern which tells you the space of the grading. 105 00:26:42.989 --> 00:26:47.459 So, we have a periodic, but. 106 00:26:47.459 --> 00:26:51.028 Information to a competition, which gives you. 107 00:26:51.028 --> 00:26:54.628 And once you have the, you can. 108 00:26:54.628 --> 00:26:58.348 Possible compare. 109 00:26:58.348 --> 00:27:04.259 Silence. 110 00:27:04.259 --> 00:27:07.378 Silence. 111 00:27:10.348 --> 00:27:14.128 Silence. 112 00:27:16.888 --> 00:27:20.969 Silence. 113 00:27:23.128 --> 00:27:26.189 Silence. 114 00:27:26.189 --> 00:27:32.278 Okay, now it's good. Let's try this again. 115 00:27:32.278 --> 00:27:35.759 1 of the things I find fascinating that 1. 116 00:27:35.759 --> 00:27:39.148 Is that how it completely changes the fields. 117 00:27:39.148 --> 00:27:43.679 Classical information and classical coming. 118 00:27:43.679 --> 00:27:47.759 For instance, there are problems that you can solve on a quantum computer. 119 00:27:47.759 --> 00:27:51.028 In many, many fewer steps, and you can solve. 120 00:27:51.028 --> 00:27:55.618 Classical and 1 of these is the factory. 121 00:27:55.618 --> 00:28:00.088 Which can be solved in roughly and. 122 00:28:00.088 --> 00:28:03.509 Time on the computer where at. 123 00:28:03.509 --> 00:28:07.798 The number of fits to the number 1 a factor, but it takes. 124 00:28:07.798 --> 00:28:11.009 Exponentially a long time when a single computer. 125 00:28:12.838 --> 00:28:15.989 So, how does it 1 computer. 126 00:28:15.989 --> 00:28:20.009 Well, it's essentially because it's experience instead of events. 127 00:28:20.009 --> 00:28:24.568 Which either be 0 or what. 128 00:28:24.568 --> 00:28:29.699 Why don't you theater, which are system. 129 00:28:29.699 --> 00:28:34.169 To either 0 or 5 of our supervision. 130 00:28:34.169 --> 00:28:37.348 I think also and tackle. 131 00:28:37.348 --> 00:28:41.098 I can interfere with each other. 132 00:28:41.098 --> 00:28:46.259 All the properties of why so. 133 00:28:46.259 --> 00:28:49.679 The way the quantum factoring works. 134 00:28:49.679 --> 00:28:53.128 It's. 135 00:28:54.838 --> 00:28:58.229 Take the number might be faster and quicker. 136 00:28:58.229 --> 00:29:03.628 Is it number 3 the problem a problem with the period of a billing problem? 137 00:29:03.628 --> 00:29:07.259 And then you use. 138 00:29:07.259 --> 00:29:10.648 As a competition in the. 139 00:29:10.648 --> 00:29:14.398 So, try Mike's when you're ready. 140 00:29:14.398 --> 00:29:18.328 Pattern which tells you spacing of the grant. 141 00:29:18.328 --> 00:29:21.538 So you have a number. 142 00:29:21.538 --> 00:29:25.348 Information you a communication. 143 00:29:25.348 --> 00:29:29.068 Which gives the parent, and once you have the. 144 00:29:29.068 --> 00:29:33.209 Classical computers. 145 00:29:33.209 --> 00:29:38.159 Silence. 146 00:29:38.159 --> 00:29:42.388 Silence. 147 00:29:45.719 --> 00:29:53.368 Okay, so we're finally ready to look into the heart of. 148 00:29:53.368 --> 00:29:57.328 Sure is factoring out with them. This is probably the. 149 00:29:57.328 --> 00:30:03.209 Most famous quantum effects. Okay. So what's the factoring problem? 150 00:30:03.209 --> 00:30:07.409 You're given some number and say it's. 151 00:30:07.409 --> 00:30:12.959 Something like 60 and your order right? Targets are factorization. 152 00:30:12.959 --> 00:30:16.648 So, what's it's prime factorization you? It's. 153 00:30:16.648 --> 00:30:19.919 2 square times 3. 154 00:30:19.919 --> 00:30:24.689 Thanks so, in general we want to write and as in the form. 155 00:30:24.689 --> 00:30:28.108 He went to the 1 that you to. 156 00:30:28.108 --> 00:30:33.898 Be clear to that you can, and these are the prime crimes that divide and. 157 00:30:33.898 --> 00:30:37.828 And those other powers, it turns out that the. 158 00:30:37.828 --> 00:30:42.868 Most interesting case of factory, the most difficult case of the factory problem. 159 00:30:42.868 --> 00:30:46.409 Is when an is a product of 2. 160 00:30:46.409 --> 00:30:53.159 Or price, and Q, where these primes are roughly equal in length. 161 00:30:53.159 --> 00:30:57.509 So that the primes are as large as possible. 162 00:30:59.068 --> 00:31:02.189 This is the case of the factory problem that's used in the. 163 00:31:02.189 --> 00:31:06.298 I see crypto system. 164 00:31:08.219 --> 00:31:14.608 The the system is the most famous public key and practice system it's used. 165 00:31:15.749 --> 00:31:18.838 You use it every time you do Internet. 166 00:31:18.838 --> 00:31:22.288 Backing or if you make a purchase online. 167 00:31:22.288 --> 00:31:26.338 Using a credit card so, what's this. 168 00:31:26.338 --> 00:31:29.459 What's the security of our system based on. 169 00:31:29.459 --> 00:31:33.028 But it's based on the difficulty of factoring numbers. 170 00:31:33.028 --> 00:31:36.209 It's based on the fact that. 171 00:31:38.759 --> 00:31:41.999 The, the scientists and mathematicians have spent decades. 172 00:31:41.999 --> 00:31:46.949 Trying to solve this problem efficiently. All they have to show for the efforts. 173 00:31:46.949 --> 00:31:52.169 Exponential so. 174 00:31:52.169 --> 00:31:56.429 Feel that little M. E. 175 00:31:57.449 --> 00:32:00.989 The length of. 176 00:32:00.989 --> 00:32:04.199 It's. 177 00:32:04.199 --> 00:32:09.689 Then the most obvious algorithms for factoring take time. 178 00:32:09.689 --> 00:32:14.098 Which is bigger, or to to the little land exponential time. 179 00:32:14.098 --> 00:32:17.249 But using a lot of ingenuity. 180 00:32:18.598 --> 00:32:21.959 There are things that have been constructed. 181 00:32:21.959 --> 00:32:25.739 Using using a lot of number Terry. 182 00:32:25.739 --> 00:32:28.919 Really ingenious techniques. 183 00:32:28.919 --> 00:32:31.919 To take time. 184 00:32:31.919 --> 00:32:36.749 2 to the order, you grew to them. 185 00:32:38.308 --> 00:32:41.548 It's still exponential time. It's just a smaller exponent. 186 00:32:41.548 --> 00:32:44.759 And before and using these. 187 00:32:44.759 --> 00:32:49.409 These kinds of outcomes the current record is, is. 188 00:32:49.409 --> 00:32:53.159 Uh, factoring something like. 189 00:32:53.159 --> 00:32:56.459 750 that number or something like. 190 00:32:56.459 --> 00:33:00.388 200 decimal digits. 191 00:33:00.388 --> 00:33:03.479 But in any case, the point is that. 192 00:33:03.479 --> 00:33:08.398 Numbers, which are I see a 1000 digits long. 193 00:33:08.398 --> 00:33:12.628 Are far beyond our capabilities currently. 194 00:33:12.628 --> 00:33:16.828 Foreseeable future. Okay. So what is it that. 195 00:33:16.828 --> 00:33:21.269 Quantum computers can do to solve this problem. 196 00:33:21.269 --> 00:33:26.338 Efficiently okay, so to understand that you're going to have to. 197 00:33:26.338 --> 00:33:29.999 What. 198 00:33:29.999 --> 00:33:35.548 They're going to have to do a little bit of elementary. 199 00:33:36.719 --> 00:33:40.709 So, to to understand this, let's work with an example. 200 00:33:40.709 --> 00:33:43.949 So, we'll choose as our example. 201 00:33:43.949 --> 00:33:47.548 And equal to 21, and now. 202 00:33:48.838 --> 00:33:54.058 We are going to have to work, we're going to have to do some. 203 00:33:54.058 --> 00:33:57.898 Elementary model arithmetic, which it. 204 00:33:57.898 --> 00:34:02.459 Which had introduced in the last lecture so I remember that. We say. 205 00:34:02.459 --> 00:34:05.489 That is going to. 206 00:34:05.489 --> 00:34:10.798 The, and this is another way of saying that. 207 00:34:10.798 --> 00:34:15.989 If you if you divide B by by M, if you write. 208 00:34:15.989 --> 00:34:21.869 He has some quotient times and plus some remainder then he is the remainder that you get. 209 00:34:21.869 --> 00:34:27.148 For this division. Okay so yeah, examples. So for example. 210 00:34:27.148 --> 00:34:30.389 To compute 2421. 211 00:34:30.389 --> 00:34:34.829 3, and also compute. 212 00:34:34.829 --> 00:34:39.719 For example, 35 or 21, what's the remainder of? Valid. 213 00:34:39.719 --> 00:34:43.378 14, you don't see well, what's. 214 00:34:43.378 --> 00:34:47.608 Minus 1 more 21, but minus 1 is the same as. 215 00:34:47.608 --> 00:34:51.208 21 plus minus 1, which is. 216 00:34:51.208 --> 00:34:54.869 Which is 20. 217 00:34:54.869 --> 00:35:01.708 All right, so now, what can you do with with you could you could do something like. 218 00:35:01.708 --> 00:35:06.898 You could you could take the numbers, like, 24, plus 35 more. 219 00:35:06.898 --> 00:35:10.889 And you could say, well, this is the same thing as. 220 00:35:10.889 --> 00:35:16.559 3, plus 14, because the same thing has 17. 221 00:35:16.559 --> 00:35:23.639 What you want, or you can try not blind to number so you might do something like. 222 00:35:23.639 --> 00:35:28.259 24 times 31. 223 00:35:29.338 --> 00:35:34.498 Which is the same thing as 3 times? 9 it's 97. 224 00:35:34.498 --> 00:35:37.768 Which is this in a 6. 225 00:35:37.768 --> 00:35:40.918 Okay, so. 226 00:35:41.969 --> 00:35:44.969 What's the moral of all this? Well, the more or less. 227 00:35:44.969 --> 00:35:49.858 Well, 1st of all you can, you can, you can add, you can multiply. 228 00:35:49.858 --> 00:35:54.358 And your working model, you can do this kind of charismatic. 229 00:35:54.358 --> 00:35:58.079 And also do it quickly, right? Because. 230 00:35:58.079 --> 00:36:01.619 Because working model is just like. 231 00:36:01.619 --> 00:36:04.739 You want to figure out the remainder so you divide by and. 232 00:36:04.739 --> 00:36:08.608 But that we can carry out efficiently. So you can. 233 00:36:08.608 --> 00:36:13.228 Do arithmetic mode. 234 00:36:13.228 --> 00:36:18.778 Efficient so that's a 1st. 235 00:36:18.778 --> 00:36:21.898 There's another thing that. 236 00:36:21.898 --> 00:36:25.708 We already used, but let me reiterate it. So. 237 00:36:25.708 --> 00:36:30.449 Greatest common devices, if you want to compute the. 238 00:36:30.449 --> 00:36:34.918 Latest common divisive 2 numbers if, for example. 239 00:36:34.918 --> 00:36:39.599 What's the greatest common advisor of. 240 00:36:39.599 --> 00:36:42.659 15 and 21. 241 00:36:43.889 --> 00:36:48.659 So, how would you figure that out? You could you could write out the prime factors. 242 00:36:48.659 --> 00:36:54.028 It's 3 times 5, the time 7 and you collect the common. 243 00:36:54.028 --> 00:36:57.179 Common factors and. 244 00:36:57.179 --> 00:37:02.998 And you would see that the city's 3, but you could also do this without. 245 00:37:02.998 --> 00:37:09.239 Factory, and this is this is the genius of algorithm, which you probably. 246 00:37:09.239 --> 00:37:14.159 Seen in high school math, your basic. 247 00:37:14.159 --> 00:37:20.188 When you divide 21 by 15 is 1 times 15 last. 248 00:37:20.188 --> 00:37:24.478 6, and now you. 249 00:37:24.478 --> 00:37:28.259 Repeat the process with 15 minutes. This is the theme is. 250 00:37:28.259 --> 00:37:31.469 2 times 6 Plus be. 251 00:37:31.469 --> 00:37:35.548 And I repeat the process with 6 and. 252 00:37:35.548 --> 00:37:40.679 Free and you get to the main the 0 and so GCD is the last. 253 00:37:40.679 --> 00:37:44.458 Non 0 remainder, but the point is. 254 00:37:44.458 --> 00:37:48.389 You can carry this process of efficiently so we can compute. 255 00:37:48.389 --> 00:37:51.748 Greatest common devisors very efficiently. 256 00:37:51.748 --> 00:37:56.969 Basket, even though we can't, we don't artifact price numbers. 257 00:37:58.108 --> 00:38:02.938 Okay, as I pointed out last time. 258 00:38:02.938 --> 00:38:06.088 If you would like to know more about arithmetic. 259 00:38:06.088 --> 00:38:09.929 You have an online resource, which is this textbook. 260 00:38:09.929 --> 00:38:13.530 It's available to you online. 261 00:38:13.530 --> 00:38:16.860 Just download the required chapters meet them. 262 00:38:16.860 --> 00:38:21.480 You don't have to do this what I just said about model arithmetic. 263 00:38:21.480 --> 00:38:26.820 If you believe it and you are comfortable with it, that's enough for you to get through this with. 264 00:38:26.820 --> 00:38:32.099 Okay, okay so now let's let's go back to. 265 00:38:32.099 --> 00:38:35.610 Our task, which is to factor 21. 266 00:38:35.610 --> 00:38:42.119 So, how are you going to do it turns out the key is to try to solve this patient. 267 00:38:42.119 --> 00:38:45.869 X squared is going to 1 more. 268 00:38:45.869 --> 00:38:49.170 Thank you. So what do I need by this? 269 00:38:49.170 --> 00:38:54.780 We are trying to look for that number more 21, such that when you multiply it by itself. 270 00:38:54.780 --> 00:38:58.440 And you reduce the result more 21 you get 1. 271 00:38:59.550 --> 00:39:07.829 So, what would such a number look like there's an easy answer. You choose X equal to 1. 272 00:39:07.829 --> 00:39:13.170 Clearly, 1 times 1 is 1 and it doesn't change. If you reduce it more, you want. 273 00:39:13.170 --> 00:39:19.619 What's another number? Well, if you, if you were not working more 21, you would say. 274 00:39:19.619 --> 00:39:25.949 X equals minus 1 and that that works as well because minus 1 is the same thing as 20. 275 00:39:25.949 --> 00:39:29.880 Mark 21, if you square it. 276 00:39:29.880 --> 00:39:34.619 Get 400, which is, which is 1 more 21. 277 00:39:34.619 --> 00:39:39.090 But, in fact, if you if you believe that you can multiply these numbers. 278 00:39:39.090 --> 00:39:43.710 Really you know, the science council minus 1 times minus 1 is 1. 279 00:39:43.710 --> 00:39:47.579 You don't even have to work that out so it turns out. 280 00:39:47.579 --> 00:39:52.650 Whatever, and is and minus ones what squared is 1 more. 281 00:39:53.699 --> 00:39:58.500 Okay, so these are so we found the square roots of 1. 282 00:39:58.500 --> 00:40:02.250 On model, but but is this all. 283 00:40:02.250 --> 00:40:06.119 Could be another X that X squared is convert into 1 more. 284 00:40:06.119 --> 00:40:09.329 Anyone I'd say, surprisingly, yes. 285 00:40:09.329 --> 00:40:12.630 There's another X that has this property so if you take. 286 00:40:12.630 --> 00:40:15.690 X equals 8 when you look at X squared. 287 00:40:15.690 --> 00:40:19.320 When X squared is 8 times 8. 288 00:40:19.320 --> 00:40:24.239 Which is 64, but then you reduce it Mark 21. 289 00:40:24.239 --> 00:40:28.349 You got 1. 290 00:40:28.349 --> 00:40:32.610 Okay, so we've discovered another square root of 1 more. 291 00:40:32.610 --> 00:40:37.800 And you want what's the script for what it's good for all. 292 00:40:37.800 --> 00:40:42.090 See, what we can say is that. 293 00:40:42.090 --> 00:40:45.420 It squared is comprehend to 1. 294 00:40:45.420 --> 00:40:50.670 1, you can move on to the other side and. 295 00:40:50.670 --> 00:40:53.760 That's 8 squared minus 1 squared. 296 00:40:53.760 --> 00:40:57.030 Online to 0, 121. 297 00:40:57.030 --> 00:41:02.820 Which means by definition that there's a remainder 0, and you divide by 21 so. 298 00:41:02.820 --> 00:41:06.360 91 divides. 299 00:41:06.360 --> 00:41:10.380 8 squared minus 1 Square, which is 8 plus 1. 300 00:41:10.380 --> 00:41:16.500 I am the minus 1, but 21 does not divide either of these. 301 00:41:16.500 --> 00:41:21.510 But how could it be the only way this could be is. 302 00:41:21.510 --> 00:41:26.730 If you write 21, if you fat tries 21, so you 3 times 7. 303 00:41:26.730 --> 00:41:32.670 Then 1, out of this device, 1 of these factors, and the other part of it devices the other 1. 304 00:41:32.670 --> 00:41:37.289 So, you can recover the prime factors by getting GCD. 305 00:41:37.289 --> 00:41:41.849 Thank you 1. that's fine. The 9. 306 00:41:43.199 --> 00:41:46.260 What's the. 307 00:41:47.489 --> 00:41:51.030 Or you could compute the city of 21 and the other. 308 00:41:51.030 --> 00:41:54.599 7, 7. 309 00:41:54.599 --> 00:41:59.219 So, you recover the prime factors if you could only compute. 310 00:42:01.800 --> 00:42:06.150 Such a non trivial square root. 311 00:42:06.150 --> 00:42:13.289 1 more, thank you. 1. okay now, is it the only such number? 312 00:42:13.289 --> 00:42:16.559 And that you can get another 1, if you think about it. 313 00:42:18.150 --> 00:42:22.710 What about X? Equals? Minus name? What's my husband about? 314 00:42:22.710 --> 00:42:26.849 That's the same thing as the team. What can I do? 1. 315 00:42:27.929 --> 00:42:32.039 Because you're when you add 21 to minus 8, you get 30. 316 00:42:32.039 --> 00:42:36.329 And, but what's the square of 13? 317 00:42:36.329 --> 00:42:40.019 91, so 13 squared. 318 00:42:40.019 --> 00:42:44.309 Is coming into 169 on, went to 1. 319 00:42:44.309 --> 00:42:49.050 Okay, so these numbers plus the. 320 00:42:49.050 --> 00:42:53.190 Minus 88 and 13, these are called non trivial square roots of 1. 1. 321 00:42:53.190 --> 00:42:58.739 And then these are. 322 00:42:58.739 --> 00:43:03.179 Okay, so so what are we looking for that what we want to do? 323 00:43:03.179 --> 00:43:08.130 We want to if he can find. 324 00:43:08.130 --> 00:43:12.929 X such that X is more. 325 00:43:12.929 --> 00:43:16.139 Plus or minus 1 more and. 326 00:43:17.219 --> 00:43:20.460 But X squared is going to 1. 327 00:43:20.460 --> 00:43:25.619 Then we are going to be done. 328 00:43:25.619 --> 00:43:29.639 Then then we are in good shape because we know that. 329 00:43:29.639 --> 00:43:34.050 And divides X plus 1. 330 00:43:34.050 --> 00:43:39.809 Times X minus 1 that's from this X squared minus 1 this comment 0. 331 00:43:39.809 --> 00:43:44.610 Since X is not. 332 00:43:44.610 --> 00:43:48.750 X plus or minus 1 is not comprehend to 0 model. 333 00:43:48.750 --> 00:43:51.840 That's another way of saying that. 334 00:43:51.840 --> 00:43:55.079 And does not. 335 00:43:55.079 --> 00:43:58.860 Divide plus. 336 00:43:58.860 --> 00:44:06.630 1 or X, minus 1 end divides the product of these 2. it doesn't divide either. 1. how could it be. 337 00:44:06.630 --> 00:44:11.940 The only way it could be is if part of, and some of the factors of and divide X plus 1. 338 00:44:11.940 --> 00:44:17.489 Others divide expand this 1 if you compute the GCD of and. 339 00:44:17.489 --> 00:44:22.469 X plus 1, you get a non trivial device and. 340 00:44:22.469 --> 00:44:26.639 And as a product of 2 primes, you recover, right? 341 00:44:26.639 --> 00:44:30.030 Okay, so. 342 00:44:30.030 --> 00:44:33.510 So now our challenge. 343 00:44:33.510 --> 00:44:37.260 Is How do we discover ethical to 8? 344 00:44:37.260 --> 00:44:41.400 How do we discovered this nontrivial factor? Well, Here's how. 345 00:44:41.400 --> 00:44:44.730 So that's has. 346 00:44:44.730 --> 00:44:50.820 And equal to 21, let's pick a random number. Let's pick X equal. 347 00:44:50.820 --> 00:44:54.389 Too, let's say, and now let's. 348 00:44:54.389 --> 00:44:59.099 Let's create a table, let's say to the 0. 349 00:44:59.099 --> 00:45:02.280 1, more anyone. 350 00:45:02.280 --> 00:45:06.360 Go to the 1 is 2. 351 00:45:06.360 --> 00:45:11.250 Anyone who's squared. 352 00:45:11.250 --> 00:45:15.570 For. 353 00:45:15.570 --> 00:45:18.840 8, go to the call. 354 00:45:18.840 --> 00:45:22.380 16. 355 00:45:22.380 --> 00:45:25.440 Through to the 32. 356 00:45:25.440 --> 00:45:31.110 The 32 is the same as 11 go to the 6. 357 00:45:31.110 --> 00:45:34.170 Well, it's 2 times 11, which is. 358 00:45:34.170 --> 00:45:38.099 22, which is 1 more anyone. 359 00:45:38.099 --> 00:45:42.090 So, 2 to the 6 is 1 more cranky 1. 360 00:45:42.090 --> 00:45:45.210 Now, what's the significance of this. 361 00:45:45.210 --> 00:45:48.300 Well, 2 to the 6. 362 00:45:48.300 --> 00:45:52.829 It's the same thing as Tokyo. Tokyo. 363 00:45:52.829 --> 00:45:56.610 So, what we know is that 2 to the 2. 364 00:45:56.610 --> 00:45:59.909 And you square it, you get 1. 365 00:45:59.909 --> 00:46:04.199 Mark and lo, and behold what's to cube? 366 00:46:04.199 --> 00:46:07.289 It's 8, so we discovered. 367 00:46:07.289 --> 00:46:10.800 A non trivial square root of 1 more 21. 368 00:46:12.360 --> 00:46:16.980 To highlight keywords that well, let's see what we want to do in general. 369 00:46:16.980 --> 00:46:20.969 So, if you're working on, em. 370 00:46:20.969 --> 00:46:25.230 X random. Now, what can we do. 371 00:46:26.940 --> 00:46:30.449 And compute X to the 0 X to the 1. 372 00:46:30.449 --> 00:46:35.190 You just keep going until we get 2 extra the eyes on run through 1. 373 00:46:35.190 --> 00:46:39.570 And now if you're lucky. 374 00:46:39.570 --> 00:46:43.769 And is even. 375 00:46:43.769 --> 00:46:49.949 So, we can write X to the R2 called squared comment 1 more then. 376 00:46:49.949 --> 00:46:53.610 If you are even look here. 377 00:46:53.610 --> 00:46:57.179 Extra to. 378 00:46:57.179 --> 00:47:00.179 Is not plus or minus 1 more than. 379 00:47:01.260 --> 00:47:04.260 And there we have. 380 00:47:04.260 --> 00:47:07.409 A non trivial square root of. 381 00:47:08.880 --> 00:47:12.840 So, what's the chance? We'll be lucky. 382 00:47:12.840 --> 00:47:16.349 Well, that's what this Lemme tells us it tells us. 383 00:47:16.349 --> 00:47:19.829 The chance we will be lucky is at least 1. 384 00:47:21.449 --> 00:47:25.139 What's it saying it's saying that and be an odd composite. 385 00:47:25.139 --> 00:47:28.469 That's what we have at least 2 distinct prime factors. 386 00:47:28.469 --> 00:47:33.329 X random between 0 and minus 1. 387 00:47:33.329 --> 00:47:38.369 That's what we'll do with the set random. Well, then it says. 388 00:47:38.369 --> 00:47:42.809 If the greatest common devise of X and equal to 1, where we come back to this in a moment. 389 00:47:42.809 --> 00:47:47.130 Then, with probability, at least half a success. 390 00:47:47.130 --> 00:47:52.079 Well, then the order of of X model, what's the order of X model? It's. 391 00:47:52.079 --> 00:47:56.190 It's the minimum our, we can raise to. 392 00:47:58.170 --> 00:48:08.340 So that we can get marked right? So it's a minimum non 0 power. We have to raise extra to get 1 more than so, that's the order. That's what you're looking for. 393 00:48:08.340 --> 00:48:14.400 Then this number is even an extra number. 2 is a non trivial squared 1 more. 394 00:48:14.400 --> 00:48:20.519 So, we are going to be successful, provided the GCD of X and as well, the greatest common advisor of excellence as well. 395 00:48:20.519 --> 00:48:27.389 So, what happens if accident have a non trivial GCD if they have some common factor. 396 00:48:29.099 --> 00:48:33.869 Well, I claim that then we are even luckier because we picked accept random. 397 00:48:35.579 --> 00:48:42.659 We can compute the greatest common Divisor effects and if it turns out not to be 1, then we've already found the non trivial factor of. 398 00:48:42.659 --> 00:48:45.900 Because remember axis smaller than than. 399 00:48:45.900 --> 00:48:50.010 So, this greatest common device is smaller than that and it's a factor of them. 400 00:48:50.010 --> 00:48:56.250 Okay, so I so this tells us that this scheme is short to work. 401 00:48:56.250 --> 00:49:00.329 But now why is this good for for. 402 00:49:01.349 --> 00:49:05.309 So, let's look at it, so here's our table. Let's let's work this answer. 403 00:49:05.309 --> 00:49:09.659 And is 21, we picked accept random. It turned out to be 2. 404 00:49:09.659 --> 00:49:13.380 And now let's drop the table. Okay. So. 405 00:49:13.380 --> 00:49:18.929 So, we, in 1 column, we put a request from 0, 1 and so on. 406 00:49:18.929 --> 00:49:23.730 In the next column, we put f of a which is X rays to a model. 407 00:49:23.730 --> 00:49:29.969 So this is the same table. We actually computed 2 slides ago. Now we are going to extend it. 408 00:49:29.969 --> 00:49:32.969 And keep going 7. 409 00:49:32.969 --> 00:49:37.230 Is it 2, 8 or. 410 00:49:37.230 --> 00:49:41.219 Mine you see, because every time you're multiplying. 411 00:49:41.219 --> 00:49:47.070 This number by 2 and more reducing modern. So we just keep going around along the same. 412 00:49:47.070 --> 00:49:51.420 Numbers again, 2816 pretend. 413 00:49:52.530 --> 00:49:56.369 1111. 414 00:49:56.369 --> 00:50:00.960 12 1, actually, let me let me write. 415 00:50:00.960 --> 00:50:06.059 This 1 like this, and let's switch back and write this. 416 00:50:06.059 --> 00:50:10.320 Like this, because now we are starting another period again. 417 00:50:12.210 --> 00:50:18.090 So so you see what we got here is a periodic function f, is a periodic function. 418 00:50:19.949 --> 00:50:23.280 Okay, so what's its area. 419 00:50:23.280 --> 00:50:27.659 Period our, in our cases. 420 00:50:28.769 --> 00:50:33.510 6, and if you can discover the theory. 421 00:50:33.510 --> 00:50:37.469 And if you are lucky, then. 422 00:50:37.469 --> 00:50:42.030 X to the hour with 2 is a non trivial square root. 423 00:50:42.030 --> 00:50:45.030 1, more. 424 00:50:45.030 --> 00:50:48.329 From which we can easily recover the factors of it. 425 00:50:48.329 --> 00:50:53.429 So, our task is now reduced to 1 of even finally. 426 00:50:53.429 --> 00:50:57.630 For dysfunction, but how big is the period? Well, the period could be. 427 00:50:57.630 --> 00:51:02.460 Comfortable to make is. 428 00:51:02.460 --> 00:51:07.949 Housing digit number period is exponentially. 429 00:51:07.949 --> 00:51:13.289 But that doesn't bother us because we have a quantum computer, and it can discover this period and. 430 00:51:13.289 --> 00:51:16.380 Which is exponentially large on the. 431 00:51:16.380 --> 00:51:19.829 Okay, so what is the, what does the algorithm look like. 432 00:51:19.829 --> 00:51:23.280 Well, it it creates a superposition. 433 00:51:23.280 --> 00:51:28.289 Some of all a going from 0 to M minus 1. 434 00:51:28.289 --> 00:51:31.619 For some suitable and which we choose. 435 00:51:31.619 --> 00:51:36.570 1, over square root and normalization. 436 00:51:36.570 --> 00:51:39.869 And then what what what does the superposition look like it? 437 00:51:39.869 --> 00:51:44.670 You know, it's a superposition over the role of this matrix of this of this table. 438 00:51:44.670 --> 00:51:48.869 Okay, and then what do we do. 439 00:51:48.869 --> 00:51:53.190 Well, you had findings so what we do is. 440 00:51:53.190 --> 00:51:57.929 We now measure the 2nd register. We see some value. So, for example. 441 00:51:57.929 --> 00:52:01.559 You might see a, is for. 442 00:52:01.559 --> 00:52:06.480 But now, what happens is every place maybe have a form. 443 00:52:06.480 --> 00:52:14.280 These are the parts of the superposition that it collapses to and the remaining rows of the matrix disappear. 444 00:52:14.280 --> 00:52:17.369 And so our superposition is now reduced to. 445 00:52:17.369 --> 00:52:22.920 Is in a superposition of 2814it'son it says periodic supposition. 446 00:52:22.920 --> 00:52:27.539 What's our next step now? We do. 447 00:52:27.539 --> 00:52:31.949 Why is sampling on the 1st register? 448 00:52:33.000 --> 00:52:40.079 And we know that provided M, satisfies the right conditions. 449 00:52:40.079 --> 00:52:44.159 We have an efficient way of classically reconstructing. 450 00:52:44.159 --> 00:52:47.909 Period of the periodic function. 451 00:52:49.260 --> 00:52:53.250 Possibly be construct. 452 00:52:53.250 --> 00:52:56.429 Here. 453 00:52:57.630 --> 00:53:01.949 Once we have the period, or we can, we can check. 454 00:53:01.949 --> 00:53:05.969 Better be were lucky ours even extra with 2. 455 00:53:05.969 --> 00:53:09.179 Is not plus or minus 1 Madame. 456 00:53:09.179 --> 00:53:14.760 If if you're lucky, then we stop, we can now. 457 00:53:14.760 --> 00:53:18.539 Be a Tom, if you're lucky, let me just try again. 458 00:53:18.539 --> 00:53:22.409 We know we succeed with property half in each trial. 459 00:53:22.409 --> 00:53:26.670 And so we don't have to spend too many trials on this. So the. 460 00:53:26.670 --> 00:53:31.949 Last thing I need to tell you is, how do we choose them? Well, we already saw this, right? 461 00:53:31.949 --> 00:53:35.130 We need to choose is sufficiently larger or. 462 00:53:35.130 --> 00:53:38.909 You know, to satisfy the conditions of of period, finding. 463 00:53:38.909 --> 00:53:43.079 What he said is as long as M. 464 00:53:43.079 --> 00:53:46.170 Is larger than. 465 00:53:46.170 --> 00:53:50.670 2 times are squared. 466 00:53:51.929 --> 00:53:56.070 Be a good enough right? What was this condition? It just have. 467 00:53:56.070 --> 00:53:59.519 As long as am of. 468 00:53:59.519 --> 00:54:03.630 Is larger than 2 times. So hours the period and. 469 00:54:03.630 --> 00:54:07.500 Our R, is the number of copies of the spirit that we get to see. 470 00:54:07.500 --> 00:54:13.769 As long as the number of copies of the period is larger, let's say, by a factor of 2 or more than the. 471 00:54:13.769 --> 00:54:17.400 Actual itself and the good. So. 472 00:54:17.400 --> 00:54:21.840 But we don't know what the period is, but we do know that the period is smaller than. 473 00:54:21.840 --> 00:54:25.019 So, we're just going to choose to be. 474 00:54:25.019 --> 00:54:28.949 Larger than 2 Times Square. 475 00:54:28.949 --> 00:54:32.639 So that sounds good. So. 476 00:54:32.639 --> 00:54:37.949 So, the 2nd, for for the for factoring, looks like this. 477 00:54:39.059 --> 00:54:43.139 All zeros, you apply the content for a transform. 478 00:54:43.139 --> 00:54:46.650 And by him, quantify your transform the. 479 00:54:46.650 --> 00:54:50.400 Is larger than 2 times and square. 480 00:54:50.400 --> 00:54:54.239 So, you just speak some power of 2, which is larger than that. 481 00:54:55.679 --> 00:55:01.530 You apply this function f is X today modern. 482 00:55:01.530 --> 00:55:08.039 But you can compute efficiently, then you measure the results here. 483 00:55:08.039 --> 00:55:12.869 On the 2nd register you for your sampling sample on the 1st register. 484 00:55:12.869 --> 00:55:17.309 You do classical voice processing check that you got that. 485 00:55:17.309 --> 00:55:21.329 Got a non trivial Sparrow. 486 00:55:21.329 --> 00:55:24.420 And if you, if you did, otherwise you would eat. 487 00:55:24.420 --> 00:55:27.929 That's it that's that's the algorithm for factory. 488 00:55:30.059 --> 00:55:34.739 Okay, so. 489 00:55:36.300 --> 00:55:42.179 Okay, if I'm I'm back again, then. 490 00:55:42.179 --> 00:55:46.889 So, the high level introduction is a lot of math involved, but yeah. 491 00:55:46.889 --> 00:55:51.420 I showed this instead of the mass foul 1, because this was shorter. 492 00:55:51.420 --> 00:55:55.739 But just do. 493 00:55:57.360 --> 00:56:03.659 Send send me an algorithm mood today. I want to show you a couple of. 494 00:56:03.659 --> 00:56:18.300 Short 1, short 1 on solving a linear system on a quantum computer X equals B, which is useful for machine learning. This will just be an introduction to it. But. 495 00:56:18.300 --> 00:56:21.989 And I have a chat window. 496 00:56:21.989 --> 00:56:29.309 Open another computer, so if you type comments there, like, you can't hear or see anything, I will see them. I hope. 497 00:56:34.079 --> 00:56:37.409 Silence. 498 00:56:37.409 --> 00:56:41.760 Let's continue reading other very important. 499 00:56:41.760 --> 00:56:47.639 Heroin has a deployed algorithm, which is also called matrix inversion. 500 00:56:47.639 --> 00:56:51.150 This protocol is used many. 501 00:56:51.150 --> 00:57:02.460 Machine learning algorithm as a fundamental building block so it is really important that we understand the logic behind it, but it's tricky algorithm. So 1st, let's go through. 502 00:57:02.460 --> 00:57:07.440 A quick overview of how it works. So the problem that we want to solve. 503 00:57:07.440 --> 00:57:11.369 Is giving a system of equations. 504 00:57:11.369 --> 00:57:22.139 We want to assuming that the question matrix is impossible. Then we want to calculate the solution X as a dangerous of 8 times. The. 505 00:57:22.139 --> 00:57:25.889 And we would like to find a point of address for this. 506 00:57:25.889 --> 00:57:30.090 Classically this would take some pulling on your time. Probably. 507 00:57:30.090 --> 00:57:34.980 Cubic in time, or maybe a bit better and. 508 00:57:34.980 --> 00:57:42.630 There is that this algorithm gives you an exponentially faster Quentin protocol for performing something very similar. 509 00:57:42.630 --> 00:57:46.050 So 1st, we have to consider state preparation. 510 00:57:46.050 --> 00:57:51.840 So you have to prepare the V, the state, the state, the vector. 511 00:57:51.840 --> 00:57:55.050 And this is in encoding. 512 00:57:56.940 --> 00:58:01.260 So, you might have to use a fairly involved circuit. 513 00:58:01.260 --> 00:58:04.739 To prepare this, so that increases your circuit that. 514 00:58:04.739 --> 00:58:08.099 And then here. 515 00:58:08.099 --> 00:58:11.519 Would be corresponding to Tony and and coding. 516 00:58:14.159 --> 00:58:17.460 Says you can think of this. 517 00:58:17.460 --> 00:58:22.050 As a, as a habit, Antonio, so if you're a is not permission. 518 00:58:22.050 --> 00:58:28.739 Then you have to make it permission by applying a simple transformation and then you would be able to include it as a head attorney. 519 00:58:28.739 --> 00:58:35.010 And then eventually as a unitary, the next stage is to perform a quantum phase estimation. 520 00:58:35.010 --> 00:58:39.119 Because we are going to estimate the values of this, a operator. 521 00:58:39.119 --> 00:58:49.860 And by estimating the agendize of this operator, what we are going to get is a very simple description of the structure of a. 522 00:58:49.860 --> 00:58:53.730 And then allows us to easily in, but. 523 00:58:53.730 --> 00:58:59.820 The higher value, so, after a quantum phase estimation, we have. 524 00:58:59.820 --> 00:59:05.309 Mistakes roughly the States, so it's some state and what we are going to do is we introduce. 525 00:59:05.309 --> 00:59:11.130 And are similar register 1 more, and we apply a control locations. 526 00:59:11.130 --> 00:59:16.079 On on the value estimates. 527 00:59:16.079 --> 00:59:22.199 And was going to give us, is, this is not a vascular register is additional 1 Cuban. 528 00:59:25.050 --> 00:59:31.800 For the time being, let's forget about what the rest of the status here, because this is what happens this is why the important thing that happens. 529 00:59:31.800 --> 00:59:38.099 So, by creating this condition are additional, then you can encode. 530 00:59:38.099 --> 00:59:42.210 Some cross the times, the inverse of daggone value. 531 00:59:42.210 --> 00:59:49.409 In the attitude of the 1 state of your ansolar register, and that's what we are going to use. 532 00:59:50.550 --> 00:59:54.329 But before we can use that, plus they have to compute. 533 00:59:54.329 --> 01:00:01.530 The Ivan value register, which means that everything that we did for the final phase estimation, we have to reverse. 534 01:00:01.530 --> 01:00:07.320 So this will be a 4 point of, is estimation reverse in this. 2nd. 535 01:00:07.320 --> 01:00:15.750 And the reason we have to do that is because if we start doing any kind of measurement here, these registers are entangled. 536 01:00:15.750 --> 01:00:29.369 And if you remember the very beginning of this course, you know, that if you could just trace out or get rid of a part of an enzyme about system, then you're going to end up with some kind of a mix. Did you want to avoid it? 537 01:00:29.369 --> 01:00:33.000 So, we have to our compute everything in these registers. 538 01:00:33.000 --> 01:00:36.750 So we have this state, so this is just a century. 539 01:00:36.750 --> 01:00:41.460 Itself expanded in. It's in an ongoing basis. 540 01:00:41.460 --> 01:00:46.769 And then this would be the vacuum state of the value register. 541 01:00:46.769 --> 01:00:51.449 And then your answer lies on touched by this inverse operation. 542 01:00:51.449 --> 01:00:57.480 So, once we do it is, we can confident that your rejection sampling, which means that we measure them. 543 01:00:57.480 --> 01:01:01.199 And if we get 0, we discard everything and we restart the calculation. 544 01:01:01.199 --> 01:01:04.769 And if we get along, that means that now. 545 01:01:04.769 --> 01:01:16.829 Whatever whatever you get is proportional to the inverse of London, and that's what we are going to use to estimate. 546 01:01:16.829 --> 01:01:21.690 Or or some measurable thing. 547 01:01:21.690 --> 01:01:26.519 Why we need the solution of the system of equations. 548 01:01:26.519 --> 01:01:31.650 So, the resource requirements of this protocol are are steep. 549 01:01:31.650 --> 01:01:36.719 So, if you watch Toronto makis, guest lecture, he told me about Sean. 550 01:01:36.719 --> 01:01:43.800 If you look at how shows algorithm works, it's actually has a similar structure. It is a very similar structure to point to phase estimation. 551 01:01:43.800 --> 01:01:49.860 So, that gives us a lower about how much resource we need to, to run this protocol. 552 01:01:49.860 --> 01:01:53.789 So, for 2048 bits are encryption. 553 01:01:53.789 --> 01:02:03.900 You would need 4,000 logical and that will take us in the range of millions of physical commits on, which we have to error correction. 554 01:02:03.900 --> 01:02:10.710 So, if we look at the number of Cubics, we have today on Gateway computers, they are less than 100. 555 01:02:10.710 --> 01:02:23.460 So, we are very, very far from being able to implement this algorithm in a practical manner. But this algorithm is definitely very important as we move forward and the better and better and computers. 556 01:02:23.460 --> 01:02:28.440 Okay. 557 01:02:28.440 --> 01:02:37.559 I didn't understand the details either, but it gave a sense of what's involved. 558 01:02:37.559 --> 01:02:41.789 Okay. 559 01:02:43.860 --> 01:02:49.500 And I've got some links here and so on, you could look at the half hour lecture. 560 01:02:50.639 --> 01:03:03.360 I want to go back to the quantum summary page later. That may be Monday. Let's do a little hardware. Actually we've seen a lot of theoretical math. Okay. 561 01:03:03.360 --> 01:03:14.670 Ways to implement actually, because these things you're not just theoretically interesting. They actually can start building them. There's several major ideas. I'll show you IBM some, maybe Monday. 562 01:03:14.670 --> 01:03:21.539 We'll do now, is 2 other thing a trapped ion computer and quantum annealing. 563 01:03:21.539 --> 01:03:25.860 And they are competing methods. 564 01:03:27.329 --> 01:03:30.900 Is a very superficial thing, but, you know. 565 01:03:30.900 --> 01:03:40.679 Ion is a charge we see 2 of them calcium and destructive. 566 01:03:40.679 --> 01:03:44.429 They are super controllable quantum systems. 567 01:03:44.429 --> 01:03:58.105 And we'll see, we can store information into either 1. so those are his initially get state 0, we can apply a pulse of energy to switch it to state 1 later for readout. 568 01:03:58.135 --> 01:04:02.394 We can use a laser. That would have no effect on stage. 0. 569 01:04:02.880 --> 01:04:09.150 But our ion in state 1 will absorb energy and then admitted back as a. 570 01:05:45.420 --> 01:05:49.650 Okay, so that's a teaser. You can go and get a lot of other. 571 01:05:49.650 --> 01:05:56.610 Videos on that, go to open courseware and so on. 572 01:05:56.610 --> 01:06:04.500 I gave you a teaser. I'll show you another technology quantum annealing D wave systems. 573 01:06:05.699 --> 01:06:11.760 This does not use Cuba, so it's a different way of looking at a quantum computer. 574 01:06:11.760 --> 01:06:14.909 Silence. 575 01:06:14.909 --> 01:06:19.980 Just a 2nd, here, there are bandwidth issues again. 576 01:06:21.570 --> 01:06:30.570 You know, I'm getting at the point, I'm trying to get fed up with Webex. I'm wondering if I should be putting my. 577 01:06:30.570 --> 01:06:42.929 Lectures on some other server, if you guys are taking other classes, which are using platforms that you think might be better than Webex. 578 01:06:42.929 --> 01:06:48.659 Feel free to mention them. I don't like this any better than you miss. 579 01:06:48.659 --> 01:06:52.139 But we'll give us a try again and see what happens. 580 01:06:57.059 --> 01:07:05.880 Quantum computing, although being a relatively young field is actually quite complex and there's many different approaches being pursued around the world. 581 01:07:05.880 --> 01:07:09.000 Development. 582 01:07:09.000 --> 01:07:13.230 Silence. 583 01:07:13.230 --> 01:07:17.340 Silence. 584 01:07:23.670 --> 01:07:26.670 Our approach is. 585 01:07:26.670 --> 01:07:29.940 In this video, I'll explain what that is. 586 01:07:29.940 --> 01:07:40.710 How it relates to the other forms of so is basically a way of using the intrinsic effects of quantum physics. 587 01:07:40.710 --> 01:07:45.030 Help you solve certain types of problems with optimization problems. 588 01:07:45.030 --> 01:07:48.300 And also related problem called probabilistic. 589 01:07:49.500 --> 01:07:54.780 And let me explain what these are. So, an optimization problem is a problem where. 590 01:07:54.780 --> 01:08:00.329 You try a serve for the best configuration are many, many different, possible combinations. 591 01:08:00.329 --> 01:08:03.960 So, an example, this is say you're trying to build a house. 592 01:08:03.960 --> 01:08:07.679 You've got a fixed budget to spend, but many, many different things. You. 593 01:08:07.679 --> 01:08:11.130 You'd like to have in your hands maybe you can't afford to. 594 01:08:11.130 --> 01:08:15.090 So, the challenge is to find a combination of all of those, if. 595 01:08:15.090 --> 01:08:19.949 Things you can afford fit into your house and maximize your happiness. 596 01:08:19.949 --> 01:08:28.590 You can imagine spending your entire budget on house, which is great, or you spend your entire budget and is not quite. 597 01:08:28.590 --> 01:08:31.590 So, an optimization problem is trying to find the best. 598 01:08:31.590 --> 01:08:34.800 The reason can use. 599 01:08:34.800 --> 01:08:38.340 Physics to solve optimization problems is because. 600 01:08:38.340 --> 01:08:42.180 You can frame them as a type of phone calls and edema minimization problem. 601 01:08:42.180 --> 01:08:49.140 And, like, the fundamental part of physics is that everything's always trying to climb with minimum and it. 602 01:08:49.140 --> 01:08:54.869 So, things slide hills or thermodynamics, hot things. 603 01:08:54.869 --> 01:08:59.010 Cool down over time and it's also true of quantum. 604 01:08:59.010 --> 01:09:04.739 It's the is using quantum physics to find a minimum and if you. 605 01:09:06.659 --> 01:09:11.760 So something problems related to optimization problems. 606 01:09:11.760 --> 01:09:17.130 But they're slightly different, instead of focusing on trying to find the minimum energy. 607 01:09:17.130 --> 01:09:26.340 What you're trying to do is sample for many low energy statements and try and characterize the shape of your energy. 608 01:09:26.340 --> 01:09:29.970 This useful outpatient areas like machine learning. 609 01:09:29.970 --> 01:09:35.550 They are trying to build a probabilistic representation of the world. 610 01:09:35.550 --> 01:09:38.819 And these samples give you information about. 611 01:09:38.819 --> 01:09:43.229 What your model is like now, and you can use those who improves your models. 612 01:09:43.229 --> 01:09:47.550 The time optimization problems also crop rpm. 613 01:09:47.550 --> 01:09:53.220 In machine learning, and typically something problems and optimization problem is very difficult to solve on. 614 01:09:53.220 --> 01:09:59.640 On classical computers, so there's a lot of interest in trying to find alternative techniques to solving. 615 01:09:59.640 --> 01:10:03.270 These kinds of. 616 01:10:03.270 --> 01:10:07.859 So that's a description of meeting. 617 01:10:07.859 --> 01:10:12.989 And the kind of things that you use, so how does it relate to the other forms of. 618 01:10:14.279 --> 01:10:18.510 Well, the 1st phone call, Alex called Kate model. 619 01:10:18.510 --> 01:10:23.250 And and the difference is between these 2 kinds. 620 01:10:23.250 --> 01:10:30.510 It can be summarized as follows so in quantum annealing, what you're trying to do is harness the natural evolution of quantum. 621 01:10:30.510 --> 01:10:34.800 Well, then you don't have any control over that. 622 01:10:34.800 --> 01:10:38.279 So, you set up the problem at the beginning. 623 01:10:38.279 --> 01:10:45.510 You like quantum physics, do its natural evolution and the configuration at the end corresponds to the answer. 624 01:10:46.529 --> 01:10:52.409 In computing, the aim is a lot more ambitious. What you're trying to do there is. 625 01:10:52.409 --> 01:10:56.039 Be able to control and manipulate the evolution of that quantity. 626 01:10:56.039 --> 01:10:59.279 The time now, this is what more difficult because. 627 01:10:59.279 --> 01:11:02.369 Quantum systems tend to be incredibly delicate to work with. 628 01:11:02.369 --> 01:11:07.260 However, you can have having that amount of control means that you can. 629 01:11:07.260 --> 01:11:14.159 Solve a bigger class of problems so these differences are the reason why it's impossible to scale out. 630 01:11:14.159 --> 01:11:18.149 Point to the naming processes to. 631 01:11:18.149 --> 01:11:21.569 Whereas the state of the table of contents. 632 01:11:21.569 --> 01:11:26.340 Is around 10 K. so it's a lot more difficult to get. 633 01:11:26.340 --> 01:11:29.939 The 2 bits to work together coherently in a gate model. 634 01:11:29.939 --> 01:11:34.260 However, there have been some very powerful algorithms developed. 635 01:11:34.260 --> 01:11:44.609 For use when they reach scale so, a couple of examples shores algorithms, the factory line numbers, and also grover's algorithm searching. 636 01:11:45.810 --> 01:11:50.279 He's promised to be way way faster than anything possibly were on a classical machine. 637 01:11:50.279 --> 01:11:58.020 Given our current knowledge, so I've been some other approaches on computing have been shown to be equivalent to. 638 01:11:58.020 --> 01:12:02.579 Do the game model approach and these are all known as universal. 639 01:12:03.630 --> 01:12:10.289 So, to be classified as a universe count computer, it needs to be sharing that there's a mapping of. 640 01:12:10.289 --> 01:12:14.130 The specialized date model algorithms to these other 4. 641 01:12:14.130 --> 01:12:18.899 It doesn't take up too much time. There's a polynomial time. 642 01:12:18.899 --> 01:12:22.439 Call the name, your results from the gate model approach. 643 01:12:22.439 --> 01:12:26.460 These other approaches isn't. 644 01:12:26.460 --> 01:12:31.380 A universal, however, it is related to 1 of the forms. 645 01:12:31.380 --> 01:12:35.850 Universal quantum computers form called adiabatic quantity. 646 01:12:36.960 --> 01:12:42.539 In fact, adiabatic, quantum computing is a specific form of quantum. 647 01:12:42.539 --> 01:12:46.770 Which also work on the process of energy minimization. 648 01:12:46.770 --> 01:12:51.510 So, it's just to say that quantum annealing and universe on computers are completely separate. 649 01:12:51.510 --> 01:12:55.560 There is a. 650 01:12:55.560 --> 01:12:59.039 So, there are described quantum annealing. 651 01:12:59.039 --> 01:13:02.250 The kind of things is useful. 652 01:13:02.250 --> 01:13:07.050 In my next video, I'm going to explain how works. 653 01:13:07.050 --> 01:13:20.130 Okay, and then this time we'll show the 1 more, and then we will finish. 654 01:13:20.130 --> 01:13:23.579 So. 655 01:13:23.579 --> 01:13:28.560 I actually have it linked in here. 656 01:13:28.560 --> 01:13:37.439 Silence. 657 01:13:44.250 --> 01:13:50.939 My last year I explain how to meaning relates to the other. 658 01:13:50.939 --> 01:13:54.689 Also have a kind of programs, so. 659 01:13:54.689 --> 01:13:59.399 This video I'm going to explain how the ultimate kneeling processor actually. 660 01:14:01.529 --> 01:14:06.510 So, let's start by looking at single cube now, if it can be in a state of either 0 or 1. 661 01:14:06.510 --> 01:14:09.779 These states from coded in a circulating current. 662 01:14:09.779 --> 01:14:15.420 A corresponding magnetic field, and because of the 2 corners, and we'll check. 663 01:14:15.420 --> 01:14:18.569 You can be in a superposition of the 0 state and the 1 state of the. 664 01:14:19.710 --> 01:14:22.920 And in the calls, meaning process, what happens is. 665 01:14:22.920 --> 01:14:30.750 The QB goes from the superposition state into either the 0 state 1 state, which classical States at the end. 666 01:14:30.750 --> 01:14:35.039 Physics of this process can be shown in an entity. 667 01:14:41.130 --> 01:14:45.000 To begin with is just 1 Valley, and the lowest point corresponds with the. 668 01:14:45.000 --> 01:14:52.560 Superposition state calls meetings, run a barrier is raised and this turns the energy diagram. 669 01:14:52.560 --> 01:14:59.670 Into what's known as a double well potential here the low point of the left Valley corresponds to the 0 state. 670 01:14:59.670 --> 01:15:03.390 The low point on the right corresponds to the 1, the state. 671 01:15:04.590 --> 01:15:08.250 And the camera will end up in 1 of these bodies at the end of the. 672 01:15:08.250 --> 01:15:11.430 It has it decide which 1? Well. 673 01:15:11.430 --> 01:15:17.310 Well, everything else be equal. The probability of the Cuba ending in the 0, to 1 state is. 674 01:15:17.310 --> 01:15:20.939 Eva is for 50 and need a state. 675 01:15:20.939 --> 01:15:25.260 And the interesting thing is you can actually control the probability of it. 676 01:15:25.260 --> 01:15:31.140 Fall into a 01, state is done by applying an external magnetic field to the. 677 01:15:31.140 --> 01:15:34.619 If anything this is to tilt the whole world potential. 678 01:15:34.619 --> 01:15:38.010 Increasing the probability of ending up in the lower. Well. 679 01:15:39.359 --> 01:15:46.020 This external magnetic field is called a bias and they keep it basically minimizing its energy and the presence of. 680 01:15:46.020 --> 01:15:54.270 This external magnetic silence. 681 01:15:54.270 --> 01:15:59.579 Okay, so being able to control the probability that a cube fall into the view of the 1 States. 682 01:15:59.579 --> 01:16:05.220 Through the real power of these processes come from these toddling from them together. 683 01:16:05.220 --> 01:16:10.319 Nigel start influencing and this is done with a device called a couple. 684 01:16:10.319 --> 01:16:14.609 A couple basically defined how few bits influencing. 685 01:16:22.079 --> 01:16:28.229 So, a couple I can make the 2 couple key ones that end up in the same state. So. 686 01:16:28.229 --> 01:16:36.510 That's either both 0 or both 1 conference and care which 1 of these is as long as the Cubans end up with the same stages. 687 01:16:36.510 --> 01:16:43.170 Or, alternatively, can make a neighboring through this once the. 688 01:16:43.170 --> 01:16:46.289 So, we, the 0, 1, 1, 0. 689 01:16:47.789 --> 01:16:53.399 When you put accompanying between 2 cubes, you're now using another phenomena in quantum physics. Cool. And. 690 01:16:53.399 --> 01:16:58.739 When to achieve, it's are in Tango now, have to be considered as a single. 691 01:16:58.739 --> 01:17:04.800 And now, which has got 4 States, so you can imagine a potential with 4 States. 692 01:17:04.800 --> 01:17:08.880 Each 1 corresponding to a different combination of the 2. 693 01:17:08.880 --> 01:17:13.649 The relative entities of these states depend on the boxes we need to. 694 01:17:13.649 --> 01:17:23.130 A company between now, when I said that for a couple of wants the Cubans to be the same, or wants them, to be honest. 695 01:17:23.130 --> 01:17:26.789 But I really mean is the couple of the meeting those states. 696 01:17:26.789 --> 01:17:33.720 Energetically favorable so, if a couple of wants the to achieve is to be the same. Really? What it's doing is lowering the energy of. 697 01:17:33.720 --> 01:17:41.939 Those 2 States in comparison to a couple of wants them to the opposite, then it's lowering the energy of those things. 698 01:17:43.380 --> 01:17:48.090 His team, they can have a BI supply to it and achievements can interact by the company. 699 01:17:48.090 --> 01:17:53.340 As a user, you can actually choose all the values for these biases and. 700 01:17:53.340 --> 01:17:59.850 Both the direction of them, and also the strength, and this is basically how a program. 701 01:17:59.850 --> 01:18:04.050 Peter choose a whole set of biases. The whole couple of things. 702 01:18:04.050 --> 01:18:07.590 That defines an energy landscape and then the quantity the. 703 01:18:07.590 --> 01:18:11.399 Does company to solve and find a minimum energy of that. 704 01:18:12.810 --> 01:18:17.550 It's now you can start to see some of the complex TV. 705 01:18:17.550 --> 01:18:22.680 2 few events of God for states, I can define energy landscape. 706 01:18:22.680 --> 01:18:26.520 Up to 3 events number of States goes up to 8. 707 01:18:26.520 --> 01:18:32.489 And for each extra cue that actually double the number of states, I can define anything landscape. 708 01:18:32.489 --> 01:18:37.020 For the number of States goes up exponentially with the number of few. 709 01:18:37.020 --> 01:18:41.399 Specifically, that relationship is to to the power of and. 710 01:18:41.399 --> 01:18:51.989 What is the number? Okay so let me summarize what I've talked about. 711 01:18:51.989 --> 01:18:55.649 And content, meaning you start off with the large set of clear of it. 712 01:18:55.649 --> 01:18:59.279 Means to you is superposition state 2. 0 1. 713 01:18:59.279 --> 01:19:06.119 And also, they're not connected yet, then they undergo the call to an evening when. 714 01:19:06.119 --> 01:19:09.359 And the bias is get introduced and the cube is all becoming tiny. 715 01:19:09.359 --> 01:19:16.079 This large quantum object then changes the probability of each cube. It will end up in the 0 1. 716 01:19:16.079 --> 01:19:19.470 And then finally, at the end of the email. 717 01:19:19.470 --> 01:19:23.760 Each Cuba ends up as either 01 in this final state. 718 01:19:23.760 --> 01:19:27.539 The minimum energy state of your problem, or 1 very close to. 719 01:19:27.539 --> 01:19:31.710 And all of this happened in chips and 20. 720 01:19:31.710 --> 01:19:39.989 Hey. 721 01:19:44.399 --> 01:19:53.699 Okay, that's enough for today. So I was showing you theory 1st, and then a couple of. 722 01:19:53.699 --> 01:19:58.949 Hardware implementations Monday I guess we'll get into more. 723 01:19:59.335 --> 01:20:11.755 Version of quantum computing C video or 2 from them, and get to see their online their simulator, and maybe run a program or 2 are loaded up into their quantum computing. 724 01:20:12.295 --> 01:20:17.005 And again you'll me a progress report or something Monday. And eventually some of the homeworks. 725 01:20:17.250 --> 01:20:21.119 Have a good weekend. See, you. 726 01:20:21.119 --> 01:20:25.109 Monday, stop snowing by then. 727 01:20:25.109 --> 01:20:29.970 Okay.