1
00:00:00,000 --> 00:00:06,003
Hello everybody. So we are finally ready
to start talking about quantum algorithms.

2
00:00:06,003 --> 00:00:12,001
And so the rest of this course will be
devoted to quantum circuits, quantum

3
00:00:12,001 --> 00:00:17,006
algorithms, analyzing them. Okay so,
before we get there, let's talk about

4
00:00:17,006 --> 00:00:23,004
something that's very basic and which
forms. The, the, the basis of quantum

5
00:00:23,004 --> 00:00:29,001
algorithms this is why quantum computers
have this potential to be exponentially

6
00:00:29,001 --> 00:00:33,075
powerful. Okay? And this is one of the
great paradoxes of quantum mechanics.

7
00:00:33,075 --> 00:00:40,003
It's, it's, it's, it's probably it's to my
mind the most counter-intuitive aspect of

8
00:00:40,003 --> 00:00:46,002
quantum mechanics and it was one that was
missed for the good part of a century. So,

9
00:00:46,002 --> 00:00:53,005
it has to do with this exponential growth.
So, let's go back and remember what, what

10
00:00:53,005 --> 00:01:00,060
a qubit is, so remember our, our picture
of it is the electron in the hydrogen atom

11
00:01:00,060 --> 00:01:08,029
can either be in a ground state or in an
excited state which we think of as zero

12
00:01:08,029 --> 00:01:14,003
and one. And of course, quantumly the
super position principal tells us the,

13
00:01:14,003 --> 00:01:20,049
that, that the electron can be, can be in
a super position of these two states which

14
00:01:20,049 --> 00:01:27,030
is, which we can write as a unit vector in
a two dimensional vector space. Now, if we

15
00:01:27,030 --> 00:01:34,054
add one more qubit, so we have a two qubit
system, classically this could be one of

16
00:01:34,054 --> 00:01:42,071
four states, two bits. Quantum state is a
superposition of all these four states. So

17
00:01:42,071 --> 00:01:48,092
it's a unit vector in a four dimensional
complex vector space. Now we can keep

18
00:01:48,092 --> 00:01:56,083
going if you add one more qubit. So now
classically, we'd been, you know since

19
00:01:56,083 --> 00:02:02,050
there are three bits they can represent
eight possibilities. But once again, the

20
00:02:02,050 --> 00:02:08,059
quantum state of this system, of this
three qubit system is a superposition of

21
00:02:08,059 --> 00:02:14,078
all these eight possibilities which means
that it's a unit vector in an eighth

22
00:02:14,078 --> 00:02:20,007
dimensional complex vector space. Why
eighth? Well, another way of seeing it

23
00:02:20,007 --> 00:02:25,078
formally is you know we are gluing
together three different Hilbert spaces

24
00:02:25,078 --> 00:02:31,089
each of two dimensions and the way we glue
them together is by taking tensor products

25
00:02:31,089 --> 00:02:38,003
and so when we take a tensor product of c2
with itself three times the dimension

26
00:02:38,003 --> 00:02:44,036
multiplies and we get an eight dimensional
complex vector space. Now we can keep

27
00:02:44,036 --> 00:02:50,081
going this way and what if we, what if we
have an n qubit system? So now n bits can

28
00:02:50,081 --> 00:02:56,014
represent two to the n different
possibilities and again the quantum state

29
00:02:56,014 --> 00:03:02,007
is a super position of all these two to
the n possibilities. So its, its in a two

30
00:03:02,007 --> 00:03:12,037
to n dimensional complex vector space.
Again it's C2 tensor C2 tensor C2 n for a

31
00:03:12,037 --> 00:03:22,002
dimension of two to the n. Now this kind
of exponential growth and dimension is

32
00:03:22,002 --> 00:03:29,015
quite startling. So even for n = 500, two
to the 500 is an, is an unimaginably large

33
00:03:29,015 --> 00:03:36,018
number. It's, it's larger than the number
of particles in the universe. Its larger

34
00:03:36,018 --> 00:03:42,073
than the age of the universe in terms of
seconds and so if you were thinking about

35
00:03:42,073 --> 00:03:48,089
this as computing power of the system.
Well then, it's, you know this is more

36
00:03:48,089 --> 00:03:54,055
computing power than you could get by a
computer which, which was working for the

