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