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.