1 00:00:00,000 --> 00:00:06,001 Okay so we are finally ready to start talking about quantum algorithms. And in 2 00:00:06,001 --> 00:00:12,007 this lecture I'll talk about some of the building blocks that go into making up 3 00:00:12,007 --> 00:00:18,008 quantum algorithms and how they were used in some early quantum algorithms to 4 00:00:18,008 --> 00:00:24,009 demonstrate the power of quantum computing. Okay so, so let's see. Last 5 00:00:24,009 --> 00:00:30,004 time we already talked about reversible computation, classical reversible 6 00:00:30,004 --> 00:00:36,004 computation, where we said suppose you have a classical circuit, that on input x 7 00:00:36,004 --> 00:00:42,028 computes C(x). And for now I'm, I'm just going to talk about the case where C(x) is 8 00:00:42,028 --> 00:00:47,069 a, is boolean. So it's, it's just a single bit, just for simplicity. So then we said 9 00:00:47,069 --> 00:00:53,074 that there's a, there's a classical reversible circuit. Which takes as input x 10 00:00:53,074 --> 00:01:00,065 and answer bit B. As well as a number of work bits, which are all initialized to 11 00:01:00,065 --> 00:01:08,021 zero. And then, what this reversible circuit does is, it spits out x unchanged. 12 00:01:08,021 --> 00:01:15,034 It also leaves the work bits in a clean state. So they are, they are also in the 13 00:01:15,034 --> 00:01:21,074 zero state. And it, it, it XORs the answer C(x) into this, into this answer bit B. So 14 00:01:21,074 --> 00:01:28,009 the output bit becomes b XOR C(x). So it toggles the bit b. So in the case that b0 15 00:01:28,009 --> 00:01:35,000 is zero, then this answer bit is exactly C(x). Now, the other thing we said is 16 00:01:35,000 --> 00:01:40,008 that, if we start with such a, such a reversible circuit, we can, we can also 17 00:01:40,008 --> 00:01:47,020 implement it using quantum gates. And so we get this unitary transformation U sub C 18 00:01:47,020 --> 00:01:54,003 which in the case that the input bits happen to be, happen to be classical in, 19 00:01:54,003 --> 00:02:01,009 in this basis states Then the behavior is exactly the same as we had before. Except, 20 00:02:01,009 --> 00:02:09,007 of course, now since U is a, is a unitary, it's a, it's a quantum circuit. So it can 21 00:02:09,007 --> 00:02:17,056 take as input of superposition inputs. So for example, if we give it as input, the 22 00:02:17,056 --> 00:02:26,083 superposition sum of all x of alpha XX. And then bs, well let's, let's, let's just 23 00:02:26,083 --> 00:02:36,004 say the input bit is always b. And I'll suppress these, you know, the work bits. 24 00:02:36,004 --> 00:02:47,092 Then the output, is sum over all x. Now fax, same amplitude. Input string is the 25 00:02:47,092 --> 00:02:56,099 same, and the output string is b XOR C(x). So you can compute and superposition this 26 00:02:56,099 --> 00:03:01,060 way. Now, this is one of the basic primitives for quantum computation. The 27 00:03:01,060 --> 00:03:07,018 fact that we can compute. Anything that we can compute classically we can compute in 28 00:03:07,018 --> 00:03:12,046 superposition. But this is not yet enough. We need one more ingredient and the 29 00:03:12,046 --> 00:03:18,071 crucial ingredient turns out to be the Hadamard transform. So remember what the 30 00:03:18,071 --> 00:03:25,013 Hadamard transform is? It's a, it's a transform on a single qubit which maps 31 00:03:25,013 --> 00:03:29,055 zero to plus and one to minus. And the plus of course, is one / square root 32 00:03:29,055 --> 00:03:37,015 two(0) + one / square root two(1). And minus is one / square root two(0) - one / 33 00:03:37,015 --> 00:03:44,013 square root two(1). That's how, that's, that's the Hadamard transform. That's our 34 00:03:44,013 --> 00:03:51,050 transformation. But, but now we can also perform this Hadamard transform on two 35 00:03:51,050 --> 00:03:58,066 qubits. Now remember what the so, so now what happens if you perform it on two 36 00:03:58,066 --> 00:04:06,068 qubits? Well, of course what we'd have is 00 would get mapped to (++) which turns 37 00:04:06,068 --> 00:04:17,017 out to be one, well it's, what is it? It's one / square root two(0) + one / square 38 00:04:17,017 --> 00:04:27,036 root two(1) tensor with one / square root two(0) + one / square root two(1) which is 39 00:04:27,036 --> 00:04:36,072 just one-half(00) + one-half(01) + one-half(10) + one-half(11). So what it 40 00:04:36,072 --> 00:04:43,000 does is it takes (00) as input, and outputs an equal superposition over all 41 00:04:43,000 --> 00:04:49,004 the four inputs. And now, you can work this out for all the other input strings. 42 00:04:49,004 --> 00:04:56,005 Or the, the rest of the three. Let's just work it out for (eleven). So what does it 43 00:04:56,005 --> 00:05:02,050 do? It outputs (--) which is one / square root two(0) - one / square root two(1) 44 00:05:02,050 --> 00:05:15,071 tensor with one / square root two(0) - one / square root two(1). And what's that? 45 00:05:15,071 --> 00:05:28,004 Well, that's a one-half(00) - one-half(01) + one-half (ten) sorry - one-half(10) + 46 00:05:28,004 --> 00:05:36,057 one-half(11). So to understand this, this sign pattern. So, so basically, you know, 47 00:05:36,057 --> 00:05:43,056 you, you should, you should check that all the four classical strings get mapped to a 48 00:05:43,056 --> 00:05:50,042 superposition of 0s you know (00), (01), (ten), and (eleven) with amplitudes. All 49 00:05:50,042 --> 00:05:56,050 the amplitude of + or - are one-half so the only, the, the only differences what 50 00:05:56,050 --> 00:06:03,036 the sign pattern is. And to understand the sign pattern you have to realize that each 51 00:06:03,036 --> 00:06:08,058 of the, these Hadamards maps one when, when you, when you start with one and end 52 00:06:08,058 --> 00:06:14,005 up with one, you get a, you get a negative sign. So, so, so this sign pattern ends up 53 00:06:14,005 --> 00:06:19,018 being the parity of how many one to one transitions there are. Now if you want to, 54 00:06:19,018 --> 00:06:24,080 if you want to write out this, the, the unitary transformation, you take the 55 00:06:24,080 --> 00:06:32,014 tensor product of this two by two matrix with itself and if you remember the rules 56 00:06:32,014 --> 00:06:40,094 for doing that, you would just fill in one / square root two this matrix in the, in 57 00:06:40,094 --> 00:06:47,001 the upper left. So you get one-half, one-half, one-half - one-half. And the 58 00:06:47,001 --> 00:06:53,002 same thing here you get one-half, one-half, one-half - one-half. Same thing 59 00:06:53,002 --> 00:06:58,008 here. One-half, one-half, one-half - one-half. And then for this, this thing, 60 00:06:58,008 --> 00:07:04,079 what you're doing is you're, you know since this entry is - one / square root 61 00:07:04,079 --> 00:07:11,071 two you'd be multiplying this matrix by -one / square root two so you'd get 62 00:07:11,071 --> 00:07:19,011 halves, but you'll also change signs. You'd get - one-half - one-half - one-half 63 00:07:19,011 --> 00:07:24,010 and one-half. Okay, so that's, that's your Hadamard transform on two qubits. 64 00:07:24,010 --> 00:07:31,010 Similarly you could do a Hadamard transform on three qubits. And you'll get 65 00:07:31,010 --> 00:07:40,004 an eight by eight matrix. And you'd be mapping, for example 000 to an equal 66 00:07:40,004 --> 00:07:49,071 superposition. So one / twice square root two(000) so on up to (111). So there would 67 00:07:49,071 --> 00:07:56,048 be eight such possibilities. And again, you'd get a different sign pattern 68 00:07:56,048 --> 00:08:03,094 depending upon what, what string you started from. So make sure you work 69 00:08:03,094 --> 00:08:11,056 through this to understand that, you know what this pattern looks like. Okay, so one 70 00:08:11,056 --> 00:08:18,008 thing you, you realize as you, as you, do this is what the Hadamard transform does 71 00:08:18,008 --> 00:08:24,006 is it, it starts with a classical string on the, on the left, you know one of the 72 00:08:24,006 --> 00:08:29,013 basis strings. And it gives you a superposition over all the two^N N bit 73 00:08:29,013 --> 00:08:36,036 strings. So this is a very powerful thing and it's a very important thing in quantum 74 00:08:36,036 --> 00:08:42,025 algorithms. Very important principle. So now let's try to understand what happens 75 00:08:42,025 --> 00:08:47,092 when we let, work with N qubits, as N tends to infinity. So what, what, what 76 00:08:47,092 --> 00:08:53,036 happens? Well, so, so now we have, we have N qubits. Let's say they were all 77 00:08:53,036 --> 00:08:59,006 initialized to, you know we start with, with each of them in the zero state, and 78 00:08:59,006 --> 00:09:04,063 they put them through the Hadamard circuit, where each of them is going 79 00:09:04,063 --> 00:09:11,001 through a Hadamard gate. What's the output? Well, the output is clearly the + 80 00:09:11,001 --> 00:09:23,046 state on all the qubits which is equ al to what? Well I claim that it's just going to 81 00:09:23,046 --> 00:09:33,052 be the sum over all N with strings. So remember this is how we denote the N bit 82 00:09:33,052 --> 00:09:39,094 strings. Where each such x has equal amplitude, and the amplitude is two^N/2 83 00:09:39,094 --> 00:09:47,083 right? Because we'll get one / square root two, how did we get this? Well this is one 84 00:09:47,083 --> 00:09:58,025 / square root two(0) + one / square root two(1) tensor with itself n times. 85 00:09:58,025 --> 00:10:13,064 Alright. So it's a tensor product with itself, N times. So, another way we 86 00:10:13,064 --> 00:10:21,048 denotes this is by just saying, one / square root two(0) + one / square root 87 00:10:21,048 --> 00:10:30,062 two(1). And then in the exponent we just put, put down, this notation tensor with 88 00:10:30,062 --> 00:10:36,077 itself N times. And now if you, if you multiply these out, what do you get? Well, 89 00:10:36,077 --> 00:10:42,026 you get, you know, depending upon which, you know, which, which choice you take 90 00:10:42,026 --> 00:10:48,079 from each, from each of these, each of these terms, you get, you get sum N bit 91 00:10:48,079 --> 00:10:54,005 string. And what's its amplitude? Well, you get one / square root two one / square 92 00:10:54,005 --> 00:11:03,069 root two N times which is one / two^N / two. Okay, but now let's try to understand 93 00:11:03,069 --> 00:11:13,072 what happens if you, if you start with some U = U1 U2 through U sub N. So let's 94 00:11:13,072 --> 00:11:21,061 say those are the N bits of U. So what happens when you perform the Hadamard 95 00:11:21,061 --> 00:11:29,029 transform on this? So, let's, let's, let's say what's our notation for this? It's H 96 00:11:29,029 --> 00:11:42,016 tensor with itself N times applied to U which, so now what do we get? Well, I 97 00:11:42,016 --> 00:11:56,017 claim that what we get is still the sum over all x of length N(x). But now, in 98 00:11:56,017 --> 00:12:09,050 front of each of these Xs we have, its amplitude is, is one / two^N / two but 99 00:12:09,050 --> 00:12:23,020 with either + or - sign. So, when do you get a + sign and when do you get the - 100 00:12:23,020 --> 00:12:37,005 sign well, you get - one to the U.x where U.x is U1 X1 + ... + Un Xn. Okay? So, 101 00:12:37,005 --> 00:12:46,046 remember what, what we, what we already discussed before. The, the only time you 102 00:12:46,046 --> 00:12:55,036 get a -one sign is when you input bit. So these are input bits now. They are U one, 103 00:12:55,036 --> 00:13:08,087 U2, so on up to U sub N. And output bits are now X1, X2 and so on up to X sub N. 104 00:13:08,087 --> 00:13:16,008 Okay. So when do you get a, when do you get a - sign? Well, only when the input 105 00:13:16,008 --> 00:13:23,055 bit is equal to the output bit equal to one, right? So U.x is counting how many, 106 00:13:23,055 --> 00:13:30,012 how many such - signs you get? And the n when you take - one to this bar, it tells 107 00:13:30,012 --> 00:13:36,065 you whether you get an odd number or an even number of - signs. And so your 108 00:13:36,065 --> 00:13:48,006 overall phase is negative if and only if you get an odd number of - signs, right? 109 00:13:48,006 --> 00:14:08,007 So, for example if N = three. U = (111). X = (101) then what's, you know what, what 110 00:14:08,007 --> 00:14:13,086 would you get? Well, you'd get U.x is = to one, one plus one zero + one, one which is 111 00:14:13,086 --> 00:00:00,000 two. And so, -one^U.x divided by two^N / two would be -one^2 / two^3 / two which is 112 00:00:00,000 --> 00:00:00,000 one / two^3 / two. So that would be the amplitude of x which is this. If you start 113 00:00:00,000 --> 00:00:00,000 with, with the input being (111). Okay. So now here's the new primitive that we have. 114 00:00:00,000 --> 00:00:00,000 The new primitive that we have is that we can start with any old superposition psi 115 00:00:00,000 --> 00:00:00,000 that we want, so we setup some superposition on N qubit psi. Then we 116 00:00:00,000 --> 00:00:00,000 apply the Hadamard transform. So we get as output some new superposition. So psi 117 00:00:00,000 --> 00:00:00,000 might be the superposition sum / x, alpha XX. Psi hat is some new superposition sum 118 00:00:00,000 --> 00:00:00,000 / x beta sub XX. Okay. So this is sum / X beta sub XX. And now what you do is now 119 00:00:00,000 --> 00:00:00,000 you perform a measurement and you measure. And so you see sum Y, so the output of 120 00:00:00,000 --> 00:00:00,000 this is sum Y with probability beta sub Y magnitude squared. Okay, so this is our 121 00:00:00,000 --> 00:00:00,000 basic, primitive in quantum computation. We call this fourier sampling because 122 00:00:00,000 --> 00:00:00,000 well, we'll see this later what, what we call it fourier sampling because the 123 00:00:00,000 --> 00:00:00,000 Hadamard transform is really the fourier transform over the group Z sub two of 124 00:00:00,000 --> 00:00:00,000 addition twelve. Okay? But that's not the important part, it's, that's just name. 125 00:00:00,000 --> 00:00:00,000 The important part is we have this primitive, which is set up any 126 00:00:00,000 --> 00:00:00,000 superposition psi, so create some superposition psi. Now perform the fourier 127 00:00:00,000 --> 00:00:00,000 transform or the Hadamard transform on these N qubits and then measure. What you 128 00:00:00,000 --> 00:00:00,000 have sampled from, is this probab ility distribution. And this is called sampling. 129 00:00:00,000 --> 00:00:00,000 What we want say is that this is a very powerful, primitive. Because, without 130 00:00:00,000 --> 00:00:00,000 access to quantum, you know a quantum circuit which is doing exponential work in 131 00:00:00,000 --> 00:00:00,000 figuring out. How these amplitudes alpha X interfere to give you the betas? You would 132 00:00:00,000 --> 00:00:00,000 have a, a very hard time to tryin g sample from the same distribution classically. 133 00:00:00,000 --> 00:00:00,000 Okay so, but how do we make sense of this? How, how do we find, you know what does 134 00:00:00,000 --> 00:00:00,000 this really, this primitive really help us do?