1
00:00:00,000 --> 00:00:07,002
Quantum computation is a remarkable field.
In fact, it's so remarkable sometimes it

2
00:00:07,002 --> 00:00:13,052
seems almost like science fiction. It's
also a very recent field. It's a very

3
00:00:13,052 --> 00:00:20,046
young field. It's only been around for a
couple of decades but in this short time,

4
00:00:20,046 --> 00:00:27,078
it has caused us to rethink a number of
basic notions. Of course, it's caused us

5
00:00:27,078 --> 00:00:38,041
to rethink, what is a computer it's cause
us to, it's, it's caused revolution and

6
00:00:38,041 --> 00:00:46,040
cryptography in which vector systems are
considered secure. And it has caused us to

7
00:00:46,040 --> 00:00:54,000
rethink the foundations of quantum
mechanics. So, what's the secret behind

8
00:00:54,000 --> 00:01:01,002
this? Why is quantum computation such a
why is it have such a big impact? So, the

9
00:01:01,002 --> 00:01:08,008
main thing about quantum computers is that
they can be exponentially more powerful

10
00:01:08,008 --> 00:01:17,005
than classical computers. To appreciate
how remarkable this, this factors.

11
00:01:17,005 --> 00:01:28,009
Consider, for example, let's say that we
have n = 500. And let's say that we had a

12
00:01:28,009 --> 00:01:37,004
computer that could perform exponential in
n number of steps. So, it can perform

13
00:01:37,004 --> 00:01:47,019
two^500 steps. And how big is two^500?
Well, it turns out that two^500 is already

14
00:01:47,019 --> 00:01:58,061
larger than estimates for the number of
particles in the universe. So, it's much

15
00:01:58,061 --> 00:02:09,057
larger than estimates for the number of
particles in the universe. It's also much

16
00:02:09,057 --> 00:02:28,040
larger than estimates on the age of the
universe picoseconds. In fact, it's much

17
00:02:28,040 --> 00:02:34,003
larger than the product of these two
numbers. So, what does this mean? Well,

18
00:02:34,003 --> 00:02:40,007
what it means is that if you were to
imagine classically that each particle in

19
00:02:40,007 --> 00:02:47,004
the universe, each element particle in the
universe was a computer and that it was a

20
00:02:47,004 --> 00:02:54,000
very powerful computer and it was, it was
so powerful that it could perform a step

21
00:02:54,000 --> 00:03:00,004
of computation in a picosecond. And
moreover, each of this computers was

22
00:03:00,004 --> 00:03:08,001
working in parallel for the entire age of
the universe. This would not be sufficient

23
00:03:08,001 --> 00:03:16,053
time for you to run in algorithm, a
program required two^500 steps. And so, if

24
00:03:16,053 --> 00:03:23,009
quantum computers are exponentially
powerful, this is a really remarkable fact

25
00:03:23,009 --> 00:03:29,009
about what they can solve, how, you know,
what are the kinds of computational

26
00:03:29,009 --> 00:03:35,007
problems they could actu ally solve in a
reasonable amount of time? Okay so, what

27
00:03:35,007 --> 00:03:41,008
are these computational problems that they
can solve so quickly? So, the most famous

28
00:03:41,008 --> 00:03:47,006
example of a computational problem that
can be solved efficiently on a quantum

29
00:03:47,006 --> 00:03:55,006
computer is factoring. So, in factoring,
you are giving us input, a number n. So,

30
00:03:55,006 --> 00:04:03,019
for example, n might be 60. Now, what
you're asked to do is to find the prime

31
00:04:03,019 --> 00:04:13,008
factors of m so you want to factorize m as
into its five prime factors p1^e1 x p2^e2

32
00:04:13,008 --> 00:04:23,076
x so on, pk^ek. So, for example, if n =
60, you want the prime factors, two^2 x

33
00:04:23,076 --> 00:04:32,014
three x five because 60 is four x five,
three x four x five. Well, it turns out

34
00:04:32,014 --> 00:04:40,032
that on a classical computer, we don't
know how to solve this factorization

35
00:04:40,032 --> 00:04:46,052
problem efficiently. The best algorithms
for this take time that grows

36
00:04:46,052 --> 00:04:53,005
exponentially in at least the square root
or the cube root of the length of the

37
00:04:53,005 --> 00:04:59,007
input. So, they take exponential time. And
in fact, the factoring problem is

38
00:04:59,007 --> 00:05:09,043
considered so difficult classically that
its the basis of the RSA cryptosystem. So,

39
00:05:09,043 --> 00:05:18,083
the RSA cryptosystem is secure, provided
that you can now factor a certain integer

40
00:05:18,083 --> 00:05:27,002
efficiently. Now, one of the most famous
Quantum algorithm is Shor's algorithm for

