1
00:00:00,000 --> 00:00:04,004
Hello everyone.
So, in this lecture we'll talk about

2
00:00:04,004 --> 00:00:11,002
unstructured quantum search or what's
called Grover's algorithm for database

3
00:00:11,002 --> 00:00:15,004
search.
So, the problem we are trying to solve is

4
00:00:15,004 --> 00:00:21,073
one of looking for a needle in a haystack.
Of course, in this case, we, our haystack

5
00:00:21,073 --> 00:00:27,051
and needle are digital.
So, what does a digital haystack look

6
00:00:27,051 --> 00:00:29,065
like.
So, think of you this way.

7
00:00:29,065 --> 00:00:34,094
You're given a table with, with n entries,
and one of these entries is marked.

8
00:00:34,094 --> 00:00:40,060
So, there is, there is a particular entry.
If you, if you look inside this entry

9
00:00:40,060 --> 00:00:46,040
you'll know, you'll know this is the entry
you are looking for and your goal is to

10
00:00:46,040 --> 00:00:52,047
find this, this special marked entry.
Now, how can you try to solve this

11
00:00:52,047 --> 00:00:58,057
problem, of course classically you might,
you might try probing every entry in turn

12
00:00:58,057 --> 00:01:05,062
and this would take you n steps.
But instead, you could do a little better

13
00:01:05,062 --> 00:01:11,043
if you probe random entries.
Well then, the expected amount of time

14
00:01:11,043 --> 00:01:18,054
before you hit the marked item, assuming
there's a single one, is n / two tries.

15
00:01:18,054 --> 00:01:26,078
So, the question we are, we are going to
be asking here is, is there a way of doing

16
00:01:26,078 --> 00:01:34,002
this, solving this problem, much faster
than this, using a quantum algorithm.

17
00:01:34,002 --> 00:01:37,065
Okay.
So, this is the image that we have in

18
00:01:37,065 --> 00:01:41,034
mind.
You know, that there's, that there's some

19
00:01:41,034 --> 00:01:47,031
way that you could look, you know,
instantly get into this haystack and find

20
00:01:47,031 --> 00:01:53,005
the, the hidden needle.
Okay so, before we do this we want to you

21
00:01:53,005 --> 00:01:58,087
know let's, let's try to understand what
the, what the relevance of, of this

22
00:01:58,087 --> 00:02:04,098
looking for a needle in a haystack is.
Well, it turns out that there are a lot

23
00:02:04,098 --> 00:02:10,008
computational problems.
In fact, a typical computational problem

24
00:02:10,008 --> 00:02:15,006
has this structure of looking for a needle
in a haystack.

25
00:02:15,006 --> 00:02:21,035
So, there is this whole class of problems
called NP-complete problems, and there are

26
00:02:21,035 --> 00:02:27,002
thousands of these, these kinds of
problems that, that have been that have

27
00:02:27,002 --> 00:02:33,024
been identified as being and proved as
being NP-complete but identified as being

28
00:02:33,024 --> 00:02:35,060
extremely important problems.
Okay.

29
00:02:35,060 --> 00:02:41,067
In fact, there was, there was, you know,
there was some compilation which said that

30
00:02:41,067 --> 00:02:46,050
over the last decade or two.
There have been, there have thousands of

31
00:02:46,050 --> 00:02:52,052
these problems that have been identified
in the physics and chemistry literature

32
00:02:52,052 --> 00:02:56,035
alone.
So, what are these NP-complete problems?

33
00:02:56,035 --> 00:03:03,024
These are computational problems for which
finding the answer is difficult to this

34
00:03:03,024 --> 00:03:08,007
computational problem.
But once you have, once you've found it,

35
00:03:08,007 --> 00:03:12,030
it's easy to check that you found the
correct answer.

36
00:03:12,030 --> 00:03:17,040
So, here's the iconic example of an
NP-complete problem.

37
00:03:17,040 --> 00:03:25,001
It's called satisfiability.
So, You're given a Boolean formula over n

38
00:03:25,001 --> 00:03:30,078
Boolean variables.
So, it's a formula which says either x1

39
00:03:30,078 --> 00:03:34,045
or, is true, or x2 is false, or x3 is
true.

40
00:03:34,045 --> 00:03:39,007
And, x2 is true or x5 is false, or x6 is
true, and so on.

41
00:03:39,007 --> 00:03:42,090
You know, there are a number of clauses of
this kind.

42
00:03:42,090 --> 00:03:47,072
You have, n such variables.
And you want to know, is there an

43
00:03:47,072 --> 00:03:54,040
assignment of true and false to, to your n
variables which makes this formula

44
00:03:54,040 --> 00:04:02,056
evaluate to true.
Which makes every clause evaluate to true.

