Hello everybody. So we are finally ready
to start talking about quantum algorithms.
And so the rest of this course will be
devoted to quantum circuits, quantum
algorithms, analyzing them. Okay so,
before we get there, let's talk about
something that's very basic and which
forms. The, the, the basis of quantum
algorithms this is why quantum computers
have this potential to be exponentially
powerful. Okay? And this is one of the
great paradoxes of quantum mechanics.
It's, it's, it's, it's probably it's to my
mind the most counter-intuitive aspect of
quantum mechanics and it was one that was
missed for the good part of a century. So,
it has to do with this exponential growth.
So, let's go back and remember what, what
a qubit is, so remember our, our picture
of it is the electron in the hydrogen atom
can either be in a ground state or in an
excited state which we think of as zero
and one. And of course, quantumly the
super position principal tells us the,
that, that the electron can be, can be in
a super position of these two states which
is, which we can write as a unit vector in
a two dimensional vector space. Now, if we
add one more qubit, so we have a two qubit
system, classically this could be one of
four states, two bits. Quantum state is a
superposition of all these four states. So
it's a unit vector in a four dimensional
complex vector space. Now we can keep
going if you add one more qubit. So now
classically, we'd been, you know since
there are three bits they can represent
eight possibilities. But once again, the
quantum state of this system, of this
three qubit system is a superposition of
all these eight possibilities which means
that it's a unit vector in an eighth
dimensional complex vector space. Why
eighth? Well, another way of seeing it
formally is you know we are gluing
together three different Hilbert spaces
each of two dimensions and the way we glue
them together is by taking tensor products
and so when we take a tensor product of c2
with itself three times the dimension
multiplies and we get an eight dimensional
complex vector space. Now we can keep
going this way and what if we, what if we
have an n qubit system? So now n bits can
represent two to the n different
possibilities and again the quantum state
is a super position of all these two to
the n possibilities. So its, its in a two
to n dimensional complex vector space.
Again it's C2 tensor C2 tensor C2 n for a
dimension of two to the n. Now this kind
of exponential growth and dimension is
quite startling. So even for n = 500, two
to the 500 is an, is an unimaginably large
number. It's, it's larger than the number
of particles in the universe. Its larger
than the age of the universe in terms of
seconds and so if you were thinking about
this as computing power of the system.
Well then, it's, you know this is more
computing power than you could get by a
computer which, which was working for the
age of the universe and have this really
incredibly quick cycle time. And moreover
it was not just one computer, but it
consisted of, it was a parallel computer
where every particle in the universe was,
was one of its course. So, this is, this
is truly extravagant. If this, if we could
ever exploit this full computing power,
this would be truly extravagant. Okay so,
now just a very quick reminder about where
this exponential growth comes from. So
this comes from tensor products. Remember
if you have a, if you have a, if you have
a k dimensional, a k state system
represented by k dimensional Hilbert
space, then you can describe the state of
this system with k parameters. And
similarly if you have a, if you have
another system which has, which is an m
state system, so if n parameters require
to describe it and now what happens if you
put these two systems together? So If
these were classical systems, you could
describe the composite system using k+
encrypt parameters. But when you take
tensor products, when you take a transit
products to these two systems, which is
what you have to do quantumly, then the
number of parameters you need to describe
this composite system is k m, right. So,
you know another way of saying this is, if
this space is c^k, this one is c^m, those
other two Hilbert spaces. Then this
composite system is represented by. C^k
tenth of c^m which is. Isomorphic to c^km.
So the dimensions multiply, and this is
where. We get this exponential growth from
if you take many, many copies of this. And
the reason you have this, this increase,
in, in dimension, is because of
entanglement. So, to describe this state
of this composite system, it's not
sufficient to just describe this state of
A and the state of B. Because, these two,
two systems in general be, be entangled
and so, and so you have to describe the
state of the system by describing a
superposition over k m possibilities. Okay
so let's, let's go back and look at all
this a little bit more pictorially. Might
just do, just to make sure we understand
all this. So we have an n qubid system.
Now, what the superposition principle
tells us is that the state of the system
is a superposition of all the classical
possibilities. It's a, it's a unit vector
in this exponentially large, exponentially
dimensional Hilbert space. Okay. So, so
the, the state of the system in
particular, is a superposition over all n
bit stringsx X where each has its
amplitude, alphas of x. And everything is
normalized so the sum of the squares of
the magnitude of alpha x is one. Now, also
the, the state of the system, how does it
evolve? Well, the way it evolves is by the
application of, for our purposes, the
application of quantum gates. So we might
pick two of these qubits and apply quantum
gate to it, which is represented by four
by four matrix tensor identity on all the
rest of the qubits because we're leaving
them alone, and the results of this is, if
you take this Hilber space, this complex
vector space, can be rotated. And as we
rotate it, the state of the system changes
and all these complex amplitudes get, get
updated. Okay, so this is an important
point that even though we are actually
working on just these two cubits alone. So
the effort we are putting in is we are
doing something. We're are applying some
Hamiltonian to these two qubits alone. So
the effort required is proportional to two
but behind the scenes what's happening is
that this entire Hilbert space got
rotated, and all of these amplitudes, the
two^n amplitudes which represents the
state of the n qubit system get updated.
Okay so, maybe let's, let's take a, let's
take a closer look at what this might look
like. So, for example, let's say that, we
had a n qubit system. And we, we happened
to apply a gate let's say we apply to this
qubit. We apply a Hadamard gate, right?
So, what happens? Well, I claim what
happens is that, if you look at, pair up
the alpha x's. So, so you look at x of the
form zero x prime. And, and you look at x
of the form. One x prime, right? And you
ask, what happens when you, when you
perform a Hadamard? Well you see, you're
only performing a Hadarmard on the first
qubit. The rest of the qubits are left
alone so x prime just stays x prime but
what happens to the first qubit? Well,
when you apply the Hadamard, what happens
is, that the new amplitude of zero x prime
is going to be equal to alpha zero x prime
+ alpha one x prime / square root two
right? Because under, under the Hardamard,
what happens is that zero goes to zero
with, with amplitude one / square root two
and one goes to one with amplitude to zero
with amplitude one / square root two. And
so these amplitudes add up in this way. On
the other hand, one x prime ends up with
amplitude alpha zero x prime - alpha one x
prime / square root two, okay. But this is
true about all, all the possible n bits
strings x. So what we've done is, we've
paired up all the n bit strings. And then,
what does gate does is, it takes the
amplitudes of these two strings and then
it mixes them up in this way. So what its
doing in effect is its updating. All the
two^n amplitudes alphas of x in this way.
Okay, so now, let's think about what, what
this is telling us. So what this is saying
is, first of all, for this 500 qubit
system, 500 hydrogen atoms. So,
microscopic really, you know, tiny system.
Nature must keep around somewhere two^500
pieces of scratch paper each with a
complex number written on it. We know it
must but it's as though it is, right, it's
as though nature has stored all these two
to the 500 amplitudes somewhere in its own
internal memory. Okay, and then, every
time you perform a simple operation on
these qubits. Even a local operation like
a Hadamard transform, something very
simple. Nature is busily scratching out
these complex numbers two^500 of them,
each from its scratch paper, and writing
new ones in their place. Two^500 as you
saw is, is larger than number of particles
in the universe. Larger than the age of
the universe, in femtoseconds. So now you
could, you could marvel at all this and
you could say how is nature able to carry
out this, this sort of extravagance. You
know you might even say, I just don't
believe it. I don't believe quantum
mechanics is correct because, how could it
be that you know, that a theory which
claims that nature behaves in, in, in such
a ridiculous fashion could possibly be
true. The other way you can think about it
is, you can say okay, let's assume that
nature does this. What are we going to do
about it? Can we use it some way? And then
you can say to yourself. Well, what's a
computer? A computer is just a physics
experiment, right? If you look, it's a
nicely packaged physics experiment. But if
you look underneath the hood, you have
wires and transistors and currents and
voltages, and so on. And so, a computer is
just a way of tricking nature into solving
a problem of interest to you. So if nature
is working so hard at the quantum level,
why should we be doing our computation at
a classical level? Should we be
implementing computers at the quantum
level? That's the thought behind quantum
computation. Okay, so there's a bit of a
rub, the problem is that this is the
private world of nature, this exponential
superposition. As soon as you look at the,
the system. You only see one of the n bit
strings with probability alpha x
manitude^2. This is meant to be an alpha.
Okay, so, so you know it's, it's as though
nature's this, you know it is, in quantum
mechanics nature behaves like one of these
people where, you know they have this, you
know they have, they have this very rich
life but its all pilot. You know and you
ask them hey, what's up? And they say oh,
nothing, nothing ever happens, right? So,
so the question behind quantum computing
really is we have a theory that nature is
exponentially extravagant, but on the
other hand we have a measurement postulate
that says, which seems to suggest that
nature covers her tracks and you know,
maybe, maybe there's, there's a way that
nature never allows us to look behind,
behind the valence to see what's going on.
And so the, the, the field of quantum
algorithms, quantum computing is trying to
peel this veil aside and, and trying to
you know there's this tension between the
measurement axiom and, and the, the first
two axioms, the super position and, and,
and unitary evolution. And, and the field
of quantum algorithms and quantum
computing tries to exploit this
exponential power despite the limited
access that the measurement axiom affords
us