1 00:00:00,000 --> 00:00:09,002 Okay. So, in this video I'm going to describe Simon's algorithm. Which includes 2 00:00:09,025 --> 00:00:16,010 a new way of setting up quantum state which we are going to perform, perform for 3 00:00:16,010 --> 00:00:22,071 a sampling on. In such a way that it gives us an exponential speed up over any 4 00:00:22,071 --> 00:00:28,054 classical algorithm. So here's the, here's the problem that we are going to be 5 00:00:28,054 --> 00:00:34,062 solving. We are given a function from n bits to n bits and we have, we have a 6 00:00:34,062 --> 00:00:41,076 promise that it's a two to one function. And it's two to one in this very special 7 00:00:41,076 --> 00:00:48,069 way. So there's a secret string s, which is an n bit string, such that f of x equal 8 00:00:48,069 --> 00:00:58,001 to f of x plus s where plus in this, in this funny symbol means it's bit-wise sum 9 00:00:58,001 --> 00:01:10,041 of two. So, so for example you know, if n is three and s is one, zero, one, then, we 10 00:01:10,041 --> 00:01:18,056 must have the case that, for example, zero, zero, zero plus one, zero, one. If 11 00:01:18,056 --> 00:01:26,074 you do a bit-wise sum, that's one, zero, one. Then, f of this must be equal to f of 12 00:01:26,074 --> 00:01:39,018 that. Or, for example, if let's do a more non-trivial example, so suppose x is zero, 13 00:01:39,018 --> 00:01:51,066 one, one. This was s, was one, zero, one, and x bit by sum with s is just zero, one, 14 00:01:51,066 --> 00:02:00,040 one, zero. So, you just threw out all the carries when you do the summation. So 15 00:02:00,040 --> 00:02:13,035 here's, here's our table for f of x so, so you can, you can see that you know, this, 16 00:02:13,035 --> 00:02:23,035 this table has f of zero, one, one is, is that and f of one, one, zero is also the 17 00:02:23,035 --> 00:02:31,083 same value, right? This is the property that, that we wanted that, that the 18 00:02:31,083 --> 00:02:39,016 function is two to one. They're, they're exactly two values of x which, which map 19 00:02:39,016 --> 00:02:45,053 to the same thing, in this case, one, zero, zero. And what are these two values? 20 00:02:45,053 --> 00:02:51,065 They are, you know, they, they satisfy this relations that this is equal to this 21 00:02:51,065 --> 00:02:57,042 plus one, zero, one. Or, this is equal to this plus one, zero, one in this bit wise 22 00:02:57,042 --> 00:03:02,079 sum manner. So now, our challenge is to find s. So, how we can do this? Well, 23 00:03:02,079 --> 00:03:09,012 let's first try to understand how we could do this classical, you know? What would a 24 00:03:09,012 --> 00:03:18,060 classical algorithm look like? So, once again, we are given this function f in the 25 00:03:18,060 --> 00:03:25,058 form of a circuit which compu tes it. And moreover, the circuit you know, is, is, is 26 00:03:25,058 --> 00:03:31,077 i n the form of a b lack box so we can't open up the circuit to look what's going 27 00:03:31,077 --> 00:03:36,042 on inside. All we can do is feed in different inputs. And so, well, we could 28 00:03:36,042 --> 00:03:42,000 just keep trying different inputs. But, until we see two different inputs which, 29 00:03:42,000 --> 00:03:47,040 which give us the same output, we are out of luck because there's no way we could 30 00:03:47,040 --> 00:03:55,092 know what s is until we see a collision. But how, how many, how many x's do we have 31 00:03:55,092 --> 00:04:05,035 to sample before we see a collision? Well, since there are, n different values, it 32 00:04:05,035 --> 00:04:13,002 turns out you know, you, you know, that by the birthday paradox, you, you, you can 33 00:04:13,002 --> 00:04:19,000 actually find a collision in, if you sample square root n of these values at 34 00:04:19,000 --> 00:04:31,054 random, which is two to the n over two. But, it turns out that also, in addition 35 00:04:31,054 --> 00:04:37,060 to the birthday paradox giving you that, this is a, this is a good bound, you can 36 00:04:37,060 --> 00:04:43,063 do it within this number of steps, it actually turns out that you don't get, you 37 00:04:43,063 --> 00:04:49,052 know, the chances that you can find a collision in much less than this number of 38 00:04:49,052 --> 00:04:55,062 trials is negligible. And so, classically, you can do no better than two to the n 39 00:04:55,062 --> 00:05:04,018 over two steps. So it takes exponential time to solve this problem classically. 40 00:05:04,018 --> 00:05:10,044 So, what we're going to see is how to use again, this Hadamard transform, this 41 00:05:10,044 --> 00:05:18,076 Fourier sampling to solve this problem using a quantum algorithm in only 42 00:05:18,076 --> 00:05:26,004 polynomial time, polynomial n number steps. Okay. So, so, this, this algorithm 43 00:05:26,033 --> 00:05:33,005 Simon's algorithm works like this. So, it works, it works in three steps. In the 44 00:05:33,005 --> 00:05:40,052 first step, we set up an appropriate superposition. The superposition is going 45 00:05:40,052 --> 00:05:48,088 to be an equal superposition over these two strings, r and r plus s, where r is a 46 00:05:48,088 --> 00:06:07,028 random and bit string. Okay. In the second step, we are going to, we are going to do 47 00:06:07,028 --> 00:06:14,002 a four year sampling of this, of this superposition. So remember, this is a 48 00:06:14,002 --> 00:06:21,004 superposition over two n bit strings you know, there's n bit string r. And then 49 00:06:21,004 --> 00:06:26,007 there's the bit-wise sum of r and s, where s is what we are looking for. So it turns 50 00:06:26,007 --> 00:06:31,072 out when you do, when you compute the Hadamard tran sform and you sample, and 51 00:06:31,072 --> 00:06:40,002 you measure, what you see is a rando m n bit string y, where y satisfies the linear 52 00:06:40,002 --> 00:06:47,083 equation y dot s is zero mark two. So, what do I mean by that? I mean that if, if 53 00:06:47,083 --> 00:06:56,041 y equal to y1 through yn, so these are the bits of y. S is equal to s1 through sn, 54 00:06:56,041 --> 00:07:05,099 then the linear equation is, that we have, is that y1, s1 plus yn, sn is polynomial 55 00:07:05,099 --> 00:07:17,050 to zero mark two. And so now, what we are going to do is repeat this process n minus 56 00:07:17,050 --> 00:07:25,070 one times. So we get n minus one such, such linear equations. Okay? So, so we 57 00:07:25,070 --> 00:07:33,020 have linear equations, let, let me call it, let me call it you know, let me call 58 00:07:33,020 --> 00:07:49,002 this the first linear equation and this is the n minus first linear equation. 59 00:07:49,002 --> 00:07:56,050 Remember these, y's are all known. And so what you can do is, you can solve these 60 00:07:56,050 --> 00:08:04,007 linear equations and as long as they are full rank, the n minus one equations, n 61 00:08:04,007 --> 00:08:10,003 unknown so you'll get exactly two solutions, since we are working more two. 62 00:08:10,003 --> 00:08:16,032 And so you'll be able to pin down all but one of the variables that takes on two 63 00:08:16,032 --> 00:08:22,008 different values, and it turns out one of the solutions will be of course the all 64 00:08:22,008 --> 00:08:28,006 zero solution because, because it's a homogeneous set. And the other solution 65 00:08:28,006 --> 00:08:35,001 will give us what the value of s is. Okay, that's the overall plan for the, for the 66 00:08:35,001 --> 00:08:40,009 algorithm. So now, what we have to show you is, how to set up this initial 67 00:08:40,009 --> 00:08:45,096 superposition to show that for your sampling will give us such a linear 68 00:08:45,096 --> 00:08:52,069 equation and that if you repeat n minus one times, there is a very good chance 69 00:08:52,069 --> 00:08:58,090 that we'll get all these n minus one, linear equations are going to be 70 00:08:58,090 --> 00:09:08,044 independent so that when we solve them, we can, we, we actually get a unique solution 71 00:09:08,044 --> 00:09:17,053 s. Okay. So, remember as before since we are given this function f, we can create a 72 00:09:17,053 --> 00:09:28,065 quantum circuit that input, on input x and zeroes outputs x and f of x. Okay. So, so 73 00:09:28,065 --> 00:09:39,064 now, how do we proceed? So, what we want, okay, so we, we start with, with I said 74 00:09:39,064 --> 00:09:48,003 you know, inputs in all in the states zero. We first do a Hadamard transform on 75 00:09:48,003 --> 00:09:58,048 any of these input bits. So, so we, we end of the superposition over all x of n bits, 76 00:09:58,048 --> 00:10:08,025 of x with amplitude one over two to the n over two. Now we feed t his, this 77 00:10:08,025 --> 00:10:17,016 superposition through the, through the, in, through our circuit for computing f. 78 00:10:17,016 --> 00:10:27,053 And so what this output of this circuit is going to be is, in the second register, 79 00:10:27,053 --> 00:10:38,029 it'll, it'll contain f of x. And now we go ahead and measure this, this second 80 00:10:38,029 --> 00:10:50,000 register to see what f of x looks like. So now, what does f of x look like? Well, if 81 00:10:50,000 --> 00:10:58,062 we were to, if we were to look at this example, then we'd have a super position 82 00:10:58,062 --> 00:11:04,074 over all these values. Right? So the first register would contain, you know, with, 83 00:11:04,074 --> 00:11:10,027 with, with amplitude one over two, one over square root of eight. It would 84 00:11:10,027 --> 00:11:15,088 contain, the first register would be zero, zero, zero and the second register would 85 00:11:15,088 --> 00:11:20,087 be zero, zero, zero, with amplitude one over square root eight. This would be the 86 00:11:20,087 --> 00:11:26,074 first two registers and so on. But now we go ahead and measure the second register. 87 00:11:26,074 --> 00:11:32,061 Okay. So we'll get one of these, you know, each of the outcomes with equal 88 00:11:32,061 --> 00:11:39,019 probability. And suppose we happen to pick out suppose the outcome happened to be 89 00:11:39,019 --> 00:11:44,086 one, zero, zero. So what's the, what's the, what's the new state of the system? 90 00:11:44,086 --> 00:11:50,076 Well, the answer is, in order to figure out the new state of the system what we 91 00:11:50,076 --> 00:11:57,069 must do is, we must, we must cross out all the parts of the superposition which are 92 00:11:57,069 --> 00:12:03,038 inconsistent with this, which is these and all of these. And then, what's the new 93 00:12:03,038 --> 00:12:10,042 state of the system? It's a superposition over, over this value and that value, 94 00:12:10,042 --> 00:12:19,053 right? We'd get an equal superposition over this value of x and that value of x. 95 00:12:19,053 --> 00:12:27,043 Meaning, it's an equal superposition of zero, one, one and zero, one, one plus s. 96 00:12:27,043 --> 00:12:38,048 Okay. So, so that's the main principle. So what, what we, what we see is, when we, 97 00:12:38,048 --> 00:12:46,026 when we do a measurement here, we'll end up seeing a superposition, we'll pick out 98 00:12:46,026 --> 00:12:52,086 a random value x as well as x plus s because, because for both of those values, 99 00:12:52,086 --> 00:13:03,068 x and x plus s, we'll see the same value of f of x, okay? So, when we measure with 100 00:13:03,068 --> 00:13:15,056 c, f of some value r, some random number x, r and then the first register. I t's 101 00:13:15,056 --> 00:13:24,039 state looks like one over square root two r plus one over square root two r plus s, 102 00:13:24,039 --> 00:13:32,032 r ight? This is what we wanted. Okay. So now, now that we have this state, one over 103 00:13:32,032 --> 00:13:37,075 square root two r plus one over square root two r plus s, we are going to do four 104 00:13:37,075 --> 00:13:43,002 year sampling on it and we want to understand what the output looks like. So, 105 00:13:43,002 --> 00:13:51,006 let's say that this output state before we sampled it, before we've measured it is 106 00:13:51,006 --> 00:14:06,004 sum over all y of beta sub y, y. So what's beta sub y? Okay. So, with what amplitude 107 00:14:06,004 --> 00:14:16,003 do you go from r to y? Remember you go from r to y with amplitude minus one to 108 00:14:16,003 --> 00:14:24,088 the r dot y over two to the n over two. Okay. But, but you already started with 109 00:14:24,088 --> 00:14:32,050 amplitude one over square root two, so it's going to be two to the one over 110 00:14:32,050 --> 00:14:42,004 square root two times two to the n over two which is two to the n plus one over 111 00:14:42,004 --> 00:14:49,082 two. And then, with what amplitude do you go from r plus s to this? It's 2y. It's 112 00:14:49,082 --> 00:14:59,054 minus one to the r plus s dot y divided by two to the n plus one over two. Okay. You 113 00:14:59,054 --> 00:15:09,019 can further factor this out to minus one to the r dot y divided by two to the n 114 00:15:09,019 --> 00:15:21,066 plus one over two times one plus minus one to the s dot y. Now you have two cases, 115 00:15:21,066 --> 00:15:35,066 case one s dot y is combined to, is equal to one. Mark two in which case, in which 116 00:15:35,066 --> 00:15:48,099 case beta sub y equal to zero. Case two, s dot y is common to zero mark two in which 117 00:15:48,099 --> 00:16:02,033 case, beta sub y is, is what? Well, it's minus one to the r dot y, s dot by zero so 118 00:16:02,033 --> 00:16:11,037 this is times two. So, it's times two divided by two to the n plus one over two. 119 00:16:11,037 --> 00:16:19,063 So it's, two to the n minus one over two. So when you sample, you see each such y 120 00:16:19,063 --> 00:16:32,065 with amplitude square of this, so beta sub y squared which is a probability of c and 121 00:16:32,065 --> 00:16:43,068 y is just one over two to the n minus one. So, what's this telling us? So, exactly 122 00:16:43,068 --> 00:16:49,058 half the y's have, have the property that y dot s is combined to zero mark two. So 123 00:16:49,058 --> 00:16:54,083 two, out of the two to the n possible ambit strings, half them have this 124 00:16:54,083 --> 00:17:01,056 property and they are sampling each one with equal probability exactly one over 125 00:17:01,056 --> 00:17:10,012 two to the minus one. Okay. So, so the net effectors, after the foray sampling we ha 126 00:17:10,012 --> 00:17:19,075 ve a random linear equation on s. So now, we want to reconstruct s. So, how do we 127 00:17:19,075 --> 00:17:28,069 recons truct S? So we have, we have a random linear equation y dot s is zero 128 00:17:28,069 --> 00:17:37,083 mark two, so this is y1, s1 plus yn, sn is zero mark two. We're working, it's, it's 129 00:17:37,083 --> 00:17:46,093 zero if you're working, working over the field of two elements. And so we can write 130 00:17:46,093 --> 00:17:53,043 down n minus one such linear equations and we want to know what's the chance that 131 00:17:53,043 --> 00:18:00,034 they're not, none of these equations are dependent on previous ones? Well, what's 132 00:18:00,034 --> 00:18:07,026 the, what's the chance that the first such equation is nontrivial? Well, the, the 133 00:18:07,026 --> 00:18:13,090 only way it could be trivial is if y happens to be zero. So the chance that the 134 00:18:13,090 --> 00:18:20,029 first equation is, is bad is one over two to the n. What about the second equation? 135 00:18:20,029 --> 00:18:27,087 What's the chance that the second equation is bad given that the first one is not? 136 00:18:27,087 --> 00:18:35,031 Well the, the, the only, only way it can be bad is if it was the all zero string or 137 00:18:35,031 --> 00:18:42,034 if it was equal to exactly, equal to y, you know, equal to y, the first string. 138 00:18:42,034 --> 00:18:49,086 Right? So, so let's, let's call the, you know, so let's say we sample y sub one, y 139 00:18:49,086 --> 00:18:57,049 sub two through y sub n minus one. These are n, n minus one linear equations. The 140 00:18:57,049 --> 00:19:04,084 chance that the second one is bad is if, if the second one happens to be the all 141 00:19:04,084 --> 00:19:10,058 zero string, or y1. There are two ways that could be so it's one over two to the, 142 00:19:10,058 --> 00:19:16,024 two over two to the n which is one over two to n minus one. What about the third 143 00:19:16,024 --> 00:19:22,042 one? The third one is bad if, if it's, it's a linear combination of the first 144 00:19:22,042 --> 00:19:28,023 two. If it's either, either the zero string, or if it's y1 or y2, or y1 plus 145 00:19:28,023 --> 00:19:35,080 y2. So there are four ways it could be bad so the chance is one over two to the n 146 00:19:35,080 --> 00:19:43,039 minus two and so on, okay? So how many terms are there? There are n minus one 147 00:19:43,039 --> 00:19:49,077 terms. So, all the way up to one quarter. We sum up this geometric series, it's, 148 00:19:49,077 --> 00:19:57,008 this is the chance of being of, of, of dependency. This is a probability that we 149 00:19:57,008 --> 00:20:06,005 could dependent linear equations is utmost a half therefore, we have full rank. They 150 00:20:06,005 --> 00:20:15,013 are all independent with probability greater than or equal to a half. Okay. So 151 00:20:15,013 --> 00:20:23,075 half th e time this algorithm is going to work. If it doesn't, we can rerun the 152 00:20:23,075 --> 00:20:32,005 algorithm. So, so what we're going to do is, is you know, run the algorithm n minus 153 00:20:32,005 --> 00:20:39,045 one times create these n minus one linear equations. Solve them, get a value for s, 154 00:20:39,045 --> 00:20:47,026 check whether s looks good. So, how do you check? What you do is, you compute f of x 155 00:20:47,026 --> 00:20:53,042 and f of x plus s for some random value of x, and check if they're equal. If they 156 00:20:53,042 --> 00:20:58,063 are, then you know you found the correct you know, you know, try this a few times 157 00:20:58,063 --> 00:21:03,055 and if you, if you, if you always find equality then you know, that you found the 158 00:21:03,055 --> 00:21:08,066 right value of s with very high probability and you can stop. Okay. So, so 159 00:21:08,066 --> 00:21:15,082 putting it altogether, this is what Simon's algorithm looks like. You start 160 00:21:15,082 --> 00:21:23,000 off with your inputs, input qubits in the state zero. You do a Hadamard transform. 161 00:21:23,000 --> 00:21:30,053 You compute f, do a Hadamard transform and measure, and that's it. This, this, this, 162 00:21:30,081 --> 00:21:38,076 this measurement gives the linear equation on the s that s must satisfy. Repeat this 163 00:21:38,076 --> 00:21:46,019 process n minus one times, collect n minus one linear equations. Solve them and you 164 00:21:46,019 --> 00:21:50,000 find your secret string s.