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?