1
00:00:00,009 --> 00:00:03,040
Okay.
So, here's our picture.

2
00:00:03,040 --> 00:00:08,066
Here was a state sign, this was a test
run.

3
00:00:08,066 --> 00:00:31,009
And then for each step, a state most, but
utmost one over square root N.

4
00:00:37,008 --> 00:00:42,008
Okay.
But now, how much can it move as a result

5
00:00:42,008 --> 00:00:48,000
of t such steps, at most t over square
root of N?

6
00:00:48,000 --> 00:00:52,008
Okay?
But now when you make a measurement, how

7
00:00:52,008 --> 00:01:01,006
much effect can this have, on the actual
probability of, of, of seeing something.

8
00:01:01,006 --> 00:01:08,003
So the, the probability changes by the
square of this, order of the square of

9
00:01:08,003 --> 00:01:14,002
this, which is order t square over N.
And that's the maximum it can change.

10
00:01:14,002 --> 00:01:20,016
So the worst that can happen to us is that
all these little changes in each step line

11
00:01:20,016 --> 00:01:26,003
up, to get constructive interference, and
when you get constructive interference,

12
00:01:26,003 --> 00:01:31,019
you get, this t square term show up, and
that's because its constructive.

13
00:01:31,019 --> 00:01:36,083
And so, what Grover's algorithm manages to
do is it manages to make these terms line

14
00:01:36,083 --> 00:01:39,058
up.
So, if you want to understand it, go back

15
00:01:39,058 --> 00:01:44,041
and look at Grover's algorithm, and you
will see in what sense these, these

16
00:01:44,041 --> 00:01:50,045
changes line up and you get constructed
interference, and so you get exactly this

17
00:01:50,045 --> 00:01:53,057
effect.
So, this effect showed that you could do

18
00:01:53,057 --> 00:01:59,011
no better and Grover managed to find a,
find a method of actually matching this

19
00:01:59,011 --> 00:02:01,060
lower bound.
Okay.

20
00:02:01,060 --> 00:02:09,006
So, now let's, you know let's try to
understand what we, what we just saw

21
00:02:09,006 --> 00:02:17,057
before where we said that no quantum, no
quantum algorithm can solve this search

22
00:02:17,057 --> 00:02:23,019
problem in with better than quadratic
speed up.

23
00:02:23,019 --> 00:02:30,051
We also saw in the last lecture that.
How this search problem corresponds to

24
00:02:30,051 --> 00:02:35,090
solving an NP complete problem, because
the entries of the table, well there, they

25
00:02:35,090 --> 00:02:40,076
could correspond to different possible
assignments to the truth values or for

26
00:02:40,076 --> 00:02:45,018
satisfiability formula.
And they, so those are the indices of the,

27
00:02:45,018 --> 00:02:50,037
you know of the entries and the entries
themselves just say whether it is a

28
00:02:50,037 --> 00:02:53,062
satisfying assignment or not a satisfying
assignment.

29
00:02:53,062 --> 00:02:59,018
And so, if you're looking for a satisfying
assignment, and we think of it as a marked

30
00:02:59,018 --> 00:03:04,048
entry, then, then the search problem
corresponds to solving the, solving

31
00:03:04,048 --> 00:03:12,059
satisfiability or NP complete problem.
So, how do you show them that quantum

32
00:03:12,059 --> 00:03:17,006
computers cannot solve NP-complete
problems at polynomial time?

33
00:03:17,006 --> 00:03:21,082
Well the answer is no.
We, we, we've shown, we haven't shown that

34
00:03:21,082 --> 00:03:27,075
because what we've, what, what we've shown
is that if we can think of our, our

35
00:03:27,075 --> 00:03:32,008
problem as a black box problem.
So if you're, if you're saying that we

36
00:03:32,008 --> 00:03:36,053
don't understand anything about the
structure of the satisfiability problem.