37
00:03:54,055 --> 00:04:00,076
age of the universe and have this really
incredibly quick cycle time. And moreover

38
00:04:00,076 --> 00:04:06,049
it was not just one computer, but it
consisted of, it was a parallel computer

39
00:04:06,049 --> 00:04:12,037
where every particle in the universe was,
was one of its course. So, this is, this

40
00:04:12,037 --> 00:04:18,061
is truly extravagant. If this, if we could
ever exploit this full computing power,

41
00:04:18,061 --> 00:04:26,002
this would be truly extravagant. Okay so,
now just a very quick reminder about where

42
00:04:26,002 --> 00:04:32,073
this exponential growth comes from. So
this comes from tensor products. Remember

43
00:04:32,073 --> 00:04:38,063
if you have a, if you have a, if you have
a k dimensional, a k state system

44
00:04:38,063 --> 00:04:44,061
represented by k dimensional Hilbert
space, then you can describe the state of

45
00:04:44,061 --> 00:04:49,007
this system with k parameters. And
similarly if you have a, if you have

46
00:04:49,007 --> 00:04:55,000
another system which has, which is an m
state system, so if n parameters require

47
00:04:55,000 --> 00:05:00,005
to describe it and now what happens if you
put these two systems together? So If

48
00:05:00,005 --> 00:05:05,007
these were classical systems, you could
describe the composite system using k+

49
00:05:05,007 --> 00:05:12,002
encrypt parameters. But when you take
tensor products, when you take a transit

50
00:05:12,002 --> 00:05:17,006
products to these two systems, which is
what you have to do quantumly, then the

51
00:05:17,006 --> 00:05:23,025
number of parameters you need to describe
this composite system is k m, right. So,

52
00:05:23,025 --> 00:05:29,007
you know another way of saying this is, if
this space is c^k, this one is c^m, those

53
00:05:29,007 --> 00:05:37,013
other two Hilbert spaces. Then this
composite system is represented by. C^k

54
00:05:37,013 --> 00:05:46,085
tenth of c^m which is. Isomorphic to c^km.
So the dimensions multiply, and this is

55
00:05:46,085 --> 00:05:53,012
where. We get this exponential growth from
if you take many, many copies of this. And

56
00:05:53,012 --> 00:05:58,019
the reason you have this, this increase,
in, in dimension, is because of

57
00:05:58,019 --> 00:06:03,025
entanglement. So, to describe this state
of this composite system, it's not

58
00:06:03,025 --> 00:06:08,055
sufficient to just describe this state of
A and the state of B. Because, these two,

59
00:06:08,055 --> 00:06:14,019
two systems in general be, be entangled
and so, and so you have to describe the

60
00:06:14,019 --> 00:06:20,086
state of the system by describing a
superposition over k m possibilities. Okay

61
00:06:20,086 --> 00:06:27,068
so let's, let's go back and look at all
this a little bit more pictorially. Might

62
00:06:27,068 --> 00:06:33,091
just do, just to make sure we understand
all this. So we have an n qubid system.

63
00:06:33,091 --> 00:06:39,084
Now, what the superposition principle
tells us is that the state of the system

64
00:06:39,084 --> 00:06:45,092
is a superposition of all the classical
possibilities. It's a, it's a unit vector

65
00:06:45,092 --> 00:06:51,096
in this exponentially large, exponentially
dimensional Hilbert space. Okay. So, so

66
00:06:51,096 --> 00:06:57,047
the, the state of the system in
particular, is a superposition over all n

67
00:06:57,047 --> 00:07:02,093
bit stringsx X where each has its
amplitude, alphas of x. And everything is

68
00:07:02,093 --> 00:07:09,079
normalized so the sum of the squares of
the magnitude of alpha x is one. Now, also

69
00:07:09,079 --> 00:07:17,075
the, the state of the system, how does it
evolve? Well, the way it evolves is by the

70
00:07:17,075 --> 00:07:24,042
application of, for our purposes, the
application of quantum gates. So we might

71
00:07:24,042 --> 00:07:31,068
pick two of these qubits and apply quantum
gate to it, which is represented by four

72
00:07:31,068 --> 00:07:38,065
by four matrix tensor identity on all the
rest of the qubits because we're leaving

