Okay so we are finally ready to start talking about quantum algorithms. And in
this lecture I'll talk about some of the building blocks that go into making up
quantum algorithms and how they were used in some early quantum algorithms to
demonstrate the power of quantum computing. Okay so, so let's see. Last
time we already talked about reversible computation, classical reversible
computation, where we said suppose you have a classical circuit, that on input x
computes C(x). And for now I'm, I'm just going to talk about the case where C(x) is
a, is boolean. So it's, it's just a single bit, just for simplicity. So then we said
that there's a, there's a classical reversible circuit. Which takes as input x
and answer bit B. As well as a number of work bits, which are all initialized to
zero. And then, what this reversible circuit does is, it spits out x unchanged.
It also leaves the work bits in a clean state. So they are, they are also in the
zero state. And it, it, it XORs the answer C(x) into this, into this answer bit B. So
the output bit becomes b XOR C(x). So it toggles the bit b. So in the case that b0
is zero, then this answer bit is exactly C(x). Now, the other thing we said is
that, if we start with such a, such a reversible circuit, we can, we can also
implement it using quantum gates. And so we get this unitary transformation U sub C
which in the case that the input bits happen to be, happen to be classical in,
in this basis states Then the behavior is exactly the same as we had before. Except,
of course, now since U is a, is a unitary, it's a, it's a quantum circuit. So it can
take as input of superposition inputs. So for example, if we give it as input, the
superposition sum of all x of alpha XX. And then bs, well let's, let's, let's just
say the input bit is always b. And I'll suppress these, you know, the work bits.
Then the output, is sum over all x. Now fax, same amplitude. Input string is the
same, and the output string is b XOR C(x). So you can compute and superposition this
way. Now, this is one of the basic primitives for quantum computation. The
fact that we can compute. Anything that we can compute classically we can compute in
superposition. But this is not yet enough. We need one more ingredient and the
crucial ingredient turns out to be the Hadamard transform. So remember what the
Hadamard transform is? It's a, it's a transform on a single qubit which maps
zero to plus and one to minus. And the plus of course, is one / square root
two(0) + one / square root two(1). And minus is one / square root two(0) - one /
square root two(1). That's how, that's, that's the Hadamard transform. That's our
transformation. But, but now we can also perform this Hadamard transform on two
qubits. Now remember what the so, so now what happens if you perform it on two
qubits? Well, of course what we'd have is 00 would get mapped to (++) which turns
out to be one, well it's, what is it? It's one / square root two(0) + one / square
root two(1) tensor with one / square root two(0) + one / square root two(1) which is
just one-half(00) + one-half(01) + one-half(10) + one-half(11). So what it
does is it takes (00) as input, and outputs an equal superposition over all
the four inputs. And now, you can work this out for all the other input strings.
Or the, the rest of the three. Let's just work it out for (eleven). So what does it
do? It outputs (--) which is one / square root two(0) - one / square root two(1)
tensor with one / square root two(0) - one / square root two(1). And what's that?
Well, that's a one-half(00) - one-half(01) + one-half (ten) sorry - one-half(10) +
one-half(11). So to understand this, this sign pattern. So, so basically, you know,
you, you should, you should check that all the four classical strings get mapped to a
superposition of 0s you know (00), (01), (ten), and (eleven) with amplitudes. All
the amplitude of + or - are one-half so the only, the, the only differences what
the sign pattern is. And to understand the sign pattern you have to realize that each
of the, these Hadamards maps one when, when you, when you start with one and end
up with one, you get a, you get a negative sign. So, so, so this sign pattern ends up
being the parity of how many one to one transitions there are. Now if you want to,
if you want to write out this, the, the unitary transformation, you take the
tensor product of this two by two matrix with itself and if you remember the rules
for doing that, you would just fill in one / square root two this matrix in the, in
the upper left. So you get one-half, one-half, one-half - one-half. And the
same thing here you get one-half, one-half, one-half - one-half. Same thing
here. One-half, one-half, one-half - one-half. And then for this, this thing,
what you're doing is you're, you know since this entry is - one / square root
two you'd be multiplying this matrix by -one / square root two so you'd get
halves, but you'll also change signs. You'd get - one-half - one-half - one-half
and one-half. Okay, so that's, that's your Hadamard transform on two qubits.
Similarly you could do a Hadamard transform on three qubits. And you'll get
an eight by eight matrix. And you'd be mapping, for example 000 to an equal
superposition. So one / twice square root two(000) so on up to (111). So there would
be eight such possibilities. And again, you'd get a different sign pattern
depending upon what, what string you started from. So make sure you work
through this to understand that, you know what this pattern looks like. Okay, so one
thing you, you realize as you, as you, do this is what the Hadamard transform does
is it, it starts with a classical string on the, on the left, you know one of the
basis strings. And it gives you a superposition over all the two^N N bit
strings. So this is a very powerful thing and it's a very important thing in quantum
algorithms. Very important principle. So now let's try to understand what happens
when we let, work with N qubits, as N tends to infinity. So what, what, what
happens? Well, so, so now we have, we have N qubits. Let's say they were all
initialized to, you know we start with, with each of them in the zero state, and
they put them through the Hadamard circuit, where each of them is going
through a Hadamard gate. What's the output? Well, the output is clearly the +
state on all the qubits which is equ al to what? Well I claim that it's just going to
be the sum over all N with strings. So remember this is how we denote the N bit
strings. Where each such x has equal amplitude, and the amplitude is two^N/2
right? Because we'll get one / square root two, how did we get this? Well this is one
/ square root two(0) + one / square root two(1) tensor with itself n times.
Alright. So it's a tensor product with itself, N times. So, another way we
denotes this is by just saying, one / square root two(0) + one / square root
two(1). And then in the exponent we just put, put down, this notation tensor with
itself N times. And now if you, if you multiply these out, what do you get? Well,
you get, you know, depending upon which, you know, which, which choice you take
from each, from each of these, each of these terms, you get, you get sum N bit
string. And what's its amplitude? Well, you get one / square root two one / square
root two N times which is one / two^N / two. Okay, but now let's try to understand
what happens if you, if you start with some U = U1 U2 through U sub N. So let's
say those are the N bits of U. So what happens when you perform the Hadamard
transform on this? So, let's, let's, let's say what's our notation for this? It's H
tensor with itself N times applied to U which, so now what do we get? Well, I
claim that what we get is still the sum over all x of length N(x). But now, in
front of each of these Xs we have, its amplitude is, is one / two^N / two but
with either + or - sign. So, when do you get a + sign and when do you get the -
sign well, you get - one to the U.x where U.x is U1 X1 + ... + Un Xn. Okay? So,
remember what, what we, what we already discussed before. The, the only time you
get a -one sign is when you input bit. So these are input bits now. They are U one,
U2, so on up to U sub N. And output bits are now X1, X2 and so on up to X sub N.
Okay. So when do you get a, when do you get a - sign? Well, only when the input
bit is equal to the output bit equal to one, right? So U.x is counting how many,
how many such - signs you get? And the n when you take - one to this bar, it tells
you whether you get an odd number or an even number of - signs. And so your
overall phase is negative if and only if you get an odd number of - signs, right?
So, for example if N = three. U = (111). X = (101) then what's, you know what, what
would you get? Well, you'd get U.x is = to one, one plus one zero + one, one which is
two. And so, -one^U.x divided by two^N / two would be -one^2 / two^3 / two which is
one / two^3 / two. So that would be the amplitude of x which is this. If you start
with, with the input being (111). Okay. So now here's the new primitive that we have.
The new primitive that we have is that we can start with any old superposition psi
that we want, so we setup some superposition on N qubit psi. Then we
apply the Hadamard transform. So we get as output some new superposition. So psi
might be the superposition sum / x, alpha XX. Psi hat is some new superposition sum
/ x beta sub XX. Okay. So this is sum / X beta sub XX. And now what you do is now
you perform a measurement and you measure. And so you see sum Y, so the output of
this is sum Y with probability beta sub Y magnitude squared. Okay, so this is our
basic, primitive in quantum computation. We call this fourier sampling because
well, we'll see this later what, what we call it fourier sampling because the
Hadamard transform is really the fourier transform over the group Z sub two of
addition twelve. Okay? But that's not the important part, it's, that's just name.
The important part is we have this primitive, which is set up any
superposition psi, so create some superposition psi. Now perform the fourier
transform or the Hadamard transform on these N qubits and then measure. What you
have sampled from, is this probab ility distribution. And this is called sampling.
What we want say is that this is a very powerful, primitive. Because, without
access to quantum, you know a quantum circuit which is doing exponential work in
figuring out. How these amplitudes alpha X interfere to give you the betas? You would
have a, a very hard time to tryin g sample from the same distribution classically.
Okay so, but how do we make sense of this? How, how do we find, you know what does
this really, this primitive really help us do?