37
00:03:36,053 --> 00:03:41,059
So we can't just look at the formula and,
and you know, syntactically based on what

38
00:03:41,059 --> 00:03:46,054
the formula look, looks like we, you know
maybe we, maybe there's a fast algorithm

39
00:03:46,054 --> 00:03:49,036
that decides whether it's satisfiable or
not.

40
00:03:49,036 --> 00:03:54,022
So what this has really noticed that
there's no way to actually evaluate the

41
00:03:54,022 --> 00:03:59,016
formula in super position without
understanding what the formula means in

42
00:03:59,016 --> 00:04:02,050
solving it quickly.
In other words, to do any better you have

43
00:04:02,050 --> 00:04:05,004
to understand the structure of the
problem.

44
00:04:05,004 --> 00:04:10,068
What makes this so difficult is that
people have been trying to understand the

45
00:04:10,068 --> 00:04:15,084
structure of NP-complete problems for
several decades and we don't know, we

46
00:04:15,084 --> 00:04:21,011
don't know how, how that works.
We, we haven't found much non-trivial

47
00:04:21,011 --> 00:04:26,047
structure to work with.
About ten years ago there was a beautiful

48
00:04:26,047 --> 00:04:32,089
paper by Eddie Farhi and his collaborators
at MIT where they gave, where they

49
00:04:32,089 --> 00:04:37,005
proposed an algorithm for solving
satisfiability.

50
00:04:37,008 --> 00:04:44,003
The, this, this is the so-called adiabatic
quantum optimization framework.

51
00:04:44,003 --> 00:04:51,000
And they were unable to analyze this
algorithm, but they ran simulations on

52
00:04:51,000 --> 00:04:57,001
small instances, you know of, you know
size n equal to ten or fifteen.

53
00:04:57,004 --> 00:05:05,062
And what they found very exciting is that
these simulations were consistent with

54
00:05:05,062 --> 00:05:10,066
polynomial time solutions.
So, here's a, here's a pointer to that,

55
00:05:10,066 --> 00:05:17,030
paper you know, you should, you should,
it's, it's, worth chasing up and, and

56
00:05:17,030 --> 00:05:22,041
reading.
Okay, and then, a few years later there

57
00:05:22,041 --> 00:05:28,045
was a company that was launched.
It was called D-Wave Systems.

58
00:05:28,045 --> 00:05:35,006
It's, it's in, Canada and Vancouver, you
know, it implemented this, this algorithm.

59
00:05:35,008 --> 00:05:41,027
In fact, you know the, the company, the
company's, launching its demonstrations

60
00:05:41,027 --> 00:05:47,028
were met with, with a, with a lot of
enthusiasm from the media including the

61
00:05:47,028 --> 00:05:53,097
economist which, which, in an unrestrained
way, talked about how the first practical

62
00:05:53,097 --> 00:06:00,004
quantum computer had been unveiled.
It talked about how you know, British

63
00:06:00,004 --> 00:06:06,060
Columbia was going to become the new
Silicon Valley, and well, there was, there

64
00:06:06,060 --> 00:06:13,020
was a, you know their economist article
was of course extremely over enthusiastic

65
00:06:13,020 --> 00:06:19,009
so let me, you know, I'll try to put it in
perspective but it was talking about how,

66
00:06:19,009 --> 00:06:24,008
how quantum computers provide this neat
short cut to solving NP-complete problems

67
00:06:24,008 --> 00:06:27,009
by putting qubits in a super position of
zero and one.

68
00:06:27,009 --> 00:06:32,003
But then they made this mistake.
Remember how in the last lecture we talked

69
00:06:32,003 --> 00:06:37,000
about how you can't just put your qubits
in super position complete the function

70
00:06:37,000 --> 00:06:39,006
and hope to find the marked elements
because.

71
00:06:39,006 --> 00:06:45,005
By the rules of measurement you won't see,
you'll, the chance you'll see the marked

