1 00:00:00,000 --> 00:00:04,019 okay. So, this week we are finally get ready to 2 00:00:04,019 --> 00:00:11,086 get the shores of in factoring numbers but before we can talk about that in today's 3 00:00:11,086 --> 00:00:18,025 lecture we have to build up some primitives for that will prove to be 4 00:00:18,025 --> 00:00:20,089 useful and in factoring. Okay. 5 00:00:20,089 --> 00:00:33,003 So, this primitive is called period finding And, in period finding, we are 6 00:00:33,003 --> 00:00:41,057 giving some function f. So F is some function that matches the 7 00:00:41,057 --> 00:00:48,070 numbers from. Zero to N minus one, so it's the domain of 8 00:00:48,070 --> 00:00:53,050 size capital N, and it maps it to some, some set S. 9 00:00:53,050 --> 00:01:01,012 S could be the numbers from zero to N minus one or it could be something else. 10 00:01:01,012 --> 00:01:06,021 We don't care. Now the, the property of F that we are, 11 00:01:06,021 --> 00:01:10,042 that we are promised is that F is periodic. 12 00:01:13,018 --> 00:01:18,098 And. Let's say, let's say the period is R. 13 00:01:18,098 --> 00:01:24,014 Say, it's periodic. With, period. 14 00:01:25,006 --> 00:01:32,071 R, except that this period R is secret. Okay. 15 00:01:32,071 --> 00:01:38,094 So, what do I mean by saying that f is periodic with period R. 16 00:01:38,094 --> 00:01:45,038 What I mean is, that f(x) = f(x+R). We off-course, this addition we are, we 17 00:01:45,038 --> 00:01:52,095 are going to do modulo n so that, so that x+r is always between zero and n-1, 18 00:01:52,095 --> 00:01:59,070 meaning if we overflow then we just subtract R and make sure that. 19 00:02:02,014 --> 00:02:06,035 Now this number is always between zero, and minus one. 20 00:02:07,015 --> 00:02:11,075 Okay. So this is true, for all X. 21 00:02:12,065 --> 00:02:16,098 And we also want to make sure that. This the only. 22 00:02:16,098 --> 00:02:22,002 Sort of you know. That, that other than this there's no. 23 00:02:22,002 --> 00:02:24,049 There's no equality. Meaning. 24 00:02:24,049 --> 00:02:34,014 What we want to make sure is that. We, we, we also want to say that if x is 25 00:02:34,014 --> 00:02:42,058 not congruent to y mode r then. F of x is not equal to f of y. 26 00:02:42,058 --> 00:02:51,041 Okay, so what, what do we mean by this, so, so what we have is, here's our, here's 27 00:02:51,041 --> 00:02:58,076 what our graph looks like. So here's, here's x, you know, let's say 28 00:02:58,076 --> 00:03:10,031 we go from zero to n minus one. Let's say f of x is, is just a number now 29 00:03:10,031 --> 00:03:11,091 for us. Right? 30 00:03:12,028 --> 00:03:18,056 And let's say that you know, that r was, was five. 31 00:03:18,056 --> 00:03:28,042 So, so for example, so if r equal to five, it might be that f of zero was, was this, 32 00:03:28,042 --> 00:03:37,005 f of one was that, f of two was, was that, f of three was that, f of four. 33 00:03:37,005 --> 00:03:38,036 What's that? Right? 34 00:03:38,036 --> 00:03:43,089 So, notice that half of zero is not equivalent to half of one is not 35 00:03:43,089 --> 00:03:48,019 equivalent to half of two and so on. All these are distinct. 36 00:03:48,019 --> 00:03:51,025 That's this condition. This condition says. 37 00:03:51,025 --> 00:03:57,091 They are distinct until you get to'R'. And now'R' is five, so'f' of'5', what 38 00:03:57,091 --> 00:04:01,096 should it be? It should be exactly'f' of zero. 39 00:04:01,096 --> 00:04:07,073 So, so, it mean it will be naught. What's'f' of'6'?'f' of'6' should be 40 00:04:07,073 --> 00:04:12,068 exactly'f' of'1'. So, it's naught.'f' of'7', it should be 41 00:04:12,068 --> 00:04:14,061 exactly naught. Right? 42 00:04:14,061 --> 00:04:18,083 So that's the condition that they are given. 43 00:04:18,083 --> 00:04:23,043 And think of N-1 as being, you know. N, N is large. 44 00:04:23,043 --> 00:04:28,012 So, sorry, so. You know, let's, let's have everything 45 00:04:28,012 --> 00:04:30,062 move over a little bit. So. 46 00:04:32,019 --> 00:04:38,011 Lets see that that's'x' going all the way out and that's in minus'1'. 47 00:04:38,011 --> 00:04:40,077 So, so this is very far. Note it. 48 00:04:40,077 --> 00:04:47,072 So we are working with, period'n' large, we are given a function which is, which is 49 00:04:47,097 --> 00:04:53,081 periodic'n', okay, so the challenge we have So. 50 00:04:54,066 --> 00:04:59,066 The challenge is to find R. Okay so this is very much like Symon's 51 00:04:59,066 --> 00:05:03,090 problem, right. There, there also we were given a function 52 00:05:03,090 --> 00:05:10,011 with some hidden property to it and then we wanted to find this, this secret right. 53 00:05:10,011 --> 00:05:16,032 There, there was a secret string and here we have a period R which we want to find 54 00:05:16,032 --> 00:05:19,058 out. Okay so again as in Symon's problem we 55 00:05:19,058 --> 00:05:23,098 are, what are we given about F. Well we are given a circuit. 56 00:05:24,068 --> 00:05:30,031 That computes amp. So they can get c sub f is a circuit, 57 00:05:30,031 --> 00:05:34,092 which is given to us as a black box, and we can input... 58 00:05:35,051 --> 00:05:41,063 'X' you know outputs'f' of'x'. And now the question is, how could you 59 00:05:41,063 --> 00:05:45,082 ever use this box, this circuit to compute out. 60 00:05:45,082 --> 00:05:53,031 Well, what you could do is you could keep, keep trying different'x'es until you get 61 00:05:53,031 --> 00:05:57,060 to whether, where'f' of'x' is equal to'f' of'I'. 62 00:05:57,060 --> 00:06:04,075 But then in order to do this, the number of times you have to try is, is some what, 63 00:06:04,075 --> 00:06:09,061 you know its, its, it gets large if, if N and R are large. 64 00:06:09,061 --> 00:06:16,058 So if R is exponentially large and N is exponentially large, then the number of, 65 00:06:16,058 --> 00:06:21,062 number of trials that you have to do grows exponentially. 66 00:06:21,062 --> 00:06:26,004 So that's the hard part, right. So, so the number of. 67 00:06:27,069 --> 00:06:34,083 Trials is proportionate to some function of R and N. 68 00:06:35,068 --> 00:06:39,035 Right? So you, you, you really have to try, you 69 00:06:39,035 --> 00:06:44,087 know, some number of tries. Which is, which, which grows quickly as r 70 00:06:44,087 --> 00:06:48,064 grows. Whereas, what we want is something that 71 00:06:48,064 --> 00:06:53,099 grows much, much more slowly. So what we'll see is that there's a 72 00:06:53,099 --> 00:07:08,070 quantum algorithm For this problem, that works in time, which grows binomially, in 73 00:07:08,070 --> 00:07:13,007 [inaudible]. Okay. 74 00:07:13,007 --> 00:07:19,066 So, so, so if you have a, you have a very fast quantum algorithm that's 75 00:07:19,066 --> 00:07:26,053 exponentially faster than the best classical algorithm for this problem. 76 00:07:26,053 --> 00:07:33,087 Okay so, so now, wha, what does this You know, what, what does this, quantum 77 00:07:33,087 --> 00:07:39,049 algorithm look like? Well, remember, you know, as we always 78 00:07:39,049 --> 00:07:47,048 did, what we, what we can do is given the circuit C sub F, we can, we can convert it 79 00:07:47,048 --> 00:07:55,000 into a quantum circuit U sub F, where we can now give a superposition over X as 80 00:07:55,000 --> 00:07:59,028 input. And now we, we normally have X as input 81 00:07:59,028 --> 00:08:06,040 but we also have. Some other, work bits and answer bits, and 82 00:08:06,040 --> 00:08:12,037 what we get as output. Is. 83 00:08:13,054 --> 00:08:18,031 X. And F of X. 84 00:08:19,010 --> 00:08:21,071 Right? Better in superpositions. 85 00:08:21,071 --> 00:08:28,020 Summa-, summation over alpha x, x, f of x. Okay, so that's what, that's, that's the 86 00:08:28,020 --> 00:08:34,053 box that we are given to play with. And what we want to do is, we want to, we 87 00:08:34,053 --> 00:08:40,069 want to very quickly figure out how to, you know what this, what this R is. 88 00:08:40,069 --> 00:08:44,076 Okay. So, how does the algorithm for this work? 89 00:08:44,076 --> 00:08:51,055 Well it turns out that it, it works very similarly to [inaudible] algorithm. 90 00:08:51,055 --> 00:08:56,017 So the, the algorithm for, for the quantum algorithm. 91 00:08:58,075 --> 00:09:06,021 For period finding. The second faith looks very similar to the 92 00:09:06,021 --> 00:09:12,095 second that your used to. So what we do is we start with the circuit 93 00:09:12,095 --> 00:09:19,055 like the Hadamard transform, except now what we'll call it is the quantum Fournier 94 00:09:19,055 --> 00:09:24,095 transform. [inaudible]. 95 00:09:24,095 --> 00:09:33,075 And if [inaudible]. Zero into this into this quantum transform 96 00:09:33,075 --> 00:09:41,089 you get it's output. You feed that into this function f, the 97 00:09:41,089 --> 00:09:49,058 periodic function. [inaudible] zeros, you get some output. 98 00:09:51,039 --> 00:09:53,096 Right? You take this output. 99 00:09:53,096 --> 00:10:00,060 So, so here you'ld have, F of X. So this is some super position of all X. 100 00:10:01,046 --> 00:10:11,070 Here you get some of the all X. Of x, f(x). 101 00:10:11,070 --> 00:10:17,066 So I am just giving you an overview of what this quantum theory of finding is 102 00:10:17,066 --> 00:10:22,039 going to look like. We are going to come back and look at this 103 00:10:22,039 --> 00:10:26,036 in detail. But this is just to give a big picture of 104 00:10:26,036 --> 00:10:32,017 where we are going with all of this. So, so now you feed this so, so as before 105 00:10:32,017 --> 00:10:36,083 what we do is we, we measure this output and we throw it away. 106 00:10:36,083 --> 00:10:41,023 And remember from what we said. If you are going to measure and throw 107 00:10:41,023 --> 00:10:44,010 away, you can also just throw away the output. 108 00:10:44,010 --> 00:10:48,063 So if you ignore this output, F of X, that, that, that's the same thing as 109 00:10:48,063 --> 00:10:51,057 though you measured it. And now we [inaudible]. 110 00:10:51,057 --> 00:10:56,042 What's left. And do another quantum [inaudible] 111 00:10:56,042 --> 00:10:58,001 transform. [inaudible]. 112 00:10:59,048 --> 00:11:13,037 And this answer is going to reveal to us what the period R is So, if he, if he let 113 00:11:13,037 --> 00:11:21,054 this answer be "L", Then the claim is. So, so this our output. 114 00:11:21,054 --> 00:11:27,041 So the, the, the claim that we make is that L. 115 00:11:29,024 --> 00:11:37,008 Divided by N is a very close approximation to. 116 00:11:39,037 --> 00:11:45,035 Some, multiple of one over r. So it's a, it's a rational number of the 117 00:11:45,035 --> 00:11:47,069 form, k over r. Okay. 118 00:11:47,069 --> 00:11:57,015 And because we know, we know L, we know N, what we can do is, we can, you know, if. 119 00:11:57,015 --> 00:12:06,044 So, so the claim is that if. If m is much, much larger than r, then 120 00:12:06,044 --> 00:12:14,079 there are, there's a certain procedure by which you can actually use the fact that, 121 00:12:14,079 --> 00:12:20,049 you know, you can use the fact that you're given l and m. 122 00:12:20,080 --> 00:12:26,024 You can efficiently. Reconstruct r. 123 00:12:27,075 --> 00:12:33,005 Okay so this is the primitive that we are we are trying to you know, we are trying 124 00:12:33,005 --> 00:12:38,016 go through we are trying to develop and this is going to be a primitive that's 125 00:12:38,016 --> 00:12:43,028 used in factory Okay, now, let me just say one other thing. 126 00:12:43,028 --> 00:12:49,038 So, it turns out that it's much, much easier to develop this primitive in a 127 00:12:49,038 --> 00:12:56,015 special case, and that's the case that we'll be, we'll be discussing for most of 128 00:12:56,015 --> 00:13:02,083 this lecture and most of the next lecture. And then if there's a chance, I'll tell 129 00:13:02,083 --> 00:13:09,002 you about the general case you know, which is what I talked about so far. 130 00:13:09,002 --> 00:13:15,050 So in the special case, what we'll assume. Is that, now remember, you have your 131 00:13:15,050 --> 00:13:22,071 function, F, which maps. The domain of size, cardinality, and to 132 00:13:22,071 --> 00:13:32,079 something, F. F of X equal to F of X plus R, more N 133 00:13:32,079 --> 00:13:37,095 [inaudible] x. We'll also make one more assumption. 134 00:13:37,095 --> 00:13:44,023 We'll also assume that R divides N, that N is a multiple of R. 135 00:13:44,023 --> 00:13:52,058 This is going to be useful for us because, you know, in, when, when R divides N, then 136 00:13:52,058 --> 00:13:59,049 this is, this is our situation. So you have, this is X, this is F of X. 137 00:13:59,049 --> 00:14:06,023 And you have, you know, F of X might. You know, let's, let's say, let's say f of 138 00:14:06,023 --> 00:14:11,055 x looks like this. And that's r minus one, that's zero, and 139 00:14:11,055 --> 00:14:19,048 then it looks the same, looks the same, so on and you get to n minus one. 140 00:14:19,098 --> 00:14:24,000 And it's the same. Right so, so we don't cut off in the 141 00:14:24,000 --> 00:14:29,013 middle, and it turns out that having this, having the pattern actually complete makes 142 00:14:29,013 --> 00:14:33,023 things a lot easier to analyze. And that's what they're going to be 143 00:14:33,023 --> 00:14:37,076 talking about for most of this and the next lecture, and then if there's a 144 00:14:37,076 --> 00:14:42,053 chance, I'll tell you about what happens in the general case, and it's not that 145 00:14:42,053 --> 00:14:46,038 much more difficult, but, but it's just easier to talk like this. 146 00:14:46,038 --> 00:14:49,042 Okay, so. All right, so, so where does all this 147 00:14:49,042 --> 00:14:52,081 leave us? Now we've, now that leaves us, we've got 148 00:14:52,081 --> 00:14:58,054 to understand what this quantum Fourier transform is, which was the analog of the 149 00:14:58,054 --> 00:15:02,007 Hademard transform that we talked about last time. 150 00:15:02,007 --> 00:15:04,062 Okay so let's, let's move on to that.