41
00:05:27,002 --> 00:05:34,009
factoring integers on a quantum computer
in polynomial time. So, what this does is

42
00:05:34,009 --> 00:05:42,001
it, it turns you that if you have a
quantum computer, we'd actually be able to

43
00:05:42,001 --> 00:05:49,002
break RSA Cryptosystem which is, which is
actually the cryptosystem that you use if

44
00:05:49,002 --> 00:05:55,004
you, if you have to purchase something
from Amazon online. In fact, quantum

45
00:05:55,004 --> 00:06:01,006
algorithms may break most public key
cryptosystems. And so, this is quite a

46
00:06:01,006 --> 00:06:08,004
remarkable aspect of quantum computers. On
the other hand, you have to be careful.

47
00:06:08,004 --> 00:06:15,002
Not all computations can be speed up of
exponentially, in fact, in order to show

48
00:06:15,002 --> 00:06:22,001
that a quantum computer can solve a, solve
a problem faster, exponentially faster

49
00:06:22,001 --> 00:06:28,001
than classical computer, you have to find
a certain kind of structure in it and you

50
00:06:28,001 --> 00:06:34,000
have to design a special kind of algorithm
for it. These are the so-called quantum

51
00:06:34,000 --> 00:06:40,000
algorithms and in this course we'll, we'll
study how to design these algorithms. In

52
00:06:40,000 --> 00:06:44,067
fact. We'll, we'll study, you know, by the
end of this course, you'll actually learn

53
00:06:44,067 --> 00:06:51,031
how to factorize integers efficiently on a
quantum computer. There are a lot of

54
00:06:51,031 --> 00:06:57,092
articles in the popular press about
quantum computers. And not all these

55
00:06:57,092 --> 00:07:04,014
articles get it, get it right. In fact,
the popular press seems to often

56
00:07:04,014 --> 00:07:09,076
exaggerate results about quantum
computers. So, for example, five years

57
00:07:09,076 --> 00:07:16,029
ago, the economists, which is otherwise of
a respectable magazine reported that first

58
00:07:16,029 --> 00:07:22,042
that there was a practical quantum
computers that have been built. And

59
00:07:22,042 --> 00:07:30,011
secondly it, it also, it also discussed
how using this quantum computer, you could

60
00:07:30,011 --> 00:07:38,056
solve the so-called NP complete problems
not only efficiently but you could solve

61
00:07:38,056 --> 00:07:44,056
them in one shot. Okay, so in this course
we'll, we'll actually learn the truth

62
00:07:44,056 --> 00:07:50,036
about this, you know, you'll actually
learn what are the limits of, of quantum

63
00:07:50,036 --> 00:07:58,007
computers, that there are certain problems
that we do know how to solve efficiently

64
00:07:58,007 --> 00:08:05,029
on a quantum computer. Okay. So, let's
talk a little bit about the structure and

65
00:08:05,029 --> 00:08:11,060
the organization and the thinking behind
this course. So, this course is based on

66
00:08:11,060 --> 00:08:17,022
an undergrad course that we've been
teaching at Berkeley for the last few

67
00:08:17,022 --> 00:08:22,047
years. And, one of the organizing
principles of that course is that we

68
00:08:22,047 --> 00:08:29,035
wanted it to be accessible to students
from many different backgrounds including

69
00:08:29,066 --> 00:08:39,032
Electrical Engineering and Computer
Science, Physics, even Chemistry or

70
00:08:39,032 --> 00:08:51,009
Mathematics. But this poses a little bit
of a problem because of course, there are

71
00:08:51,009 --> 00:08:56,093
some background, various kinds that's,
that's required to study the quantum

72
00:08:56,093 --> 00:09:02,039
computation. So, in particular, how would
our Physics and Chemistry students

73
00:09:02,039 --> 00:09:07,060
understand everything in this quantum
computing course without knowing a lot of

74
00:09:07,060 --> 00:09:12,051
background material in Computer Science?
Well, the way the course is organized,

75
00:09:12,051 --> 00:09:18,015
it's track, it's designed to be as self
contained as possible which means that, if

76
00:09:18,015 --> 00:09:23,074
you are a Physics student, you'd be able
to follow most of the course, of course,

77
00:09:23,074 --> 00:09:29,032
you would need some very basic concepts
and computations, some of which you

78
00:09:29,032 --> 00:09:35,034
hopefully already have some which would
pick up in the course itself and then

79
00:09:35,034 --> 00:09:41,083
maybe there are some things such as you
know, such as complexity classes or some

80
00:09:41,083 --> 00:09:47,073
fine points about algorithms that, you
know, which maybe you would not have as a