73
00:07:38,065 --> 00:07:46,010
them alone, and the results of this is, if
you take this Hilber space, this complex

74
00:07:46,010 --> 00:07:53,094
vector space, can be rotated. And as we
rotate it, the state of the system changes

75
00:07:53,094 --> 00:08:00,017
and all these complex amplitudes get, get
updated. Okay, so this is an important

76
00:08:00,017 --> 00:08:05,085
point that even though we are actually
working on just these two cubits alone. So

77
00:08:05,085 --> 00:08:11,033
the effort we are putting in is we are
doing something. We're are applying some

78
00:08:11,033 --> 00:08:17,005
Hamiltonian to these two qubits alone. So
the effort required is proportional to two

79
00:08:17,005 --> 00:08:22,085
but behind the scenes what's happening is
that this entire Hilbert space got

80
00:08:22,085 --> 00:08:30,094
rotated, and all of these amplitudes, the
two^n amplitudes which represents the

81
00:08:30,094 --> 00:08:40,026
state of the n qubit system get updated.
Okay so, maybe let's, let's take a, let's

82
00:08:40,026 --> 00:08:49,036
take a closer look at what this might look
like. So, for example, let's say that, we

83
00:08:49,036 --> 00:09:00,002
had a n qubit system. And we, we happened
to apply a gate let's say we apply to this

84
00:09:00,002 --> 00:09:09,092
qubit. We apply a Hadamard gate, right?
So, what happens? Well, I claim what

85
00:09:09,092 --> 00:09:20,040
happens is that, if you look at, pair up
the alpha x's. So, so you look at x of the

86
00:09:20,040 --> 00:09:37,010
form zero x prime. And, and you look at x
of the form. One x prime, right? And you

87
00:09:37,010 --> 00:09:42,071
ask, what happens when you, when you
perform a Hadamard? Well you see, you're

88
00:09:42,071 --> 00:09:48,006
only performing a Hadarmard on the first
qubit. The rest of the qubits are left

89
00:09:48,006 --> 00:09:53,008
alone so x prime just stays x prime but
what happens to the first qubit? Well,

90
00:09:53,008 --> 00:10:01,097
when you apply the Hadamard, what happens
is, that the new amplitude of zero x prime

91
00:10:01,097 --> 00:10:10,008
is going to be equal to alpha zero x prime
+ alpha one x prime / square root two

92
00:10:10,008 --> 00:10:20,078
right? Because under, under the Hardamard,
what happens is that zero goes to zero

93
00:10:20,078 --> 00:10:27,097
with, with amplitude one / square root two
and one goes to one with amplitude to zero

94
00:10:27,097 --> 00:10:35,085
with amplitude one / square root two. And
so these amplitudes add up in this way. On

95
00:10:35,085 --> 00:10:42,074
the other hand, one x prime ends up with
amplitude alpha zero x prime - alpha one x

96
00:10:42,095 --> 00:10:50,008
prime / square root two, okay. But this is
true about all, all the possible n bits

97
00:10:50,008 --> 00:10:56,025
strings x. So what we've done is, we've
paired up all the n bit strings. And then,

98
00:10:56,025 --> 00:11:02,053
what does gate does is, it takes the
amplitudes of these two strings and then

99
00:11:02,053 --> 00:11:15,043
it mixes them up in this way. So what its
doing in effect is its updating. All the

100
00:11:15,043 --> 00:11:26,053
two^n amplitudes alphas of x in this way.
Okay, so now, let's think about what, what

101
00:11:26,053 --> 00:11:33,044
this is telling us. So what this is saying
is, first of all, for this 500 qubit

102
00:11:33,044 --> 00:11:39,079
system, 500 hydrogen atoms. So,
microscopic really, you know, tiny system.

103
00:11:39,079 --> 00:11:46,045
Nature must keep around somewhere two^500
pieces of scratch paper each with a

104
00:11:46,045 --> 00:11:54,090
complex number written on it. We know it
must but it's as though it is, right, it's

105
00:11:54,090 --> 00:12:00,095
as though nature has stored all these two
to the 500 amplitudes somewhere in its own

106
00:12:00,095 --> 00:12:07,050
internal memory. Okay, and then, every
time you perform a simple operation on