72
00:06:45,005 --> 00:06:51,001
element is exactly the chance, you would
see if you, if you ran a problemalisitc

73
00:06:51,001 --> 00:06:52,001
algorithm.
Okay.

74
00:06:52,001 --> 00:06:56,009
So, so the, the economist, fell into this
trap of making this mistake.

75
00:06:56,009 --> 00:07:05,005
But okay, so, so let me say a little bit,
two minutes about what adiabatic quantum

76
00:07:05,005 --> 00:07:12,012
computing is.
So what you do is, is you designs some

77
00:07:12,012 --> 00:07:17,006
Hamiltonian H which, which is easy to
implement.

78
00:07:17,006 --> 00:07:24,000
And such that the ground state of this
Hamiltoninan H of final, is the output.

79
00:07:24,000 --> 00:07:29,004
It's, it's the output to your, to the
problem that you're trying to solve.

80
00:07:29,004 --> 00:07:33,007
But this is a, this is, of course, a
solution which is hard to find.

81
00:07:33,007 --> 00:07:36,009
So you, you don't know how to find this
solution.

82
00:07:36,009 --> 00:07:41,009
But you also design a easy Hamiltonian
whose ground state you already know.

83
00:07:41,009 --> 00:07:46,006
And now, what you do is, you, you start in
this ground state of the known

84
00:07:46,006 --> 00:07:51,001
Hamiltonian, the initial Hamiltonian.
And you gradually transform the

85
00:07:51,001 --> 00:07:58,000
Hamiltonian from H naught to HF.
By taking a linear convex combination of

86
00:07:58,000 --> 00:08:02,005
the two.
What the adiabatic theorem says is that,

87
00:08:02,005 --> 00:08:09,001
if you do this slowly enough, then you'll
drag the ground state from this known

88
00:08:09,001 --> 00:08:14,001
ground state psi naught, to this target
ground state, psi sub f.

89
00:08:14,001 --> 00:08:18,000
So, if you do this slowly enough.
But how slowly?

90
00:08:18,000 --> 00:08:23,000
Well, how fast you can go is one over the
square of the gap.

91
00:08:23,002 --> 00:08:28,006
The gap between the ground energy and the
first excited energy.

92
00:08:28,006 --> 00:08:33,003
So if, if enaught equal to the ground.
Energy.

93
00:08:33,007 --> 00:08:39,003
And E one is the first excited state's
energy.

94
00:08:39,003 --> 00:08:48,004
Then the gap is E1 minus E naught.
And so, how fast you can go depends upon

95
00:08:48,004 --> 00:08:53,008
the smallest gap during this
transformation.

96
00:08:54,005 --> 00:08:58,002
Okay.
So, here's an example that shows you how

97
00:08:58,002 --> 00:09:03,001
to, how to, how to encode three sat as a
local Hamiltonian problem.

98
00:09:03,001 --> 00:09:09,009
How to write out the Hamiltonian, H sub F,
so that its ground state is, a solution to

99
00:09:09,009 --> 00:09:14,009
this, to this to this to this
satisfiability problem.

100
00:09:14,009 --> 00:09:20,077
In fact, what we are going to write, is,
we are going to H sub F as H1 + H2 +H sub

101
00:09:20,077 --> 00:09:24,004
N.
So, there is going to be a term of the

102
00:09:24,004 --> 00:09:30,005
Hamiltonian for each clause here.
Sorry, this is going to be a little fast

103
00:09:30,005 --> 00:09:34,007
for most of you.
But, I'm just giving you sort of a

104
00:09:34,007 --> 00:09:41,009
perspective for those who can follow this.
Okay, so the n bits get transformed to n

105
00:09:41,009 --> 00:09:46,003
qubits.
The clause x1 or x2 or x3 corresponds to

106
00:09:46,003 --> 00:09:53,005
an eight by eight Hamiltonian matrix,
which is acting on the first three qubits.