81
00:09:47,073 --> 00:09:53,093
background and, and the way the courses
are organized then maybe would miss only a

82
00:09:53,093 --> 00:09:59,095
very small part of it so a small part of
one lecture or maybe, maybe half of some

83
00:09:59,095 --> 00:10:05,046
lecture but, but so that you can follow
most of the course. Now, there's one

84
00:10:05,046 --> 00:10:11,064
other, one other thing that you know,
that's we're thinking about which is well

85
00:10:11,064 --> 00:10:17,054
how does it work for Computer Science
students who do not have a background in

86
00:10:17,054 --> 00:10:23,092
quantum mechanics? Obviously this is
something that that's essential if you

87
00:10:23,092 --> 00:10:29,037
want to study quantum computation. In
fact, quantum algorithms are based on, on

88
00:10:29,037 --> 00:10:34,043
some very interesting properties of
quantum mechanics you know, the super

89
00:10:34,043 --> 00:10:40,000
position principle or entanglement and
certainly you cannot understand any of

90
00:10:40,000 --> 00:10:44,088
these without understanding basic quantum
mechanics. And so, you know, so, when we

91
00:10:44,088 --> 00:10:51,016
say about knowledge of quantum mechanics
is not a prerequisite for this course. So,

92
00:10:51,016 --> 00:10:56,079
doesn't this make this, this course as
difficult as two courses folded into one,

93
00:10:56,079 --> 00:11:02,005
you know, Introduction to Quantum
Mechanics and an Introduction to Quantum

94
00:11:02,005 --> 00:11:08,021
Computation. Well, so, the reason it's not
is because there's this basic concept of a

95
00:11:08,021 --> 00:11:13,097
quantum data. This is a basic building
block which is a very simple building

96
00:11:13,097 --> 00:11:20,030
block for quantum algorithms. And we can
describe the basics of quantum mechanics

97
00:11:20,030 --> 00:11:27,004
in terms of qubits and that's the approach
that, that I'm going to take in this

98
00:11:27,004 --> 00:11:33,077
course. And so, so, this course was will
also serve as, as a very simple

99
00:11:33,077 --> 00:11:39,052
introduction to quantum mechanics. And
what we'll do is we'll approach quantum

100
00:11:39,052 --> 00:11:45,018
mechanics and quantum computation is in
qubits, as our billing blocks and quantum

101
00:11:45,018 --> 00:11:50,092
gates to manipulate these qubits. You
know, this is not only a simpler way to

102
00:11:50,092 --> 00:11:56,033
approach quantum mechanics but it also
emphasizes some of the intuitive and

103
00:11:56,033 --> 00:12:02,062
paradoxical elements of quantum mechanics
the ones that actually quantum computation

104
00:12:02,062 --> 00:12:09,001
exploits you know. And so you know, even
for some of you who have already studied

105
00:12:09,001 --> 00:12:14,031
quantum mechanics, you might find that
this helps you understand some aspects of

106
00:12:14,031 --> 00:12:21,003
the subject at a much deeper level. Okay,
in terms of I have mentioned the Berkeley

107
00:12:21,003 --> 00:12:27,098
course that this in this online course is
based on, well, actually the, you know,

108
00:12:27,098 --> 00:12:34,055
the online course is, is covers roughly
the first eight weeks of the Berkeley

109
00:12:34,055 --> 00:12:39,094
course. The remaining about five weeks of
the course, five to six weeks of the

110
00:12:39,094 --> 00:12:46,001
course okay so at the, at the end of this
eight weeks, you will, of course, learn

111
00:12:46,001 --> 00:12:51,098
about basic quantum mechanics but also
about how to factor integers in polynomial

112
00:12:51,098 --> 00:12:57,069
time on a quantum computer so we'll, we'll
study the factoring algorithm and also

113
00:12:57,092 --> 00:13:04,090
Grover's quantum search algorithm. So and
you will also understands some of the

114
00:13:04,090 --> 00:13:12,098
limits of quantum algorithms. So you know,
our kind of understanding of whether or

115
00:13:12,098 --> 00:13:19,064
not quantum computers can solve NP
complete problems in polynomial time.

116
00:13:19,064 --> 00:13:26,051
Okay, so that's, that's what the course
will cover. The last five weeks of, of

117
00:13:26,079 --> 00:13:34,095
Berkeley course actually what, what, what
that covers is how would you implement

118
00:13:34,095 --> 00:13:42,060
qubits and quantum gates in the lab. So,
you know, how could one build a quantum

119
00:13:42,060 --> 00:13:52,040
computer and what's the current state of
the art. So, implementing qubits and

120
00:13:52,040 --> 00:14:04,000
quantum gates using the spins, protons,
etc., atoms.