45
00:04:02,056 --> 00:04:06,052
So.
So, notice that there are two properties

46
00:04:06,052 --> 00:04:11,090
of, of this kind of a problem.
First is that, the first is that the

47
00:04:11,090 --> 00:04:15,061
number of possible answers is very, very
large.

48
00:04:15,061 --> 00:04:20,043
It grows exponentially in the number of
variables.

49
00:04:20,043 --> 00:04:26,024
So, it grows like two^n.
Because each variable can be assigned

50
00:04:26,024 --> 00:04:30,049
either true or false.
The second property is that.

51
00:04:30,049 --> 00:04:36,014
Once you actually find a solution.
So, if you find an assignment that

52
00:04:36,014 --> 00:04:43,016
satisfies every clause, then it's easy to
check that you have indeed found the, the

53
00:04:43,016 --> 00:04:47,049
answer.
And so in this sense, solving this problem

54
00:04:47,049 --> 00:04:56,022
is like finding a needle in a haystack.
Okay, but how does the, how does the

55
00:04:56,022 --> 00:05:03,065
satisfiability problem correspond to this
searching of the, of the digital haystack

56
00:05:03,065 --> 00:05:10,076
or of this unstructured search problem?
So, well, let N be two^n.

57
00:05:10,076 --> 00:05:20,096
So, that two^n possible truth assignments
that you can make to, to your n Boolean

58
00:05:20,096 --> 00:05:26,021
variables.
So, think of, think of each entry of this,

59
00:05:26,021 --> 00:05:33,061
of this table as corresponding to a
particular truth assignment x.

60
00:05:33,061 --> 00:05:42,083
Okay, and now mark each entry, let, let,
let the, let the contents of each entry

61
00:05:42,083 --> 00:05:50,061
be, either that the, that the assignment
is a satisfying assignment, or that it's

62
00:05:50,061 --> 00:05:56,007
not a satisfying assignment.
So, now the kind of question we are, we

63
00:05:56,007 --> 00:06:01,002
are asking is.
Well, the marked items correspond to those

64
00:06:01,002 --> 00:06:05,000
assignments which satisfy this Boolean
formula.

65
00:06:05,000 --> 00:06:09,000
And what we are looking for is one such
assignment.

66
00:06:09,000 --> 00:06:14,000
So we are looking for a marked entry in
this digital haystack.

67
00:06:14,000 --> 00:06:19,000
Okay, so, how would you go about trying to
solve this quantumly?

68
00:06:19,000 --> 00:06:25,005
Well, here's a tempting thing.
Why not try to use this, the fact that you

69
00:06:25,005 --> 00:06:32,082
have an exponential super position to
probe all these two^n entries in parallel.

70
00:06:32,082 --> 00:06:36,061
In different quantum universes so to
speak.

71
00:06:36,061 --> 00:06:46,008
So, in other words, we all know that, that
we could, we could take n qubits, you know

72
00:06:46,008 --> 00:06:55,050
n qubits where two^n = N and we could put
them in the, in an equal superposition

73
00:06:55,050 --> 00:07:02,006
over all n-bit strings.
So, you know, all numbers between zero and

74
00:07:02,006 --> 00:07:07,035
N-1.
So we, we, we start in this, you know, we,

75
00:07:07,035 --> 00:07:15,001
we could use a Hadamard transform.
And create this superposition, sum over

76
00:07:15,001 --> 00:07:21,003
all y.
Y= zero to N-1 of one / square root N, Y.

77
00:07:21,003 --> 00:07:29,005
And now, we go ahead and, and probe the
yth entry of our, of our table.

78
00:07:29,005 --> 00:07:35,053
If you want, re, remember what, what,
what, what this digital haystack

79
00:07:35,053 --> 00:07:40,070
corresponded to.
So, so let's, let's write it down here,

80
00:07:40,070 --> 00:07:45,074
so.
Remember, we had some, some Boolean

81
00:07:45,074 --> 00:07:52,064
formula f(x).
We're thinking of x as, as x1, x2 through

82
00:07:52,064 --> 00:07:59,083
xn.
As N and this and f(x) with some Boolean

83
00:07:59,083 --> 00:08:10,009
formula which, which was say x1 or x2 bar
or x3 and so on and so on and so on.

84
00:08:12,008 --> 00:08:19,042
Okay, so it's in and of a bunch of clauses
and we think of f(x) as being either zero

85
00:08:19,042 --> 00:08:23,000
or one.
And so now we, what we would do is, we

86
00:08:23,000 --> 00:08:27,000
just feed this into some circuit, which
computes f.

87
00:08:28,005 --> 00:08:38,001
And our output would be of course, of
course, is a superposition over all y of y

