Okay. So, in this video, we'll talk about one other aspect of quantum circuits which
is their reversibility. And this is it, it turns out to be something that's, that's
eventually simple to deal with but its something that we have to tackle. So,
quantum computers are always reversible. So, what do we mean by that? So, let's
say, you have a quantum circuit U, it takes as input the state x. So, the output
is U, U (x). Now, it claim that there is some quantum circuit which, which undoes
this and, you know, on input U (x), it'll output x. So, what, what does this quantum
circuit look like? It's just U dagger. Right, U is unitary and so we know that U
times U dagger = U dagger times U is identity. In fact, there's something even
more that's true which is, which is that if you, if you look at the gates inside of
you, you can just take these gates and the U dagger, you just, you just create the
corresponding gates, G dagger and G' dagger and so on, in the opposite order.
And so, what happens is when you, when you put these two, these two circuits
together, then this, this gate annihilates that one and the next gate here will then
annihilate that, that one and so on because each one is the, is, is a
conjugate transpose of the corresponding one. And so, these two circuits completely
annihilate each other and, and so what you, what you have is the identity map
which just maps x to itself. Okay. So, so, that's what we mean by saying that quantum
computers are reversible, meaning that whatever you compute, you can also
uncompute if you like, by just doing the opposite of what you did, did to get
there. Okay. So now, let's see what this means, if we are, if we are just trying to
implement a classical circuit. So, for example, a classical circuit might be,
might be doing something like it might take its input, m bits and output one bit
and its computing some function f, the Boolean function f on input x. So now, how
would we, how would we actually compute this quantumly? Well, we, we have some
quantum circ uit for computing f, which on input x. So, there's ny's coming in and we
want one of the y's on the output to contain f (x), and of course, you remember
in the quantum circuit, if there's n inputs, there's always n output. And so,
from the reversibility property, it must be the case that, we then should be able
to compute. We, we should be able to uncompute this function and recover x from
this output. But is it always possible to recover that the input from that? Well,
think about an AND gate, right. So, if you have an AND gate, it takes as input two
bits, a and b. And it outputs a, the bits a and b which is, which is one, if and
only, if both the bits are one, right. So, so, this is equal to one, if and only if a
equal to b equal to one and zero otherwise. So now, is there any way that
this circuit could be, you know, even if we output any other bit of our choice, is
there any way of making this, this a reversible gate, a, a reversible circuit?
And I claim its not. So you know, just, just play with it and check, that there's
no way to recover a and b if you're given a and b as one of the, one of the, one of
the outputs. And something arbitrary for the, for the second bit, you could choose
it to be b, you could choose it to be a or b. Just choose it to be anything you want
and check that there isn't enough information in this to tell you about,
about, about what the, you know, what the two inputs are. You see because, why, why
is that? Well, because if, if this, if the end of these two bits is zero, then there
are three possibilities that are consistent with it, but this bit whatever
this, this output bit is, no matter how you create it, it can only tell you about
two possibilities. So, there is no way we could identify which of the three, three
images we came from by only two different possibilities here. Okay, so clearly, if
we were to go ahead and implement our function in a straight forward way, it
would not be reversible. So, what can we do? Okay, so what we want to do is somehow
we want to, we wan t to feed in the input x, as well as an answer bit b. So, we
think of b as initially being zero. So, it's a, it's a, it's a place where the
answer is going to be stored. And we want our quantum circuit to output x unchanged,
but also the answer f (x). And maybe, you know, what, what it does is it, it, it, x
solves b with f (x). So, it takes the sum of two of the two. So, it, it, it flips b,
if and only if x = one. And now, if you were to compute use of f again, well this
would, this would, this would undo everything and, and would, it would
restore the state of this, this output bit. Okay. So, this is what we want to do
ideally, and so, let's try to see that we can, we can actually implement our basic
gates in a reversible matter. So, let, let's start by looking at simple examples.
What about the NOT gate? Our claim is it's, it's already reversible, right? It
takes as input the NOT gate we, we also called x, right? Because it takes as input
a bit, zero, one. And, and it outputs, it, it, it, you know, if the input was zero,
then the output is one and if the input is one, and output zero. So, that, that's
already a reversible gate and in fact, the quantum analog of it is exactly the x gate
which, which we know about. Similarly, if you were doing an x r, is like a CNOT
gate, takes as input two bits, a and b, outputs a, ax, or b. And, of course, we
know the CNOT is its own inverse so, so it's reversible. But what about the AND
gate, that's the one we have trouble with. So now, consider a controlled SWAP gate.
So, here's, here's how we might right this controlled SWAP. Here's how we might draw
it. So, it, it has three wires, the first is a control, and then we have the second
two where what this control wire does is, if the control wire is a one, then you
swap the other two. So, you have a and then b, c, and b and c gets swapped if and
only if a = one. So, why should this allow us to compute the end of two bits? So,
imagine that we have, we have c = zero. So now, what's this output going to be? Well
if a is zero, then the output is zero. And if a is one, then the output is b. So. If
a = zero, the output is zero. And if a = one, the output is b. So, this is another
way of writing the AND function. Because the only way the output is one is if a =
one, and b = one. So, this output is a and b. Okay, so, this is the way of computing
the AND gate, in a way that's reversible, because the CSWAP gate is it's own
inverse. So now, we have an AND gate, we have a NOT gate, so we have a NAND gate,
and that's universal for classical computation. And so, what we can do is,
given any classical circuit, we can replace all the NOT and the, well, we
don't have to replace the NOT gates but we can replace all the AND gates by SWAP
gates. In the process, we may have to add in new fresh bits, which I initialize to
zeros and we get, we get certain bits which are, which are output which we
didn't want. But that's okay, because, because that's just junk bits. Okay. So,
so, this is, this is how the construction then works. We have been given some
classical circuit. We want a reversible circuit which has exactly the same
behavior. A classical reversible circuit and so, what we do is, we'll assume that
all the gates in here are, are NAND gates. And, you know, AND, and NOT gates. The NOT
gates, already reversible, AND gates we replace by these controlled SWAP gates. We
feed in a number of fresh zero bits to help the circuit run. And the output is
going to be the output of the circuit plus some junk bits. Okay. So now, is this good
enough for our purposes? Well, how do we intend to use this in, in quantum
computing? So, imagine that, that, that we had the circuit. And what we wanted was a
unitary transformation which would do the same thing for us, okay? So, so, what we
really want is, once we have this reversible circuit, we can actually, we
can actually think about each its constituent gates as being a unitary
transformation, okay, because, because if you go back to each of the constituent
gates it's a NOT, CNOT, and CSWAP and all these are unitaries. And so, so this, this
c ircuit can actually be implemented by a sequence of unitary gates and so we can
equivalently write down the unitary circuit corresponding to this. Which on
input x and 0's will output C (x) and junk (x), alright. This junk is going to be a
function of x, in general. Okay. So , why do we want to do this? Well, because, now,
we can also ask what happens if we, if we, provide this input not as a classical
state, but as a superposition over all possible x. So, we might feed in sum over
x, alpha x, x and this register could be, all zeros. These, these remaining bits all
zeros. Now what's our output going to be? Well, remember, quantum circuit is linear
so the output is sum of x alpha x C (x). And then, this register is going to be
junk (x). Well, the junk (x), we don't want, so can't we just throw this away and
be done with it? Okay, so, we are going to argue that, in fact, this junk is really
critical and we really, you know, we really don't wanted that. Even if we throw
it, throw it away , it's going to, it's going to cause trouble for us. That's
because of the rules of quantum mechanics. So, let's see that in a moment. So, what
we'll see is that. This is not the circuit that we want to end up with. The circuit
that we want to end up with, the reversible circuit we want to end up with
is one that actually erases the junk. And in its place, leave the input string x.
So, it, it, it takes the input x and a bunch of zeroes. It outputs x as well as C
(x), the output of the original circuit and some zeroes. So, for us, this
situation is infinitely preferable to that one. This is really not good for us. So,
let's see why's that the case and let's see how to, how to make this happen.