1 00:00:00,000 --> 00:00:04,005 Hi, everyone. This is the last lecture for this class 2 00:00:04,005 --> 00:00:10,007 and what I wanted to do in this last lecture is give you an overview about 3 00:00:10,007 --> 00:00:16,003 quantum complexity theory. So you know one lecture's obviously not 4 00:00:16,003 --> 00:00:23,003 sufficient to do justice to this subject. And so, in parts the lecture is going to 5 00:00:23,003 --> 00:00:27,001 be very, you know its going to be very sketchy. 6 00:00:27,001 --> 00:00:32,048 I'll, I'll sort of sketch for you a picture of the subject at a high level. 7 00:00:32,048 --> 00:00:38,057 And I don't really expect you to follow all of it or even much of it but, you 8 00:00:38,057 --> 00:00:44,040 know, if, if you get a, if you get a sense of what the subject is about and whether 9 00:00:44,040 --> 00:00:49,007 you are interested in it, I'll feel that's, that's a successful lecture. 10 00:00:49,007 --> 00:00:55,004 Okay, so, so try to follow as much as you can and if you can't, you know well, you 11 00:00:55,004 --> 00:01:01,001 can skip, skip past most of this, or you know, just get a sense of what's, what's, 12 00:01:01,001 --> 00:01:06,032 what the subject is about. Okay, so in the first part of this, in the 13 00:01:06,032 --> 00:01:12,074 first video, I'm going to talk about the lower band for quantum search, and what it 14 00:01:12,074 --> 00:01:18,003 tells us about quantum algorithms for any incomplete problems. 15 00:01:18,027 --> 00:01:25,041 Okay so remember what the, what, what the search problem was, the, the unstructured 16 00:01:25,041 --> 00:01:31,015 search problem. So we think about having, you know we, we 17 00:01:31,015 --> 00:01:39,038 are looking for a needle in a, in a hay stack or digital needle in a digital hay 18 00:01:39,038 --> 00:01:43,027 stack. So, so a digital hay stack is a, is a 19 00:01:43,027 --> 00:01:50,053 table with the with the capital N equal to two to the little n entries. 20 00:01:50,053 --> 00:01:57,040 And one of these entries is marked and, and, so this is the proverbial needle, and 21 00:01:57,040 --> 00:02:02,081 we are searching for this entry. So we, we said that there's a theorem that 22 00:02:02,081 --> 00:02:09,019 last, in the last lecture that any quantum algorithm must take at least square root 23 00:02:09,019 --> 00:02:12,097 of n time. Actually what we meant by square root n 24 00:02:12,097 --> 00:02:19,021 time is, it must make at least square root of capital N queries to this table. 25 00:02:19,021 --> 00:02:24,090 And since square root of capital N is two to the little n over two. 26 00:02:24,090 --> 00:02:29,006 This is exponential time in the length of the input. 27 00:02:29,006 --> 00:02:35,040 So let me, let me again say, what, what our, you know what our setting is. 28 00:02:35,040 --> 00:02:43,035 We think of this table as being specified by some, some circuit. 29 00:02:43,035 --> 00:02:50,040 So, some circuit that computes some function f, so that when input x, it 30 00:02:50,040 --> 00:02:56,064 outputs f(x), which is either zero or one, so it's a Boolean function. 31 00:02:56,064 --> 00:03:03,097 And f(x) equal to one says that x is a marked element, and zero says it's 32 00:03:03,097 --> 00:03:08,090 unmarked. So, the length of the input x, x is an n 33 00:03:08,090 --> 00:03:12,058 bit string. So the length of x is n bits. 34 00:03:12,058 --> 00:03:19,013 And so the, the running time, the number of queries is exponential in the, in the 35 00:03:19,013 --> 00:03:23,046 length of x. Okay, so, how do we prove such a theorem? 36 00:03:23,046 --> 00:03:29,094 So first let's, let's show that using one quantum query, there's, there's no, no 37 00:03:29,094 --> 00:03:36,053 quantum algorithm that can guarantee a success probability larger than some 38 00:03:36,053 --> 00:03:39,085 constant over N. Probably four over N. 39 00:03:39,085 --> 00:03:43,051 So, here's how, here's how we, we argue this. 40 00:03:43,051 --> 00:03:48,046 So, let's perform a test, test run with an empty haystack. 41 00:03:48,046 --> 00:03:54,062 By this I mean, that there's no marked element in this, in this haystack. 42 00:03:54,062 --> 00:03:58,053 Okay? No marked element in this table. 43 00:03:58,053 --> 00:04:04,030 And now, suppose that the algorithm makes this query. 44 00:04:04,030 --> 00:04:11,024 Sum over all x, alpha xx. Now remember, for this to be normalized, 45 00:04:11,024 --> 00:04:17,045 the sum of alpha x magnitude squared must be equal to one. 46 00:04:17,045 --> 00:04:23,078 So there are some alpha. So there is, there is some x, such that 47 00:04:23,078 --> 00:04:29,056 alpha sub x squared is less than or equal to one over n. 48 00:04:29,056 --> 00:04:32,027 Right? Just by averaging. 49 00:04:32,027 --> 00:04:36,074 In fact if we, if we pick a typical X it has this property. 50 00:04:36,074 --> 00:04:44,012 Okay so now what we do is, mark that element, so we mark that x for which alpha 51 00:04:44,012 --> 00:04:51,064 x magnitude squared is small as possible. So now, when we make this query, when the, 52 00:04:51,064 --> 00:04:56,067 you know, the algorithm doesn't know where, where the marked element is so, so 53 00:04:56,067 --> 00:05:01,065 it of course, once we put the marked element there, it still makes the same 54 00:05:01,065 --> 00:05:05,026 query. And so it queries the marked element with 55 00:05:05,026 --> 00:05:16,095 amplitude, you know, with amplitude so the amplitude with which it, it varies this, 56 00:05:16,095 --> 00:05:23,012 this, this particular element. Let's call it X star. 57 00:05:23,012 --> 00:05:31,067 You know, the, the, the magnitude of the amplitude is at most one over square root 58 00:05:31,067 --> 00:05:32,051 of N. Okay. 59 00:05:32,051 --> 00:05:38,062 And so now, what we are, what we're going to argue is that the final state of the 60 00:05:38,062 --> 00:05:42,062 algorithm, if you look at the quantum state of the algorithm. 61 00:05:42,062 --> 00:05:47,092 You know, so if you have the quantum algorithm, you, you look at the final, the 62 00:05:47,092 --> 00:05:52,021 final state psi which you are now going to measure. 63 00:05:52,021 --> 00:06:00,008 Well, psi was something you know psi had some value when, when we performed the 64 00:06:00,008 --> 00:06:05,074 test run. And now what we're saying is psi cannot be 65 00:06:05,074 --> 00:06:14,088 changed by very much. You know when we, when we actually run it 66 00:06:14,088 --> 00:06:21,096 on the table with a, with a marked element, it can change by utmost one over 67 00:06:21,096 --> 00:06:28,002 square root of N in euclidean distance. And so, what that implies if you work 68 00:06:28,002 --> 00:06:35,025 through it, is that, is that the chance that your measurement outputs, a different 69 00:06:35,025 --> 00:06:42,065 value than it did in the case of the empty, empty haystack or the new marked 70 00:06:42,065 --> 00:06:44,092 element. Is, is very small. 71 00:06:44,092 --> 00:06:51,001 It's, it's smaller than constant over n. It's smaller than some constant times 72 00:06:51,001 --> 00:06:55,009 this, the square of this value. Okay, and that shows that one quantum 73 00:06:55,009 --> 00:07:00,008 query cannot possibly help. So now, what we'd like to do is, we'd like 74 00:07:00,008 --> 00:07:05,004 to generalize this, this, this particular argument to many steps. 75 00:07:05,004 --> 00:07:13,073 So suppose, suppose our algorithm now makes, so our quantum algorithm makes t 76 00:07:13,073 --> 00:07:18,009 steps, for sum t. Now, how does, how does the success 77 00:07:18,009 --> 00:07:26,002 probability of the algorithm vary? You know, how, how does it increase as T 78 00:07:26,002 --> 00:07:31,001 increases? So, what we are actually going to show, is 79 00:07:31,001 --> 00:07:40,092 that the probability of success is going to, is going to grow only as T squared 80 00:07:40,092 --> 00:07:45,008 over N. And this is why, if you want any 81 00:07:45,008 --> 00:07:51,088 significant success probability you'll have to use T to be about square root of 82 00:07:51,088 --> 00:07:58,002 N. Okay, now the, the argument for doing this 83 00:07:58,002 --> 00:08:04,019 is very similar to what we did, in the in the previous case where we, where we had 84 00:08:04,019 --> 00:08:09,097 only one, query. So what we're going to do is perform the 85 00:08:09,097 --> 00:08:14,006 test run with the empty haystacks so no marked element. 86 00:08:14,006 --> 00:08:19,036 So run, you know whatever algorithm we, we, w have, We are going to show there is 87 00:08:19,036 --> 00:08:24,003 some, some marked element. Such that if, if, you know some location 88 00:08:24,003 --> 00:08:29,008 so that the marked element is there, then this algorithm is going to do badly. 89 00:08:29,008 --> 00:08:35,000 It's, it's going to succeed with probability at most or the t square of N. 90 00:08:35,000 --> 00:08:39,001 So what do we do? We do the test run with empty tester, with 91 00:08:39,001 --> 00:08:43,004 no marked element. Now, we find that element which is queried 92 00:08:43,004 --> 00:08:48,093 the, with the minimum squared amplitude. So, we, we look in every step and we see 93 00:08:48,093 --> 00:08:55,048 with what squared amplitude does, does the location x get queried over all these T 94 00:08:55,048 --> 00:08:59,080 steps? And I find that X for which this, this is, 95 00:08:59,080 --> 00:09:04,003 is minimized. And now we put the, you know we call that 96 00:09:04,003 --> 00:09:08,011 particular x, x star and we make that the marked element. 97 00:09:08,011 --> 00:09:14,020 And now what we'd like to do is we'd like to show that, in fact, if we, if we now 98 00:09:14,020 --> 00:09:19,091 run our algorithm on this, on this particular table, with this particular 99 00:09:19,091 --> 00:09:26,036 marked element, then the quantum algorithm is unable to distinguish this from the 100 00:09:26,036 --> 00:09:30,036 empty haystack, case. Except with very small amplitude. 101 00:09:30,036 --> 00:09:35,075 So the final state of the algorithm is almost indistinguishable from the case 102 00:09:35,075 --> 00:09:41,020 where there was no marked element. Now, the difficulty in doing all this is 103 00:09:41,020 --> 00:09:46,014 that, is that the subsequent queries, query amplitudes, change depending upon 104 00:09:46,014 --> 00:09:49,082 previous answers. So, so you know as, as the algorithm runs, 105 00:09:49,082 --> 00:09:55,013 it doesn't make, you know its, its subsequent queries do not act as the same 106 00:09:55,013 --> 00:09:59,013 way that they did. The, the queries don't look, look like 107 00:09:59,013 --> 00:10:03,085 what they did, when we did the test run. They now diverge more and more, and in 108 00:10:03,085 --> 00:10:08,009 fact one might even suspect that they diverge exponentially. 109 00:10:08,009 --> 00:10:14,002 So, so what we have to do is show that the, the queries, you know somehow the, 110 00:10:14,002 --> 00:10:19,007 the run cannot diverge very much. Okay so, so I don't want to spend too much 111 00:10:19,007 --> 00:10:24,003 time on this argument but I'll just give you the gist of it. 112 00:10:24,003 --> 00:10:27,007 So this is what's called the hybrid argument. 113 00:10:27,007 --> 00:10:31,004 It's probe by what's called the hybrid argument. 114 00:10:32,001 --> 00:10:39,044 Which is one of the very basic arguments, you know ways of, of pounding, running 115 00:10:39,044 --> 00:10:45,041 times of quantum algorithms. So, the first thing we do is we spread out 116 00:10:45,041 --> 00:10:50,029 the quantum circuit. So, so that only one gate is being applied 117 00:10:50,029 --> 00:10:53,096 at a time. Now, of course you know, in the quantum 118 00:10:53,096 --> 00:10:59,023 circuit maybe there many gates acting in parallel, but then we can always delay 119 00:10:59,023 --> 00:11:03,000 some of the gates. So if there five gates acting in parallel, 120 00:11:03,000 --> 00:11:08,001 we could just have one of them act, act first and then the second one and then the 121 00:11:08,001 --> 00:11:12,062 third one and it makes no difference to their actual workings of the quantum 122 00:11:12,062 --> 00:11:17,004 circuit, it only delays the output, you know it makes it run slower. 123 00:11:17,004 --> 00:11:20,002 So, but we don't care, we have plenty of time. 124 00:11:20,002 --> 00:11:27,055 So, here's our quantum circuit. It, it applies some unitary U1 and then 125 00:11:27,055 --> 00:11:32,004 some unitary U2, U3. U sub T. 126 00:11:32,004 --> 00:11:39,005 But now, there's one other aspect that we, we, we really must, fix which is, is this 127 00:11:39,005 --> 00:11:44,004 a test run or is this, is this the real run of the algorithm? 128 00:11:44,004 --> 00:11:51,015 So, so let's say that we say that we have our function F which is identically zero, 129 00:11:51,015 --> 00:11:55,093 so this was our test run. And then we use this to identify a 130 00:11:55,093 --> 00:12:02,005 function F prime such that F prime of X star equal to one, and it's zero 131 00:12:02,005 --> 00:12:06,063 everywhere else. So, this was our real run of the 132 00:12:06,063 --> 00:12:08,009 algorithm. Okay. 133 00:12:08,009 --> 00:12:13,004 So, so let's, let's say up here we have the test run. 134 00:12:14,000 --> 00:12:21,001 So, this is, so whenever it calls in Oracle, whenever it calls F, so that's, 135 00:12:21,001 --> 00:12:32,073 that's the test run. And then down here, we have, we have the 136 00:12:32,073 --> 00:12:43,021 real run of the algorithm. Whenever we make a query, we make a query 137 00:12:43,021 --> 00:12:51,085 to F prime. And what we'd like to do is we'd like to 138 00:12:51,085 --> 00:12:59,016 say that, that, the output here, the output state here, psi prime is very close 139 00:12:59,016 --> 00:13:05,047 to the output state here, psi. These two are not very far from each 140 00:13:05,047 --> 00:13:09,060 other. And so the way we'll do this is we are 141 00:13:09,060 --> 00:13:16,097 going to modify the test run into the, into the actual run one step at a time. 142 00:13:16,097 --> 00:13:27,017 So what I mean by this is that we'll do a, a run where everything is like the, 143 00:13:27,017 --> 00:13:33,086 everything looks like the test run. Okay? 144 00:13:33,086 --> 00:13:45,036 Except for the last step is done, as though we were doing the real one at the 145 00:13:45,036 --> 00:13:51,049 algorithm, okay? So now what we want to do is we want to 146 00:13:51,049 --> 00:14:00,068 say, how different is, this outputs psi one from psi? 147 00:14:00,068 --> 00:14:08,015 And the answer is, well, it's very much like, you know so well, there's only one 148 00:14:08,015 --> 00:14:13,004 query that's changed between, between, between these two runs. 149 00:14:13,004 --> 00:14:19,008 But we know how to analyze one query. All it does is it changes the output state 150 00:14:19,008 --> 00:14:25,007 by roughly one over square root N. So, so in other words, what it did was, if 151 00:14:25,007 --> 00:14:34,000 this was the output state psi. Then, then what it did was it changed it 152 00:14:37,004 --> 00:14:44,028 to some new state which is roughly one over square root N of a from the, from the 153 00:14:44,028 --> 00:14:47,084 old one. In some direction we don't know, we don't 154 00:14:47,084 --> 00:14:54,041 know in which direction the change is, but it's, it's at most one over square root of 155 00:14:54,041 --> 00:14:57,000 N. So, now we repeat this process. 156 00:14:57,004 --> 00:15:06,034 And we do one more run which still looks almost like the test run. 157 00:15:06,034 --> 00:15:22,064 Except, now the last two steps look like the real run of the algorithm. 158 00:15:22,064 --> 00:15:26,048 So we make queries to F prime. Okay. 159 00:15:26,048 --> 00:15:37,089 So now, how different is this output psi two from psi? 160 00:15:37,089 --> 00:15:44,012 Well, in order to analyze that, let's just understand how differences psi two from 161 00:15:44,012 --> 00:15:48,000 psi one. Well, the only difference between these 162 00:15:48,000 --> 00:15:54,001 two, of course lies in one step. Okay so we know what, how different the 163 00:15:54,001 --> 00:16:00,007 output of this one step is in these two cases at most one over square root N. 164 00:16:00,007 --> 00:16:04,004 But this is not the last step of the algorithm. 165 00:16:04,004 --> 00:16:10,052 For surely this is a different situation. So, so we can say that before the last 166 00:16:10,052 --> 00:16:16,016 step of the algorithm, the, the, the, the input to the last step of the algorithm in 167 00:16:16,016 --> 00:16:20,031 these two cases differs by at most one over square root N. 168 00:16:20,031 --> 00:16:25,063 The, the input vectors in the two cases differ by at most one over square root N. 169 00:16:25,063 --> 00:16:30,061 But now remember there's, there's this crucial fact about quantum computation, 170 00:16:30,061 --> 00:16:35,098 which is quantum evolution is unitary, meaning this last step, whatever it was, 171 00:16:35,098 --> 00:16:40,013 it's the same in both cases. We are applying the same unitary 172 00:16:40,013 --> 00:16:45,082 transformation. So if you give two inputs which, which 173 00:16:45,082 --> 00:16:52,065 make a certain angle with each other, then this last step is going to preserve that 174 00:16:52,065 --> 00:16:55,053 angle. So it's going to preserve the distance 175 00:16:55,053 --> 00:16:59,072 between the two vectors. So psi one and psi two are going to differ 176 00:16:59,072 --> 00:17:06,044 by at most one over square root N. Again, we don't know in which direction, 177 00:17:06,044 --> 00:17:11,093 but we know that they can be at most one over square root N apart. 178 00:17:11,093 --> 00:17:18,015 So we proceed this way, making one change at a time until we get back to the 179 00:17:18,015 --> 00:17:21,074 original, you know the, the actual circuit. 180 00:17:21,074 --> 00:17:28,041 And we realize that, that we that, that our state moves in t steps, the each step 181 00:17:28,041 --> 00:17:32,003 changes the state by one over square root N.