107
00:12:07,050 --> 00:12:13,007
these qubits. Even a local operation like
a Hadamard transform, something very

108
00:12:13,007 --> 00:12:20,054
simple. Nature is busily scratching out
these complex numbers two^500 of them,

109
00:12:20,054 --> 00:12:27,045
each from its scratch paper, and writing
new ones in their place. Two^500 as you

110
00:12:27,045 --> 00:12:32,091
saw is, is larger than number of particles
in the universe. Larger than the age of

111
00:12:32,091 --> 00:12:38,074
the universe, in femtoseconds. So now you
could, you could marvel at all this and

112
00:12:38,074 --> 00:12:44,021
you could say how is nature able to carry
out this, this sort of extravagance. You

113
00:12:44,021 --> 00:12:50,009
know you might even say, I just don't
believe it. I don't believe quantum

114
00:12:50,009 --> 00:12:55,037
mechanics is correct because, how could it
be that you know, that a theory which

115
00:12:55,037 --> 00:13:00,092
claims that nature behaves in, in, in such
a ridiculous fashion could possibly be

116
00:13:00,092 --> 00:13:06,080
true. The other way you can think about it
is, you can say okay, let's assume that

117
00:13:06,080 --> 00:13:13,042
nature does this. What are we going to do
about it? Can we use it some way? And then

118
00:13:13,042 --> 00:13:19,076
you can say to yourself. Well, what's a
computer? A computer is just a physics

119
00:13:19,076 --> 00:13:25,018
experiment, right? If you look, it's a
nicely packaged physics experiment. But if

120
00:13:25,018 --> 00:13:31,012
you look underneath the hood, you have
wires and transistors and currents and

121
00:13:31,012 --> 00:13:37,014
voltages, and so on. And so, a computer is
just a way of tricking nature into solving

122
00:13:37,014 --> 00:13:43,011
a problem of interest to you. So if nature
is working so hard at the quantum level,

123
00:13:43,011 --> 00:13:48,041
why should we be doing our computation at
a classical level? Should we be

124
00:13:48,041 --> 00:13:54,069
implementing computers at the quantum
level? That's the thought behind quantum

125
00:13:54,069 --> 00:14:02,087
computation. Okay, so there's a bit of a
rub, the problem is that this is the

126
00:14:02,087 --> 00:14:11,076
private world of nature, this exponential
superposition. As soon as you look at the,

127
00:14:11,076 --> 00:14:20,062
the system. You only see one of the n bit
strings with probability alpha x

128
00:14:20,062 --> 00:14:34,016
manitude^2. This is meant to be an alpha.
Okay, so, so you know it's, it's as though

129
00:14:34,016 --> 00:14:40,067
nature's this, you know it is, in quantum
mechanics nature behaves like one of these

130
00:14:40,067 --> 00:14:47,068
people where, you know they have this, you
know they have, they have this very rich

131
00:14:47,068 --> 00:14:54,022
life but its all pilot. You know and you
ask them hey, what's up? And they say oh,

132
00:14:54,022 --> 00:15:00,070
nothing, nothing ever happens, right? So,
so the question behind quantum computing

133
00:15:00,070 --> 00:15:06,080
really is we have a theory that nature is
exponentially extravagant, but on the

134
00:15:06,080 --> 00:15:13,005
other hand we have a measurement postulate
that says, which seems to suggest that

135
00:15:13,005 --> 00:15:18,060
nature covers her tracks and you know,
maybe, maybe there's, there's a way that

136
00:15:18,060 --> 00:15:23,077
nature never allows us to look behind,
behind the valence to see what's going on.

137
00:15:23,077 --> 00:15:29,069
And so the, the, the field of quantum
algorithms, quantum computing is trying to

138
00:15:29,069 --> 00:15:36,035
peel this veil aside and, and trying to
you know there's this tension between the

139
00:15:36,035 --> 00:15:42,044
measurement axiom and, and the, the first
two axioms, the super position and, and,

140
00:15:42,044 --> 00:15:48,037
and unitary evolution. And, and the field
of quantum algorithms and quantum

141
00:15:48,037 --> 00:15:53,078
computing tries to exploit this
exponential power despite the limited

142
00:15:53,078 --> 00:15:57,005
access that the measurement axiom affords
us