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.