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.