1 00:00:00,000 --> 00:00:05,087 Okay. So, in this video, we'll talk about one other aspect of quantum circuits which 2 00:00:05,087 --> 00:00:12,067 is their reversibility. And this is it, it turns out to be something that's, that's 3 00:00:12,067 --> 00:00:19,003 eventually simple to deal with but its something that we have to tackle. So, 4 00:00:20,000 --> 00:00:25,077 quantum computers are always reversible. So, what do we mean by that? So, let's 5 00:00:25,077 --> 00:00:32,060 say, you have a quantum circuit U, it takes as input the state x. So, the output 6 00:00:32,060 --> 00:00:39,054 is U, U (x). Now, it claim that there is some quantum circuit which, which undoes 7 00:00:39,054 --> 00:00:46,008 this and, you know, on input U (x), it'll output x. So, what, what does this quantum 8 00:00:46,008 --> 00:00:53,024 circuit look like? It's just U dagger. Right, U is unitary and so we know that U 9 00:00:53,024 --> 00:01:00,066 times U dagger = U dagger times U is identity. In fact, there's something even 10 00:01:00,066 --> 00:01:10,004 more that's true which is, which is that if you, if you look at the gates inside of 11 00:01:10,004 --> 00:01:19,021 you, you can just take these gates and the U dagger, you just, you just create the 12 00:01:19,021 --> 00:01:29,067 corresponding gates, G dagger and G' dagger and so on, in the opposite order. 13 00:01:29,067 --> 00:01:36,020 And so, what happens is when you, when you put these two, these two circuits 14 00:01:36,020 --> 00:01:43,047 together, then this, this gate annihilates that one and the next gate here will then 15 00:01:43,047 --> 00:01:48,018 annihilate that, that one and so on because each one is the, is, is a 16 00:01:48,018 --> 00:01:54,004 conjugate transpose of the corresponding one. And so, these two circuits completely 17 00:01:54,004 --> 00:01:59,009 annihilate each other and, and so what you, what you have is the identity map 18 00:01:59,009 --> 00:02:06,000 which just maps x to itself. Okay. So, so, that's what we mean by saying that quantum 19 00:02:06,000 --> 00:02:11,006 computers are reversible, meaning that whatever you compute, you can also 20 00:02:11,006 --> 00:02:16,064 uncompute if you like, by just doing the opposite of what you did, did to get 21 00:02:16,064 --> 00:02:23,016 there. Okay. So now, let's see what this means, if we are, if we are just trying to 22 00:02:23,016 --> 00:02:28,087 implement a classical circuit. So, for example, a classical circuit might be, 23 00:02:28,087 --> 00:02:34,075 might be doing something like it might take its input, m bits and output one bit 24 00:02:34,075 --> 00:02:41,038 and its computing some function f, the Boolean function f on input x. So now, how 25 00:02:41,038 --> 00:02:47,044 would we, how would we actually compute this quantumly? Well, we, we have some 26 00:02:47,044 --> 00:02:53,057 quantum circ uit for computing f, which on input x. So, there's ny's coming in and we 27 00:02:53,057 --> 00:02:59,075 want one of the y's on the output to contain f (x), and of course, you remember 28 00:02:59,075 --> 00:03:06,026 in the quantum circuit, if there's n inputs, there's always n output. And so, 29 00:03:06,026 --> 00:03:13,078 from the reversibility property, it must be the case that, we then should be able 30 00:03:13,078 --> 00:03:21,004 to compute. We, we should be able to uncompute this function and recover x from 31 00:03:21,004 --> 00:03:29,058 this output. But is it always possible to recover that the input from that? Well, 32 00:03:29,058 --> 00:03:38,003 think about an AND gate, right. So, if you have an AND gate, it takes as input two 33 00:03:38,003 --> 00:03:45,076 bits, a and b. And it outputs a, the bits a and b which is, which is one, if and 34 00:03:45,076 --> 00:03:53,087 only, if both the bits are one, right. So, so, this is equal to one, if and only if a 35 00:03:53,087 --> 00:04:00,007 equal to b equal to one and zero otherwise. So now, is there any way that 36 00:04:00,007 --> 00:04:08,001 this circuit could be, you know, even if we output any other bit of our choice, is 37 00:04:08,001 --> 00:04:15,000 there any way of making this, this a reversible gate, a, a reversible circuit? 38 00:04:15,000 --> 00:04:21,067 And I claim its not. So you know, just, just play with it and check, that there's 39 00:04:21,067 --> 00:04:27,090 no way to recover a and b if you're given a and b as one of the, one of the, one of 40 00:04:27,090 --> 00:04:34,003 the outputs. And something arbitrary for the, for the second bit, you could choose 41 00:04:34,003 --> 00:04:40,081 it to be b, you could choose it to be a or b. Just choose it to be anything you want 42 00:04:40,081 --> 00:04:48,003 and check that there isn't enough information in this to tell you about, 43 00:04:48,003 --> 00:04:55,067 about, about what the, you know, what the two inputs are. You see because, why, why 44 00:04:55,067 --> 00:05:01,051 is that? Well, because if, if this, if the end of these two bits is zero, then there 45 00:05:01,051 --> 00:05:07,007 are three possibilities that are consistent with it, but this bit whatever 46 00:05:07,007 --> 00:05:13,007 this, this output bit is, no matter how you create it, it can only tell you about 47 00:05:13,007 --> 00:05:19,007 two possibilities. So, there is no way we could identify which of the three, three 48 00:05:19,007 --> 00:05:26,026 images we came from by only two different possibilities here. Okay, so clearly, if 49 00:05:26,026 --> 00:05:35,000 we were to go ahead and implement our function in a straight forward way, it 50 00:05:35,000 --> 00:05:45,000 would not be reversible. So, what can we do? Okay, so what we want to do is somehow 51 00:05:45,000 --> 00:05:53,036 we want to, we wan t to feed in the input x, as well as an answer bit b. So, we 52 00:05:53,036 --> 00:06:01,004 think of b as initially being zero. So, it's a, it's a, it's a place where the 53 00:06:01,004 --> 00:06:09,035 answer is going to be stored. And we want our quantum circuit to output x unchanged, 54 00:06:09,035 --> 00:06:17,044 but also the answer f (x). And maybe, you know, what, what it does is it, it, it, x 55 00:06:17,044 --> 00:06:26,087 solves b with f (x). So, it takes the sum of two of the two. So, it, it, it flips b, 56 00:06:26,087 --> 00:06:35,090 if and only if x = one. And now, if you were to compute use of f again, well this 57 00:06:35,090 --> 00:06:41,079 would, this would, this would undo everything and, and would, it would 58 00:06:41,079 --> 00:06:48,001 restore the state of this, this output bit. Okay. So, this is what we want to do 59 00:06:48,001 --> 00:06:56,005 ideally, and so, let's try to see that we can, we can actually implement our basic 60 00:06:56,005 --> 00:07:02,009 gates in a reversible matter. So, let, let's start by looking at simple examples. 61 00:07:03,009 --> 00:07:10,046 What about the NOT gate? Our claim is it's, it's already reversible, right? It 62 00:07:10,046 --> 00:07:18,045 takes as input the NOT gate we, we also called x, right? Because it takes as input 63 00:07:18,045 --> 00:07:28,007 a bit, zero, one. And, and it outputs, it, it, it, you know, if the input was zero, 64 00:07:28,007 --> 00:07:35,009 then the output is one and if the input is one, and output zero. So, that, that's 65 00:07:35,009 --> 00:07:43,005 already a reversible gate and in fact, the quantum analog of it is exactly the x gate 66 00:07:43,005 --> 00:07:51,052 which, which we know about. Similarly, if you were doing an x r, is like a CNOT 67 00:07:51,052 --> 00:08:03,096 gate, takes as input two bits, a and b, outputs a, ax, or b. And, of course, we 68 00:08:03,096 --> 00:08:09,073 know the CNOT is its own inverse so, so it's reversible. But what about the AND 69 00:08:09,073 --> 00:08:16,077 gate, that's the one we have trouble with. So now, consider a controlled SWAP gate. 70 00:08:16,077 --> 00:08:24,003 So, here's, here's how we might right this controlled SWAP. Here's how we might draw 71 00:08:24,003 --> 00:08:30,070 it. So, it, it has three wires, the first is a control, and then we have the second 72 00:08:30,070 --> 00:08:38,052 two where what this control wire does is, if the control wire is a one, then you 73 00:08:38,052 --> 00:08:46,029 swap the other two. So, you have a and then b, c, and b and c gets swapped if and 74 00:08:46,029 --> 00:08:56,001 only if a = one. So, why should this allow us to compute the end of two bits? So, 75 00:08:56,001 --> 00:09:05,082 imagine that we have, we have c = zero. So now, what's this output going to be? Well 76 00:09:05,082 --> 00:09:14,019 if a is zero, then the output is zero. And if a is one, then the output is b. So. If 77 00:09:14,019 --> 00:09:24,005 a = zero, the output is zero. And if a = one, the output is b. So, this is another 78 00:09:24,005 --> 00:09:31,092 way of writing the AND function. Because the only way the output is one is if a = 79 00:09:31,092 --> 00:09:39,062 one, and b = one. So, this output is a and b. Okay, so, this is the way of computing 80 00:09:39,062 --> 00:09:45,035 the AND gate, in a way that's reversible, because the CSWAP gate is it's own 81 00:09:45,035 --> 00:09:51,025 inverse. So now, we have an AND gate, we have a NOT gate, so we have a NAND gate, 82 00:09:51,025 --> 00:09:56,051 and that's universal for classical computation. And so, what we can do is, 83 00:09:56,051 --> 00:10:02,005 given any classical circuit, we can replace all the NOT and the, well, we 84 00:10:02,005 --> 00:10:08,007 don't have to replace the NOT gates but we can replace all the AND gates by SWAP 85 00:10:08,007 --> 00:10:15,005 gates. In the process, we may have to add in new fresh bits, which I initialize to 86 00:10:15,005 --> 00:10:21,004 zeros and we get, we get certain bits which are, which are output which we 87 00:10:21,004 --> 00:10:30,069 didn't want. But that's okay, because, because that's just junk bits. Okay. So, 88 00:10:30,069 --> 00:10:37,017 so, this is, this is how the construction then works. We have been given some 89 00:10:37,017 --> 00:10:43,019 classical circuit. We want a reversible circuit which has exactly the same 90 00:10:43,019 --> 00:10:50,065 behavior. A classical reversible circuit and so, what we do is, we'll assume that 91 00:10:50,065 --> 00:10:57,054 all the gates in here are, are NAND gates. And, you know, AND, and NOT gates. The NOT 92 00:10:57,054 --> 00:11:04,038 gates, already reversible, AND gates we replace by these controlled SWAP gates. We 93 00:11:04,038 --> 00:11:11,006 feed in a number of fresh zero bits to help the circuit run. And the output is 94 00:11:11,006 --> 00:11:20,069 going to be the output of the circuit plus some junk bits. Okay. So now, is this good 95 00:11:20,069 --> 00:11:27,077 enough for our purposes? Well, how do we intend to use this in, in quantum 96 00:11:27,077 --> 00:11:34,040 computing? So, imagine that, that, that we had the circuit. And what we wanted was a 97 00:11:34,040 --> 00:11:45,008 unitary transformation which would do the same thing for us, okay? So, so, what we 98 00:11:45,008 --> 00:11:53,052 really want is, once we have this reversible circuit, we can actually, we 99 00:11:53,052 --> 00:12:01,000 can actually think about each its constituent gates as being a unitary 100 00:12:01,000 --> 00:12:08,015 transformation, okay, because, because if you go back to each of the constituent 101 00:12:08,015 --> 00:12:15,068 gates it's a NOT, CNOT, and CSWAP and all these are unitaries. And so, so this, this 102 00:12:15,068 --> 00:12:24,073 c ircuit can actually be implemented by a sequence of unitary gates and so we can 103 00:12:24,073 --> 00:12:36,095 equivalently write down the unitary circuit corresponding to this. Which on 104 00:12:36,095 --> 00:12:48,083 input x and 0's will output C (x) and junk (x), alright. This junk is going to be a 105 00:12:48,083 --> 00:12:57,057 function of x, in general. Okay. So , why do we want to do this? Well, because, now, 106 00:12:57,057 --> 00:13:04,071 we can also ask what happens if we, if we, provide this input not as a classical 107 00:13:04,071 --> 00:13:12,004 state, but as a superposition over all possible x. So, we might feed in sum over 108 00:13:12,004 --> 00:13:21,048 x, alpha x, x and this register could be, all zeros. These, these remaining bits all 109 00:13:21,048 --> 00:13:30,050 zeros. Now what's our output going to be? Well, remember, quantum circuit is linear 110 00:13:30,050 --> 00:13:42,005 so the output is sum of x alpha x C (x). And then, this register is going to be 111 00:13:42,005 --> 00:13:52,070 junk (x). Well, the junk (x), we don't want, so can't we just throw this away and 112 00:13:52,070 --> 00:14:01,048 be done with it? Okay, so, we are going to argue that, in fact, this junk is really 113 00:14:01,048 --> 00:14:06,072 critical and we really, you know, we really don't wanted that. Even if we throw 114 00:14:06,072 --> 00:14:11,076 it, throw it away , it's going to, it's going to cause trouble for us. That's 115 00:14:11,076 --> 00:14:17,061 because of the rules of quantum mechanics. So, let's see that in a moment. So, what 116 00:14:17,061 --> 00:14:23,032 we'll see is that. This is not the circuit that we want to end up with. The circuit 117 00:14:23,032 --> 00:14:28,040 that we want to end up with, the reversible circuit we want to end up with 118 00:14:28,040 --> 00:14:34,046 is one that actually erases the junk. And in its place, leave the input string x. 119 00:14:34,046 --> 00:14:40,069 So, it, it, it takes the input x and a bunch of zeroes. It outputs x as well as C 120 00:14:40,069 --> 00:14:46,001 (x), the output of the original circuit and some zeroes. So, for us, this 121 00:14:46,001 --> 00:14:52,023 situation is infinitely preferable to that one. This is really not good for us. So, 122 00:14:52,023 --> 00:14:58,007 let's see why's that the case and let's see how to, how to make this happen.