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