Okay. So, so now why do we want to remove
this junk? Well the reason it's important
to remove this junk is because it prevents
quantum interference. So let's see an
example of this. So suppose that we had a
quantum, we had a circuit that on input x,
just outputs x. So x is a bit and the
circuit just does nothing to it, it
outputs x as is. So of course, if we, if
this is was a quantum circuit and we input
summation of x, x then the output is also
summation of x, x because it does nothing
to the, to the output. Okay, so, so now,
suppose that we have this quantum circuit,
and then further we feed the output into a
Hadamard gate, okay? And let's say that we
set up the input to this circuit to be in
the plus state. So, so, lets say that
input was one over square root two zero
plus one over square root two one. And
now, so the output of the, the, the first
circuit is also in the plus state and when
this is fed into the Hadamard, out pops
the zero state. So if we measure, if we
were to measure this output, we'll see
zero with probability one. Okay. So, this
is what we wanted to happen. Okay. But now
instead, let's say we started with this
classical circuit which on input x,
outputs x. So this was a classical
circuit. We convert this into, into a
reversible circuit. So R sub c. And let's
say that the process of converting it into
a reversible circuit, the following
happens to it. So it takes as input x as
well as some clean bits zero and it
outputs the correct answer, but it also
creates some junk. And let's say the junk
it creates is a function of x and in fact,
it's x itself. So it just makes another
copy of this input bit. Okay, now since
this is a reversible circuit, all the
gates are reversible, we go ahead and make
this out of quantum gates. Maybe our
universal family, maybe, maybe using just
the c swap as a, including c swap and now
you know as the family. So now it takes as
input two, two cubits, outputs two cubits
where now what we'd like is to, is to
understand what happens when we feed the
output into a Hadamard gate, right? So we,
we take as input the plus state one over
square root two zero plus one over square
root two one and this, and this clean bit.
And now the output of this, of this
circuit is one over square root two zero,
zero plus one over square root two zero
one. And now what happens when we actually
do a Hadamard of the first qubit? Well,
this part goes to one over two zero, zero
plus one over two one zero, and this gets
transformed to one over two zero one plus
one over two one, one. So we get all four
strings. And now what happens is when we,
when we measure the first, first qubit, we
see zero and one with equal probability
which is different from what we had here.
So let's see. What, what happened here?
When you see, what happened here is that,
when we did a Hadamard transform on this,
on this on this first qubit so, so, lets,
lets say we, we do a Hadamard transform
here. Okay. So, so lets see first what
happened when we did the Hadamard here
without the junk qubits. Well, so one over
square root two is zero after the Hadamard
went to one over two zero plus one over
two one whereas one over square root two
one after the Hadamard went to one over
two zero minus one over two one. And so
when you start with the superposition of
these two, you have to add these two and
this part cancels, so that's destructive
interference. This part reinforce each
other in constructive interference. And
you get as outcome, half plus a half,
which is one times zero. What happens
here? Well here, this piece gets mapped to
that and this piece gets mapped to that.
But, but see before, in this case, this
minus should have cancel that one. And so
you should have been left only with the
first qubit equal to zero. But now, the
second qubit doesn't allow these two
pieces to interfere with each other
because these two are different, different
states. These are orthogonal states. They
can't interfere with each other. And so
the presence of this junk here, junk of x,
actually prevents an interference pattern
from happen ing and so we get the wrong
results in our quantum computation. Okay.
So, you can still ask, well, can't we just
throw away the junk qubits? The answer is
no. You can't throw away the junk qubits.
You see, because, remember what, you know,
we had, we had we had a state when we fed
in one over square root two zero plus one
over square root two one, and a zero here,
what we got out is one over square root
two zero, zero plus one over square root
two one, one which you might recognize as
the Bell State. So now in the Bell State
if you throw away one of the qubits,
right? Throw it away you know, send it to,
send it, send it to the other part of the,
of the city, send, send it across the
country, doesn't matter, they're still
entangled, right? You, you can't just
throw it away. You can't change the state
of these two qubits to intense the product
state just by throwing away the qubit. In
fact, when you throw away the qubit, it's
as though you measured it. Okay? So this
really doesn't help at all. What we have
to do is somehow make sure, change the
circuit so that the junk qubits are not
created. It turns out there's a very
elegant way of doing this. So what do you
do? Well, let's remember, this was our
reversible circuit. It takes as input x, a
bunch of zeroes it outputs C of x, the
correct answer. But then it also outputs
this junk which is, which may be a
function of x. So what are we going to do?
Well, remember we have, it's a reversible
circuit, so we could, we could apply the
reverse of the circuit, okay? So, so we
could, we could, we have the inverse of,
of, of the circuit and if we apply it, it
gets rid of the junk. And restore all
these, all these bits back to zero. But of
course, there's a problem because it also
takes the answer C of x and it restores it
to x. So, that's not very good. It's, you
know, we've thrown out the baby with the
bathwater. So, how can we get rid of the
junk, but also keep the answer bits
around? Well the answer is simple, all we
do is copy it. So, what we do is, is
before we, we ap ply the inverse circuit,
we just, we just start with some, some
fresh bits where we, where we set y to be
all zeroes and then we do a CNOT from each
of these answer bits into these, into
these y bits. Okay. So we, if, if y is
zero then, then we get a copy of the
answer bits, the output of the circuit.
And now we are free too run the inverse of
this, of this circuit. And so what it does
is it erases the junk, erases the answer,
restores the input. And so what we have
finally is what we were looking for. We
have, we have a circuit where we gave as
input x, bunch of zeroes, maybe y's also
zeroes. Now what do we get as output? We
get a bunch of zeroes, we get, we get x.
So, so the input is copied over, this is
important for their visibility, and then
we get the out, actual output we are
looking for, okay? And now the point is
that this is, there's, there's no junk,
there, there, there, there's no junk
associated with the, with the, with the
input. And so, this circuit, if you now
write as a quantum circuit, it actually,
it actually does what we want. And it
doesn't prevent interference. Okay. So, so
what's the upshot of what we, what, what
I, what I've been saying so far? The
upshot is, if you are given any classical
circuit, if you give me any classical
circuit C which takes as input x and
outputs C of x. What I can do is,
transform this into quantum circuit. Let's
call it use of C which states as input x
and a whole bunch of zeroes. And what it
does is it outputs x, C of x, and zeroes.
Okay? Now, because this is a quantum
circuit, you could also give it as input,
a superposition sum over x alpha x, x. And
in the second register we have a bunch of
zeroes. Now what's the output when you
apply this circuit to it? You get
superposition over x, alpha x, x in this
first register, C of x in the second
register, and a bunch of zeroes in the
third register. Right? You remember the
notation that we have, right? The, the
notation was if you write down x, y this
is the same thing as writing x tensor y,
and we even can write it as x, y its all
the same. Its just notation for saying
yeah, this many qubits, the, these are in
the state x, these are in the state y, its
a tensor product, okay? Okay. So, this our
basic theorem, it says given any classical
circuit you can convert it into a quantum
circuit, okay? It turns out that, okay. So
historically, the initial interest in
quantum computations started not with
trying to show that quantum computers
could be much more powerful than classical
computers. It actually started with, with,
people who wondered, could it be that
quantum mechanics imposes further
constraints on what can and cannot be
computed? So could it be that this fact
that, quantum mechanics is unitary and so
reversible? Does this mean that not
everything that you can compute
classically could be is allowed by quantum
mechanics? So maybe there are some
constraints that we weren't aware of so
far. And of course, this shows that there
are no such constraints and, and it shows
that given any classical circuit you can
actually make a corresponding quantum
circuit. Okay? And this will turn out to
be a very useful primitive as we move
forward into quantum algorithms.