Quantum computation is a remarkable field.
In fact, it's so remarkable sometimes it
seems almost like science fiction. It's
also a very recent field. It's a very
young field. It's only been around for a
couple of decades but in this short time,
it has caused us to rethink a number of
basic notions. Of course, it's caused us
to rethink, what is a computer it's cause
us to, it's, it's caused revolution and
cryptography in which vector systems are
considered secure. And it has caused us to
rethink the foundations of quantum
mechanics. So, what's the secret behind
this? Why is quantum computation such a
why is it have such a big impact? So, the
main thing about quantum computers is that
they can be exponentially more powerful
than classical computers. To appreciate
how remarkable this, this factors.
Consider, for example, let's say that we
have n = 500. And let's say that we had a
computer that could perform exponential in
n number of steps. So, it can perform
two^500 steps. And how big is two^500?
Well, it turns out that two^500 is already
larger than estimates for the number of
particles in the universe. So, it's much
larger than estimates for the number of
particles in the universe. It's also much
larger than estimates on the age of the
universe picoseconds. In fact, it's much
larger than the product of these two
numbers. So, what does this mean? Well,
what it means is that if you were to
imagine classically that each particle in
the universe, each element particle in the
universe was a computer and that it was a
very powerful computer and it was, it was
so powerful that it could perform a step
of computation in a picosecond. And
moreover, each of this computers was
working in parallel for the entire age of
the universe. This would not be sufficient
time for you to run in algorithm, a
program required two^500 steps. And so, if
quantum computers are exponentially
powerful, this is a really remarkable fact
about what they can solve, how, you know,
what are the kinds of computational
problems they could actu ally solve in a
reasonable amount of time? Okay so, what
are these computational problems that they
can solve so quickly? So, the most famous
example of a computational problem that
can be solved efficiently on a quantum
computer is factoring. So, in factoring,
you are giving us input, a number n. So,
for example, n might be 60. Now, what
you're asked to do is to find the prime
factors of m so you want to factorize m as
into its five prime factors p1^e1 x p2^e2
x so on, pk^ek. So, for example, if n =
60, you want the prime factors, two^2 x
three x five because 60 is four x five,
three x four x five. Well, it turns out
that on a classical computer, we don't
know how to solve this factorization
problem efficiently. The best algorithms
for this take time that grows
exponentially in at least the square root
or the cube root of the length of the
input. So, they take exponential time. And
in fact, the factoring problem is
considered so difficult classically that
its the basis of the RSA cryptosystem. So,
the RSA cryptosystem is secure, provided
that you can now factor a certain integer
efficiently. Now, one of the most famous
Quantum algorithm is Shor's algorithm for
factoring integers on a quantum computer
in polynomial time. So, what this does is
it, it turns you that if you have a
quantum computer, we'd actually be able to
break RSA Cryptosystem which is, which is
actually the cryptosystem that you use if
you, if you have to purchase something
from Amazon online. In fact, quantum
algorithms may break most public key
cryptosystems. And so, this is quite a
remarkable aspect of quantum computers. On
the other hand, you have to be careful.
Not all computations can be speed up of
exponentially, in fact, in order to show
that a quantum computer can solve a, solve
a problem faster, exponentially faster
than classical computer, you have to find
a certain kind of structure in it and you
have to design a special kind of algorithm
for it. These are the so-called quantum
algorithms and in this course we'll, we'll
study how to design these algorithms. In
fact. We'll, we'll study, you know, by the
end of this course, you'll actually learn
how to factorize integers efficiently on a
quantum computer. There are a lot of
articles in the popular press about
quantum computers. And not all these
articles get it, get it right. In fact,
the popular press seems to often
exaggerate results about quantum
computers. So, for example, five years
ago, the economists, which is otherwise of
a respectable magazine reported that first
that there was a practical quantum
computers that have been built. And
secondly it, it also, it also discussed
how using this quantum computer, you could
solve the so-called NP complete problems
not only efficiently but you could solve
them in one shot. Okay, so in this course
we'll, we'll actually learn the truth
about this, you know, you'll actually
learn what are the limits of, of quantum
computers, that there are certain problems
that we do know how to solve efficiently
on a quantum computer. Okay. So, let's
talk a little bit about the structure and
the organization and the thinking behind
this course. So, this course is based on
an undergrad course that we've been
teaching at Berkeley for the last few
years. And, one of the organizing
principles of that course is that we
wanted it to be accessible to students
from many different backgrounds including
Electrical Engineering and Computer
Science, Physics, even Chemistry or
Mathematics. But this poses a little bit
of a problem because of course, there are
some background, various kinds that's,
that's required to study the quantum
computation. So, in particular, how would
our Physics and Chemistry students
understand everything in this quantum
computing course without knowing a lot of
background material in Computer Science?
Well, the way the course is organized,
it's track, it's designed to be as self
contained as possible which means that, if
you are a Physics student, you'd be able
to follow most of the course, of course,
you would need some very basic concepts
and computations, some of which you
hopefully already have some which would
pick up in the course itself and then
maybe there are some things such as you
know, such as complexity classes or some
fine points about algorithms that, you
know, which maybe you would not have as a
background and, and the way the courses
are organized then maybe would miss only a
very small part of it so a small part of
one lecture or maybe, maybe half of some
lecture but, but so that you can follow
most of the course. Now, there's one
other, one other thing that you know,
that's we're thinking about which is well
how does it work for Computer Science
students who do not have a background in
quantum mechanics? Obviously this is
something that that's essential if you
want to study quantum computation. In
fact, quantum algorithms are based on, on
some very interesting properties of
quantum mechanics you know, the super
position principle or entanglement and
certainly you cannot understand any of
these without understanding basic quantum
mechanics. And so, you know, so, when we
say about knowledge of quantum mechanics
is not a prerequisite for this course. So,
doesn't this make this, this course as
difficult as two courses folded into one,
you know, Introduction to Quantum
Mechanics and an Introduction to Quantum
Computation. Well, so, the reason it's not
is because there's this basic concept of a
quantum data. This is a basic building
block which is a very simple building
block for quantum algorithms. And we can
describe the basics of quantum mechanics
in terms of qubits and that's the approach
that, that I'm going to take in this
course. And so, so, this course was will
also serve as, as a very simple
introduction to quantum mechanics. And
what we'll do is we'll approach quantum
mechanics and quantum computation is in
qubits, as our billing blocks and quantum
gates to manipulate these qubits. You
know, this is not only a simpler way to
approach quantum mechanics but it also
emphasizes some of the intuitive and
paradoxical elements of quantum mechanics
the ones that actually quantum computation
exploits you know. And so you know, even
for some of you who have already studied
quantum mechanics, you might find that
this helps you understand some aspects of
the subject at a much deeper level. Okay,
in terms of I have mentioned the Berkeley
course that this in this online course is
based on, well, actually the, you know,
the online course is, is covers roughly
the first eight weeks of the Berkeley
course. The remaining about five weeks of
the course, five to six weeks of the
course okay so at the, at the end of this
eight weeks, you will, of course, learn
about basic quantum mechanics but also
about how to factor integers in polynomial
time on a quantum computer so we'll, we'll
study the factoring algorithm and also
Grover's quantum search algorithm. So and
you will also understands some of the
limits of quantum algorithms. So you know,
our kind of understanding of whether or
not quantum computers can solve NP
complete problems in polynomial time.
Okay, so that's, that's what the course
will cover. The last five weeks of, of
Berkeley course actually what, what, what
that covers is how would you implement
qubits and quantum gates in the lab. So,
you know, how could one build a quantum
computer and what's the current state of
the art. So, implementing qubits and
quantum gates using the spins, protons,
etc., atoms.