88
00:08:38,001 --> 00:08:41,007
f(y).
Right, and now.

89
00:08:41,007 --> 00:08:48,008
Okay, looks like we've computed f in super
position and now, could we reach and then

90
00:08:48,008 --> 00:08:55,008
and pick out a satisfying assignment, a y
such that f(y) =one.

91
00:08:55,008 --> 00:08:59,009
But think about it.
That's not how quantum mechanics works,

92
00:08:59,009 --> 00:09:02,005
right?
Remember, we have our rules of

93
00:09:02,005 --> 00:09:05,042
measurement.
So, if we do a measurement, so what

94
00:09:05,042 --> 00:09:10,063
happens if we measure?
What happens is, what's the chance we see

95
00:09:10,063 --> 00:09:13,068
f(y) = one.
Well, remember our rules of measurement.

96
00:09:13,068 --> 00:09:16,093
It's the same as though we measured
everything.

97
00:09:16,093 --> 00:09:24,002
We measured all our inputs, all, you know
all our qubits and then it's a chance that

98
00:09:24,002 --> 00:09:29,049
f(y) = one if we measure all the qubits.
But what happens if we measure all the

99
00:09:29,049 --> 00:09:32,024
qubits?
Well, when we measure all the qubits, we

100
00:09:32,024 --> 00:09:38,024
see a random, a uniformly random y.
So, we each see each y with probability

101
00:09:38,024 --> 00:09:42,051
one / two^n.
And so, the chance we see f(y) = one is

102
00:09:42,051 --> 00:09:49,069
exactly the same as the chance we, that,
that we, we a, we find this satisfying

103
00:09:49,069 --> 00:09:54,008
assignment if we probe the random entry of
the table.

104
00:09:54,008 --> 00:10:00,056
Now, the chance of we see, see a marked
item if we probe the random entry of the

105
00:10:00,056 --> 00:10:04,034
table.
So, so unfortunately, this way of doing

106
00:10:04,034 --> 00:10:18,005
things is no better than probing a random,
a random entry of the table.

107
00:10:20,002 --> 00:10:28,000
Okay, so remember what, what give quantum
algorithms all its power was not just the

108
00:10:28,000 --> 00:10:35,005
fact that we could get a superposition
that, that, you know, that was spread over

109
00:10:35,005 --> 00:10:42,006
two^n different choices.
That's not yet enough because we can do

110
00:10:42,006 --> 00:10:49,006
something like that probabilistically.
So, if we pick a random entry if, if you

111
00:10:49,006 --> 00:10:54,004
sample uniformly.
We could think of that as, having a

112
00:10:54,004 --> 00:10:58,068
probability.
A probability spread out uniformly over

113
00:10:58,068 --> 00:11:03,007
all, and, you know, all these
exponentially many choices.

114
00:11:03,007 --> 00:11:09,006
What makes quantum computing unique, what,
what gives it its power is not only the

115
00:11:09,006 --> 00:11:13,009
ability to do that.
But also then later to get constructive

116
00:11:13,009 --> 00:11:18,003
and destructive interference.
So, we want to get constructive

117
00:11:18,003 --> 00:11:24,002
interference only at, at those strings
which correspond to answers to the problem

118
00:11:24,002 --> 00:11:29,004
that we are trying to solve.
Okay, so this is, this is what we're

119
00:11:29,004 --> 00:11:34,007
really trying to do next.
So, what we want to know is, can we

120
00:11:34,007 --> 00:11:41,008
actually come up with a better kind of
algorithm, much, you know, an algorithm

121
00:11:41,008 --> 00:11:46,077
that, that, that quantumly somehow probes
this digital haystack.

122
00:11:46,077 --> 00:11:57,007
In time, which, which grows not like N /
two, as in the, in the, in the, in the

123
00:11:57,007 --> 00:12:04,074
classical case.
But, but like log of N or [inaudible] in

124
00:12:04,074 --> 00:12:05,053
n.
Right?

125
00:12:05,053 --> 00:12:09,046
That would be, that would be the ultimate
goal.

126
00:12:09,046 --> 00:12:12,044
Unfortunately, there's a theorem.
Okay.

127
00:12:12,044 --> 00:12:17,051
That, that we can prove.
Which says that any quantum algorithm to

128
00:12:17,051 --> 00:12:24,014
solve this problem of finding a needle in
a digital haystack must take at least

129
00:12:24,014 --> 00:12:31,007
square root of N time.
Where square root of N is now two^n / two.

130
00:12:31,008 --> 00:12:38,000
So, it's exponential times two, even
though that it, you know, this, this is,

131
00:12:38,000 --> 00:12:41,082
okay.
So, so, you know, two^n / two is still