107
00:09:53,005 --> 00:09:58,008
It assigns a penalty of one.
If the clause is not satisfied, so the

108
00:09:58,008 --> 00:10:01,099
only way to not satisfy the clause is if
x1 = x2 = x3 = zero.

109
00:10:02,000 --> 00:10:07,004
So, you put a one in this lower left
corner there, and then 0's everywhere so,

110
00:10:07,004 --> 00:10:13,004
its going to be a diagonal matrix with a
penalty of one corresponding to this truth

111
00:10:13,004 --> 00:10:18,008
assignment where the, the only assignment
that does not satisfy this clause.

112
00:10:18,008 --> 00:10:24,000
And now what you can check is that the
satisfying assignment for this formula

113
00:10:24,000 --> 00:10:28,008
correspond to an eigenvector of this
Hamiltonian with eigen value zero.

114
00:10:28,008 --> 00:10:34,029
And all other truth assignment are, are
eigenvectors with eigenvalue equal to the

115
00:10:34,029 --> 00:10:39,002
number of unsatisfied clauses.
So the ground energy is exactly the, the

116
00:10:39,002 --> 00:10:43,009
ground state is exactly a satisfying
assignment to the, to the formula.

117
00:10:45,002 --> 00:10:50,004
Okay remember we, how fast we can go
depends upon the minimum gap.

118
00:10:50,007 --> 00:10:57,001
It turns out that there are, you know,
there are few things that are known about

119
00:10:57,001 --> 00:11:03,007
this, this problem, so there It's known
that the adiabatic optimiziation can be,

120
00:11:03,007 --> 00:11:09,001
can be used in the certain way to give
quadratic speed of research.

121
00:11:09,001 --> 00:11:12,006
But that, in general, takes exponential
time.

122
00:11:14,006 --> 00:11:20,000
It, it can also be, it's, it's also been
shown that it, it generally takes

123
00:11:20,000 --> 00:11:25,009
exponential time for NP-complete problems
but that if you set up the problem in

124
00:11:25,009 --> 00:11:30,005
certain contrite ways, then you can tunnel
through local optima.

125
00:11:31,005 --> 00:11:37,029
And then there's this paper that shows
that using arguments, you know?

126
00:11:37,029 --> 00:11:43,017
Using arguments from Anderson
localization, it shows that, the algorithm

127
00:11:43,017 --> 00:11:48,095
typically gets stuck in local optima.
So what does all this say about this

128
00:11:48,095 --> 00:11:55,030
endeavor to build quantum optimization,
adiabatic optimization, and the deviate

129
00:11:55,030 --> 00:11:59,046
computer?
Well, the consensus of the, the research

130
00:11:59,046 --> 00:12:06,026
community right now is that, is that, It's
unlikely that this algorithm will work

131
00:12:06,026 --> 00:12:11,044
well for any interesting problems that
will give us a speed of interesting

132
00:12:11,044 --> 00:12:14,085
problems.
However, there are reasons that David try

133
00:12:14,085 --> 00:12:19,013
to implement this.
And the reasons have to do with the fact

134
00:12:19,013 --> 00:12:24,027
that it is actualy easier to implement
then general quantum computing.

135
00:12:24,027 --> 00:12:27,063
And so, it's a long shot.
It's a very long shot.

136
00:12:27,063 --> 00:12:31,093
But somebody should be doing it.
So its very unlikely to succeed.

137
00:12:31,093 --> 00:12:37,036
But, but, on the other hand, maybe, you
know, given that it is so hard to analyze,

138
00:12:37,036 --> 00:12:40,070
adiabatic quantum optimization, in
general.

139
00:12:40,070 --> 00:12:46,052
Even though the indications are that it's
not going to give a speed up for typical

140
00:12:46,052 --> 00:12:49,094
problems.
It's worth trying to implement it and

141
00:12:49,094 --> 00:12:55,049
check that on the off chance it actually
gives a speed up for certain kinds of