UMESH VAZIRANI: Hello.
I'm Umesh Vazirani at UC Berkeley.
And I'm delighted to welcome you to this course
on Quantum Mechanics and Quantum Computation.
I'm sure many of you know that quantum computation
starts with this remarkable discovery that quantum
systems are exponentially powerful. So a major goal
of quantum computation is to harness this exponential power
to solve interesting computation problems. So in this
overview I want to tell you about what you can expect
to learn from this course, and how this course is organized.
OK.
So let's start with trying to understand more
precisely what it means when we say that quantum
systems are exponentially powerful. Imagine that
we have a small of quantum system over a few hundred
particles, like a few hundred electrons, or photons,
or something. So let's say, for definiteness we had a
system of 500 particles. Now if we could harness all
the computational power inherent in the system that
quantum mechanics promises us, then in each cycle of
the resulting quantum computer we would be able to
carry out exponential in 500s, say 2 to 500 steps.
Now how big is 2 to the 500? It sounds like a large
number. But the interesting thing is 2 to the 500 is
and possibly large number. So 2 to the 500 is much
larger than estimates for the total number of particles
in the universe. It's also much larger than estimates for
the age of the universe in femtoseconds. In fact, it's much
larger than the product of these two quantities. So what this
means is that if you could harness this computational power,
then there's no way that in the cla**ical universe we couldn't match
it, even if you were able to use the entire resources of the
universe in that computation. But now, of course, the
difficulty lies in harnessing this power. And there are
several challenges. And these are the challenges we'll
speak about in this course.
So first we have to pick the right computational
problems. So not every computational problem can be
sped up by quantum computation. Probably the most famous
example of a computational problem that can be sped
up is what's called the factoring problem, where you're given a number n
and you want to write it, factorize it into its prime power factors.
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
OK.
Now even if you have the right computation problem,
designing a quantum algorithm is a tricky task.
And actually, for those of you who are already
familiar with the design of cla**ical algorithms,
quantum algorithms look very, very different. And they
have very different design principles. So we'll talk
about things like the quantum Fourier transform, and a
completely new style of designing algorithms. We'll also
speak about, of course, what are the limits of quantum
computers? What are those problems that cannot be solved,
or we believe cannot be solved quickly, even if we
had quantum computers. And then there's, of course,
the challenge of building a quantum computer.
So this is something that hundreds of scientists
are working on around the world today. It's a very
difficult challenge. And in this course I'll just touched
upon, briefly, the kinds of systems and the principles
that go into designing such quantum computers. So that's
what we'll cover in quantum computing. But of course, in
order to study this, you'll have to learn the basics of
quantum mechanics. And this brings me to the other part
of the course, which is an introduction to quantum mechanics.
Now the way we'll study quantum mechanics in this course
is in terms of a very simple building block, which comes
from quantum computation, which is that of a qubit.
So just as a bit, it's the simplest representation
of information in the cla**ical world. A qubit is the
simplest quantum system that we can think of. And describing
quantum mechanics, the basic principles of quantum mechanics,
in terms of qubits, greatly simplifies the presentation.
So what this would mean is that within three to four weeks
we'll be in the position where we can start studying quantum
computation, the basic notions of quantum computation, as well
as quantum algorithms, designing quantum algorithms.
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
Now there's another advantage to studying quantum
mechanics this way, which is that we'll be able to
jump right into some of the most counterintuitive
aspects of quantum mechanics. So in particular, we'll
right away, probably the second week of the course,
start talking about entanglement, which is one of the most
mysterious aspects of quantum systems. And once we are
into entanglement, we'll actually talk about various manifestations
of it. We'll talk about bell inequalities, and we talk
about things like quantum teleportation. And so very
quickly, very soon in this course, you'll start
grappling with the counterintuitive aspects of
quantum mechanics. This is quite important because,
of course, quantum computation exploits the most counterintuitive
aspects of quantum mechanics. Now, there's a sense in
which this way of learning quantum mechanics might actually
be a good thing, independent of whether you are interested in
quantum computation or not.
So here's a quote from Niels Bohr, who is the famous
physicist who discovered the structure of that.
And he talks about how quantum mechanics is a very
counterintuitive theory. And anyone who's not
shocked by quantum mechanics has not understood it.
Another way of understanding this quote is that,
if you really want to deeply understand quantum
mechanics, then you have to grapple with the quantum
counterintuitive aspects of the theory. And so for those of
you who haven't really studied quantum mechanics before,
this way of approaching it, this emphasis on the one simple
systems, which illustrate the most counterintuitive
aspects of the theory, this might be the right way to
start studying the subject. And then later if you're
interested you can go on to take a standard course in
quantum mechanics to learn the physics of the
hydrogen atom, et cetera. And for those of you who've
already studied quantum mechanics, this treatment might
deepen your appreciation of quantum mechanics.
--------------------------------------------------------------------------
--------------------------------------------------------------------------
So this finally brings me to the required background for this course,
and the teaching philosophy of the course. So in terms of
required background, we've really tried to design this course
to make it as broadly accessible as possible. So to people
from computer science, physics, math backgrounds. And so the
prerequisites have been pared down to the minimal possible
prerequisites. So basically there are two prerequisites.
The main one is that you must have a solid background in
basic linear algebra. And the second requirement is
pretty simple one. You should be able to an*lyze the
running time, you must have seen how to an*lyze the running
time of a simple algorithm. You know any simple algorithm,
like sorting, or multiplying integers. How do you count the
number of steps of the algorithm as a function n, the size of
the input? So something very basic. OK let me also say a
few words about the philosophy of the course, or how
it's going to be taught. So there's one interesting aspect
of it, which is what I call a Kanban approach to mathematical
notation of math concepts. So this is an approach to manufacturing
that the Japanese had. A Kanban means just in time. It's a just in
time approach. So in the '80s they came up with this approach where,
instead of creating large inventories of raw materials and parts,
what they would do is make the inventories as small as possible
and have these parts supplied just in time. This made things much more efficient.
OK.
So what I after here is that you're going to be seeing a lot of
interesting new concepts, and many of these concepts are going to be
paradoxical. And understanding them, wrapping your mind
around these concepts and being able to intuitively understand
them is going to be quite challenging. And so what I want to do is,
I don't want to overload you with mathematical notation at the same
time that you're grappling with these concepts. What the course
will do is it will adopt Kanban approach to mathematical concepts
and notation. And so, to the extent possible, when a new concept
is introduced, I'll introduce it as naively as possible.
So that you're confronted with it, and you can build an intuition for it.
And then, of course, things will be made precise.
I'll push them off as late as possible. But in a way that it's
still understandable, and everything can be made precise.
Finally, let me just say that probably the most important
thing that you can bring to this course, make sure you bring
your imagination and your ability to think, grapple with these
concepts, some of which are going to be quite mind bending.
So it should be an exciting eight weeks.
And I hope you enjoy it.