Okay.
So, here's our picture.
Here was a state sign, this was a test
run.
And then for each step, a state most, but
utmost one over square root N.
Okay.
But now, how much can it move as a result
of t such steps, at most t over square
root of N?
Okay?
But now when you make a measurement, how
much effect can this have, on the actual
probability of, of, of seeing something.
So the, the probability changes by the
square of this, order of the square of
this, which is order t square over N.
And that's the maximum it can change.
So the worst that can happen to us is that
all these little changes in each step line
up, to get constructive interference, and
when you get constructive interference,
you get, this t square term show up, and
that's because its constructive.
And so, what Grover's algorithm manages to
do is it manages to make these terms line
up.
So, if you want to understand it, go back
and look at Grover's algorithm, and you
will see in what sense these, these
changes line up and you get constructed
interference, and so you get exactly this
effect.
So, this effect showed that you could do
no better and Grover managed to find a,
find a method of actually matching this
lower bound.
Okay.
So, now let's, you know let's try to
understand what we, what we just saw
before where we said that no quantum, no
quantum algorithm can solve this search
problem in with better than quadratic
speed up.
We also saw in the last lecture that.
How this search problem corresponds to
solving an NP complete problem, because
the entries of the table, well there, they
could correspond to different possible
assignments to the truth values or for
satisfiability formula.
And they, so those are the indices of the,
you know of the entries and the entries
themselves just say whether it is a
satisfying assignment or not a satisfying
assignment.
And so, if you're looking for a satisfying
assignment, and we think of it as a marked
entry, then, then the search problem
corresponds to solving the, solving
satisfiability or NP complete problem.
So, how do you show them that quantum
computers cannot solve NP-complete
problems at polynomial time?
Well the answer is no.
We, we, we've shown, we haven't shown that
because what we've, what, what we've shown
is that if we can think of our, our
problem as a black box problem.
So if you're, if you're saying that we
don't understand anything about the
structure of the satisfiability problem.
So we can't just look at the formula and,
and you know, syntactically based on what
the formula look, looks like we, you know
maybe we, maybe there's a fast algorithm
that decides whether it's satisfiable or
not.
So what this has really noticed that
there's no way to actually evaluate the
formula in super position without
understanding what the formula means in
solving it quickly.
In other words, to do any better you have
to understand the structure of the
problem.
What makes this so difficult is that
people have been trying to understand the
structure of NP-complete problems for
several decades and we don't know, we
don't know how, how that works.
We, we haven't found much non-trivial
structure to work with.
About ten years ago there was a beautiful
paper by Eddie Farhi and his collaborators
at MIT where they gave, where they
proposed an algorithm for solving
satisfiability.
The, this, this is the so-called adiabatic
quantum optimization framework.
And they were unable to analyze this
algorithm, but they ran simulations on
small instances, you know of, you know
size n equal to ten or fifteen.
And what they found very exciting is that
these simulations were consistent with
polynomial time solutions.
So, here's a, here's a pointer to that,
paper you know, you should, you should,
it's, it's, worth chasing up and, and
reading.
Okay, and then, a few years later there
was a company that was launched.
It was called D-Wave Systems.
It's, it's in, Canada and Vancouver, you
know, it implemented this, this algorithm.
In fact, you know the, the company, the
company's, launching its demonstrations
were met with, with a, with a lot of
enthusiasm from the media including the
economist which, which, in an unrestrained
way, talked about how the first practical
quantum computer had been unveiled.
It talked about how you know, British
Columbia was going to become the new
Silicon Valley, and well, there was, there
was a, you know their economist article
was of course extremely over enthusiastic
so let me, you know, I'll try to put it in
perspective but it was talking about how,
how quantum computers provide this neat
short cut to solving NP-complete problems
by putting qubits in a super position of
zero and one.
But then they made this mistake.
Remember how in the last lecture we talked
about how you can't just put your qubits
in super position complete the function
and hope to find the marked elements
because.
By the rules of measurement you won't see,
you'll, the chance you'll see the marked
element is exactly the chance, you would
see if you, if you ran a problemalisitc
algorithm.
Okay.
So, so the, the economist, fell into this
trap of making this mistake.
But okay, so, so let me say a little bit,
two minutes about what adiabatic quantum
computing is.
So what you do is, is you designs some
Hamiltonian H which, which is easy to
implement.
And such that the ground state of this
Hamiltoninan H of final, is the output.
It's, it's the output to your, to the
problem that you're trying to solve.
But this is a, this is, of course, a
solution which is hard to find.
So you, you don't know how to find this
solution.
But you also design a easy Hamiltonian
whose ground state you already know.
And now, what you do is, you, you start in
this ground state of the known
Hamiltonian, the initial Hamiltonian.
And you gradually transform the
Hamiltonian from H naught to HF.
By taking a linear convex combination of
the two.
What the adiabatic theorem says is that,
if you do this slowly enough, then you'll
drag the ground state from this known
ground state psi naught, to this target
ground state, psi sub f.
So, if you do this slowly enough.
But how slowly?
Well, how fast you can go is one over the
square of the gap.
The gap between the ground energy and the
first excited energy.
So if, if enaught equal to the ground.
Energy.
And E one is the first excited state's
energy.
Then the gap is E1 minus E naught.
And so, how fast you can go depends upon
the smallest gap during this
transformation.
Okay.
So, here's an example that shows you how
to, how to, how to encode three sat as a
local Hamiltonian problem.
How to write out the Hamiltonian, H sub F,
so that its ground state is, a solution to
this, to this to this to this
satisfiability problem.
In fact, what we are going to write, is,
we are going to H sub F as H1 + H2 +H sub
N.
So, there is going to be a term of the
Hamiltonian for each clause here.
Sorry, this is going to be a little fast
for most of you.
But, I'm just giving you sort of a
perspective for those who can follow this.
Okay, so the n bits get transformed to n
qubits.
The clause x1 or x2 or x3 corresponds to
an eight by eight Hamiltonian matrix,
which is acting on the first three qubits.
It assigns a penalty of one.
If the clause is not satisfied, so the
only way to not satisfy the clause is if
x1 = x2 = x3 = zero.
So, you put a one in this lower left
corner there, and then 0's everywhere so,
its going to be a diagonal matrix with a
penalty of one corresponding to this truth
assignment where the, the only assignment
that does not satisfy this clause.
And now what you can check is that the
satisfying assignment for this formula
correspond to an eigenvector of this
Hamiltonian with eigen value zero.
And all other truth assignment are, are
eigenvectors with eigenvalue equal to the
number of unsatisfied clauses.
So the ground energy is exactly the, the
ground state is exactly a satisfying
assignment to the, to the formula.
Okay remember we, how fast we can go
depends upon the minimum gap.
It turns out that there are, you know,
there are few things that are known about
this, this problem, so there It's known
that the adiabatic optimiziation can be,
can be used in the certain way to give
quadratic speed of research.
But that, in general, takes exponential
time.
It, it can also be, it's, it's also been
shown that it, it generally takes
exponential time for NP-complete problems
but that if you set up the problem in
certain contrite ways, then you can tunnel
through local optima.
And then there's this paper that shows
that using arguments, you know?
Using arguments from Anderson
localization, it shows that, the algorithm
typically gets stuck in local optima.
So what does all this say about this
endeavor to build quantum optimization,
adiabatic optimization, and the deviate
computer?
Well, the consensus of the, the research
community right now is that, is that, It's
unlikely that this algorithm will work
well for any interesting problems that
will give us a speed of interesting
problems.
However, there are reasons that David try
to implement this.
And the reasons have to do with the fact
that it is actualy easier to implement
then general quantum computing.
And so, it's a long shot.
It's a very long shot.
But somebody should be doing it.
So its very unlikely to succeed.
But, but, on the other hand, maybe, you
know, given that it is so hard to analyze,
adiabatic quantum optimization, in
general.
Even though the indications are that it's
not going to give a speed up for typical
problems.
It's worth trying to implement it and
check that on the off chance it actually
gives a speed up for certain kinds of