132
00:12:41,082 --> 00:12:47,008
exponential in little n.
So this is something that we actually

133
00:12:47,008 --> 00:12:53,003
proved way back in 1994.
Around the same time as Shor's factoring

134
00:12:53,003 --> 00:12:56,002
algorithm.
So, given this theorem.

135
00:12:56,002 --> 00:13:02,001
Which, which says that there's, there's
really not much, you know, that, that you

136
00:13:02,001 --> 00:13:08,002
cannot get an exponential speed-up for
searching for a needle in a haystack, and

137
00:13:08,002 --> 00:13:13,005
to the extent that the NP-complete
problems are really well modeled by

138
00:13:13,005 --> 00:13:19,003
digital haystacks that you cannot get an
exponential speedup for NP-complete

139
00:13:19,003 --> 00:13:23,000
problems.
Then Shor's algorithm for factoring was

140
00:13:23,000 --> 00:13:28,007
somehow the best we could have hoped for.
So, it came as a really pleasant, an

141
00:13:28,007 --> 00:13:34,001
unexpected pleasant surprise that quantum
algorithms were this powerful.

142
00:13:34,001 --> 00:13:37,007
This was, this was really a remarkable
discovery.

143
00:13:38,008 --> 00:13:47,008
Okay, a couple of years later there was
this beautiful iris that was discovered by

144
00:13:47,008 --> 00:13:56,003
Grover which, which showed that in fact.
You could get this quadratic speed-up.

145
00:13:56,003 --> 00:14:01,051
So, you can't get an exponential speed-up
for unstructured search.

146
00:14:01,051 --> 00:14:07,007
But you can get a quadratic speed-up over
the best classical algorithm.

147
00:14:07,007 --> 00:14:12,008
And you can solve this problem in the
square root of N steps.

148
00:14:12,008 --> 00:14:17,005
So, let's, you know, let's again be clear
about the problem we are solving.

149
00:14:17,005 --> 00:14:22,022
So, if the problem is, we are given a
function from zero, one through, zero,

150
00:14:22,024 --> 00:14:25,062
from a domain of size capital N to zero,
one.

151
00:14:25,062 --> 00:14:29,090
And the challenge is to find an x such
that f(x) = one.

152
00:14:29,090 --> 00:14:35,015
The hardest case, of course, is when
there's exactly one needle.

153
00:14:35,015 --> 00:14:41,043
So, you're looking for you know, there,
there's exactly one x such that f(x) = one

154
00:14:41,043 --> 00:14:47,005
and you're looking for that one.
Okay.

155
00:14:47,005 --> 00:14:55,001
So, so once again, the way to think about
this, this, this, this problem is you're

156
00:14:55,001 --> 00:15:01,008
given a program for, for computing f.
So, you're given some, some circuit.

157
00:15:02,003 --> 00:15:11,009
C sub f, which takes as input.
N bits, and outputs a single bit f(x).

158
00:15:11,009 --> 00:15:20,008
So, it takes as input x, outputs f(x).
And equivalently, of course, you can, you

159
00:15:20,008 --> 00:15:27,002
can transform this.
Into a quantum circuit, U sub f.

160
00:15:27,002 --> 00:15:37,037
Which takes us and put x output x.
It takes a input x and zero, and outputs x

161
00:15:37,037 --> 00:15:46,035
and f(x) Or if you want, you can, you can
actually let the input, you know, you can,

162
00:15:46,035 --> 00:15:52,047
you can say it more generally, and if this
answer bit initially was B, then your

163
00:15:52,047 --> 00:15:58,074
output bit as B exclusive or f(x).
So, it toggles the bit if and only if f(x)

164
00:15:58,074 --> 00:16:02,030
= one.
What we're assuming here is that you

165
00:16:02,030 --> 00:16:07,074
cannot look inside the circuit.
The circuit is given to you as a black

166
00:16:07,074 --> 00:16:10,094
box.
And you cannot look inside this quantum

167
00:16:10,094 --> 00:16:15,025
circuit, either.
So, all you can do is give it an input and

168
00:16:15,025 --> 00:16:20,007
see what the output is.
Of course in the quantum case, you can not

169
00:16:20,007 --> 00:16:26,089
only give it an input x, but you can also
give it an input sum over all x.

170
00:16:26,089 --> 00:16:34,057
So superposition of all x.
And then your output is a superposition.

171
00:16:34,057 --> 00:16:39,025
The same superposition over all x, of x,
f(x).

172
00:16:39,025 --> 00:16:47,068
Okay, so in the next video we'll see how,
how to actually get this quadratic speed

173
00:16:47,068 --> 00:16:50,009
up for this search problem.