1 00:00:00,000 --> 00:00:06,026 Okay. So, to see how powerful this, this Hadamard Transform can be, let's look at 2 00:00:06,026 --> 00:00:12,008 the following simple problem, which is a parity problem. So, we're given some 3 00:00:12,008 --> 00:00:19,004 function f from n bits to one bit, and it's given to us as a black box. So, we're 4 00:00:19,004 --> 00:00:26,000 given a program that will compute this function for us but we cannot look inside 5 00:00:26,000 --> 00:00:33,070 the program to see how it's doing so. All we can do is run this program on any given 6 00:00:33,070 --> 00:00:41,006 input. So, program or a black box containing a circuit for computing this 7 00:00:41,006 --> 00:00:49,004 function f. Now, we're also told that this, this, this function f has some, has 8 00:00:49,004 --> 00:00:56,009 a very special property. It's, all it is, is a parity of some subset of the, of the 9 00:00:56,009 --> 00:01:04,094 bits. So it's of the form U.x for some hidden U which is an n bit string. So, for 10 00:01:04,094 --> 00:01:14,069 example, n might be equal to three, U equal to one, zero, one, in which case, 11 00:01:14,069 --> 00:01:24,049 what this function does is on input x1, x2, x3. So, x is a three, three bit 12 00:01:24,049 --> 00:01:37,025 string, f(x) is just x1 exclusive all x3. All right, it's x1 + x3 mark two. Okay. 13 00:01:38,007 --> 00:01:52,049 What, what, what we mean by U.x it's U.x mod two. So, this now this is fun, this is 14 00:01:52,049 --> 00:02:01,003 the circuit that we have it takes input x it outputs f(x) and we want to try to use 15 00:02:01,003 --> 00:02:11,010 this box to try to figure out what, what this parity mask U looks like. So, 16 00:02:11,010 --> 00:02:20,071 classically this is, you know, this is sort of easy to figure out. What you would 17 00:02:20,071 --> 00:02:28,068 do is, you'd give as input so you might first input one zero, zero, zero. What's 18 00:02:28,068 --> 00:02:35,086 the output? Well, it's just U1. And then you could output zero one zero, zero, 19 00:02:35,086 --> 00:02:44,004 zero, zero and the output would be U2. And so in, in such steps, you can figure out 20 00:02:44,004 --> 00:02:52,058 U, which is U1 through U sub n. Can you do any better? Well, clearly not. Because 21 00:02:52,058 --> 00:03:01,006 each time you run the circuit, you get only one bit of information. So, you can 22 00:03:01,006 --> 00:03:08,066 conclude you need at least n steps. Because you need to reconstruct n bits of 23 00:03:08,066 --> 00:03:17,054 information. So, that's a classical situation. What about in the quantum 24 00:03:17,054 --> 00:03:24,051 world? Okay, in the quantum world, remember, what we do is take the circuit, 25 00:03:24,051 --> 00:03:30,073 and make a quantum circuit out of it. So now, it takes as input x and also an input 26 00:03:30,073 --> 00:03:37,068 b, which is the answer bit. And what th e quantum circ uit does, is it outputs x and 27 00:03:37,068 --> 00:03:44,034 bx, or f(x). So, the output, the answer that gets toggled, if and only if f(x) = 28 00:03:44,034 --> 00:03:51,059 one. I'm suppressing the work, work bits, because, you know, they are, they start at 29 00:03:51,059 --> 00:03:58,027 zero and end at zero. Now, of course, quantumly, we can also input. We, we can 30 00:03:58,027 --> 00:04:06,037 put x in superposition, so our input could be sum over x of alpha x. Get x.and the 31 00:04:06,037 --> 00:04:15,005 output is now going to be sum over x alpha x ket x, but the, but then we have the 32 00:04:15,005 --> 00:04:22,003 answer in superposition f(x), as well. Okay. So, so, can we do, can we 33 00:04:22,003 --> 00:04:29,008 reconstruct U using fewer queries to f(x)? So, we needed n such queries in the 34 00:04:29,008 --> 00:04:36,007 classical case, can we do it in fewer queries? And it turns out, the answer is 35 00:04:36,007 --> 00:04:42,053 yes. There's a, there's a, there's an algorithm that, that does this using as 36 00:04:42,053 --> 00:04:49,095 few as one query to, to, do this do this circuit for computing, for computing f in 37 00:04:49,095 --> 00:04:56,018 the quantum case. And so, the, the, the strange part here, the, the 38 00:04:56,018 --> 00:05:04,064 counter-intuitive part here is that even though the circuit is outputting one bit 39 00:05:04,064 --> 00:05:11,030 on one bit of information we seem to be getting n bits out of it. Okay. So, how 40 00:05:11,030 --> 00:05:17,045 does this, how does this algorithm work? So, it works by first setting up a, a 41 00:05:17,045 --> 00:05:24,010 particular kind of superposition, which is a superposition of all n bit strings x of 42 00:05:24,010 --> 00:05:30,084 x with this, with this phase -one, with the phase of -one if and only if f(x) = 43 00:05:30,084 --> 00:05:38,075 one. Okay, so, this is, this we call the phase state. And now, what you do is you 44 00:05:38,075 --> 00:05:45,055 do for a sampling and you obtain U. So, let me first explain why this second step 45 00:05:45,055 --> 00:05:53,006 works. You see, because, because f(x) is just U.x so this superposition is just one 46 00:05:53,006 --> 00:06:01,066 / two^n/2, sum over all x - one^u.x x. Now remember, what is, what is this state? 47 00:06:01,066 --> 00:06:09,089 Well, this state is exactly what you get if you do the Hadamard transform on input 48 00:06:09,089 --> 00:06:19,063 U. So, if that's, if that's your input, then this is what your output is. Okay. 49 00:06:19,063 --> 00:06:26,025 So, so, what we want to do is we want to run this circuit backwards. We want to run 50 00:06:26,025 --> 00:06:32,083 the Hadamard circuit backwards. Because we want this as input, and we want that as 51 00:06:32,083 --> 00:06:38,033 output. So, how do we do that? Well, remember, the Hadamard transfor m is its 52 00:06:38,033 --> 00:06:44,088 own inverse. So, all we have to do is, is we have to put this, this input through 53 00:06:44,088 --> 00:06:51,020 the Hadamard transform again. We'll get this as output, and then we just measure. 54 00:06:51,020 --> 00:06:57,079 And we'll, we'll obtain, obtain the, this hidden view that we were looking for. So 55 00:06:57,079 --> 00:07:03,044 the, the only thing we have to do now is to figure out how to set up this 56 00:07:03,044 --> 00:07:09,051 superposition. Okay. So, so, how do we set up this superposition? Well, this is, this 57 00:07:09,051 --> 00:07:16,026 is actually not that difficult to do. So, what do we do? Well, we star with n bits 58 00:07:16,026 --> 00:07:23,095 in the zero state, we perform a Hadamard transform on them. So, so now, if you 59 00:07:23,095 --> 00:07:32,003 start with zero^n, we perform the Hadamard transform. What do we get? We get sum over 60 00:07:32,003 --> 00:07:43,059 all n bit strings x of x with amplitude one / two^n/2. Now, what we do is, we set 61 00:07:43,059 --> 00:07:55,013 up the answer bit in the state minus. Okay. So, so, the answer bit b, is in the 62 00:07:55,013 --> 00:08:06,076 state minus, which is one / square root 2,0 - one /square root 2,1. Now, if the 63 00:08:06,076 --> 00:08:15,079 answer, okay. So, what, what happens if f(x) = zero? Remember, the answer bit 64 00:08:15,079 --> 00:08:23,007 becomes b, x or f(x) so, so what's b exclusive or f(x) in this case? Well, it 65 00:08:23,007 --> 00:08:30,025 just stays minus, right, because, because when you x or zero into something, it does 66 00:08:30,025 --> 00:08:38,047 nothing. So, it just stays one /square root of zero minus one / square root of 67 00:08:38,047 --> 00:08:48,084 one. What happens if f(x) = one? Then b, x, or f(x) is just, well, you toggle it, 68 00:08:48,084 --> 00:08:58,024 right? So, you get one / square root 2,1 minus one /square root 2,0 which is just, 69 00:08:58,024 --> 00:09:06,006 you pick up a phase of -one. So, that's what we're doing. We, we set up the answer 70 00:09:06,006 --> 00:09:13,047 beta as a minus, and then, we are running the circuit for computing f. So, remember 71 00:09:13,047 --> 00:09:20,046 the input to the circuit is a superposition over all x, and what happens 72 00:09:20,046 --> 00:09:28,028 when we, when we compute, compute f(x) with the output bit? The answer bit set 73 00:09:28,028 --> 00:09:35,041 as, as minus? Well, whenever the, whenever, for those x such that f(x) = 74 00:09:35,041 --> 00:09:43,028 zero, the phase doesn't change. And for those x such that f(x) = one, the phase , 75 00:09:43,028 --> 00:09:50,089 changes to -one. Okay, so, so what's another way of saying it? So, at this 76 00:09:50,089 --> 00:10:03,032 point, our superposition was sum over all x, one / two^n/2 plus, sorry, x. And our, 77 00:10:03,032 --> 00:10:19,029 answer bit was set as m inus. And now, when we compute use of f, wll go to sum 78 00:10:19,029 --> 00:10:29,075 over all x, one / two^n/2 And then, we get, we still get x. We still get minus. 79 00:10:29,075 --> 00:10:42,004 Except that whenever f(x) = one, we pick up a phase of -one. So, we get -one^f(x), 80 00:10:42,004 --> 00:10:49,037 okay? But this is always minus, so this is always a tensor product state. And so, if 81 00:10:49,037 --> 00:10:55,035 you look at these qubits, the first n qubits, we've got the desired phase state, 82 00:10:55,035 --> 00:11:01,027 which is that. And now, if we do another Hadamard transform we end up with our, 83 00:11:01,027 --> 00:11:08,000 with, with, with U. Okay, so this gives us this is really the, the algorithm. We, we, 84 00:11:08,000 --> 00:11:15,016 we set up n qubits, the zero state, answer qubit in the minus state, we perform 85 00:11:15,016 --> 00:11:21,034 Hadamard transform, perform U and now, we give, set up the phase state, we do 86 00:11:21,034 --> 00:11:28,030 Hadamard transform on the first n qubits and we will recover U, so we mention. 87 00:11:28,030 --> 00:11:33,086 Okay, so, this, this algorithm was, was really the, the base case of a recursive 88 00:11:33,086 --> 00:11:38,062 algorithm. You know, this recursive algorithm is called Recursive Fourier 89 00:11:38,062 --> 00:11:44,016 Sampling. I'll just give you a very short sketch of it not really enough to explain 90 00:11:44,016 --> 00:11:49,027 it to you, but just a little, you know, the basic idea. So, in this recursive 91 00:11:49,027 --> 00:11:54,061 version, we solve a recursive version of this, this same parity problem. And now, 92 00:11:54,061 --> 00:12:01,014 we are trying to amplify this difference between classical and quantum. In the 93 00:12:01,014 --> 00:12:06,065 classical case, you needed n queries. In the quantum case, you needed only a 94 00:12:06,065 --> 00:12:12,044 constant number of queries. And so, so what you do is, in the recursive version 95 00:12:12,044 --> 00:12:18,054 of the of the, of the, of the, of the, of the problem, classical algorithms satisfy 96 00:12:18,054 --> 00:12:24,071 the recursion that time to solve a problem of size n is at least n times the time to 97 00:12:24,071 --> 00:12:31,010 solve a problem of size n/2 + order n, where this n, is the number of queries 98 00:12:31,010 --> 00:12:39,007 required to solve the parity problem. If you solve this recursion, you get t(n) is, 99 00:12:39,007 --> 00:12:50,009 grows at least like n^log n. So this is, superpolomial. If you work through the 100 00:12:50,009 --> 00:12:56,000 quantum algorithm for this, for the, for the recursive problem, it satisfies the 101 00:12:56,000 --> 00:13:02,049 recursion t(n) = two t(n) / two + order n whose solution is t(n) = n log n This is 102 00:13:02,049 --> 00:13:09,074 like the recursion for the, for mergesort, and so you get a polynomial time quantum 103 00:13:09,074 --> 00:13:16,056 algorithm. And so, this gives y ou already a glimpse of this power of Fourier 104 00:13:16,056 --> 00:13:23,029 sampling. That it gives you a super polynomial speed up for a certain kind of 105 00:13:23,029 --> 00:13:31,037 problem. Okay. So, in the next video, we will see, how to use, sampling in, in an 106 00:13:31,037 --> 00:13:34,002 even more dramatic way.