Hi, everyone.
This is the last lecture for this class
and what I wanted to do in this last
lecture is give you an overview about
quantum complexity theory.
So you know one lecture's obviously not
sufficient to do justice to this subject.
And so, in parts the lecture is going to
be very, you know its going to be very
sketchy.
I'll, I'll sort of sketch for you a
picture of the subject at a high level.
And I don't really expect you to follow
all of it or even much of it but, you
know, if, if you get a, if you get a sense
of what the subject is about and whether
you are interested in it, I'll feel
that's, that's a successful lecture.
Okay, so, so try to follow as much as you
can and if you can't, you know well, you
can skip, skip past most of this, or you
know, just get a sense of what's, what's,
what the subject is about.
Okay, so in the first part of this, in the
first video, I'm going to talk about the
lower band for quantum search, and what it
tells us about quantum algorithms for any
incomplete problems.
Okay so remember what the, what, what the
search problem was, the, the unstructured
search problem.
So we think about having, you know we, we
are looking for a needle in a, in a hay
stack or digital needle in a digital hay
stack.
So, so a digital hay stack is a, is a
table with the with the capital N equal to
two to the little n entries.
And one of these entries is marked and,
and, so this is the proverbial needle, and
we are searching for this entry.
So we, we said that there's a theorem that
last, in the last lecture that any quantum
algorithm must take at least square root
of n time.
Actually what we meant by square root n
time is, it must make at least square root
of capital N queries to this table.
And since square root of capital N is two
to the little n over two.
This is exponential time in the length of
the input.
So let me, let me again say, what, what
our, you know what our setting is.
We think of this table as being specified
by some, some circuit.
So, some circuit that computes some
function f, so that when input x, it
outputs f(x), which is either zero or one,
so it's a Boolean function.
And f(x) equal to one says that x is a
marked element, and zero says it's
unmarked.
So, the length of the input x, x is an n
bit string.
So the length of x is n bits.
And so the, the running time, the number
of queries is exponential in the, in the
length of x.
Okay, so, how do we prove such a theorem?
So first let's, let's show that using one
quantum query, there's, there's no, no
quantum algorithm that can guarantee a
success probability larger than some
constant over N.
Probably four over N.
So, here's how, here's how we, we argue
this.
So, let's perform a test, test run with an
empty haystack.
By this I mean, that there's no marked
element in this, in this haystack.
Okay?
No marked element in this table.
And now, suppose that the algorithm makes
this query.
Sum over all x, alpha xx.
Now remember, for this to be normalized,
the sum of alpha x magnitude squared must
be equal to one.
So there are some alpha.
So there is, there is some x, such that
alpha sub x squared is less than or equal
to one over n.
Right?
Just by averaging.
In fact if we, if we pick a typical X it
has this property.
Okay so now what we do is, mark that
element, so we mark that x for which alpha
x magnitude squared is small as possible.
So now, when we make this query, when the,
you know, the algorithm doesn't know
where, where the marked element is so, so
it of course, once we put the marked
element there, it still makes the same
query.
And so it queries the marked element with
amplitude, you know, with amplitude so the
amplitude with which it, it varies this,
this, this particular element.
Let's call it X star.
You know, the, the, the magnitude of the
amplitude is at most one over square root
of N.
Okay.
And so now, what we are, what we're going
to argue is that the final state of the
algorithm, if you look at the quantum
state of the algorithm.
You know, so if you have the quantum
algorithm, you, you look at the final, the
final state psi which you are now going to
measure.
Well, psi was something you know psi had
some value when, when we performed the
test run.
And now what we're saying is psi cannot be
changed by very much.
You know when we, when we actually run it
on the table with a, with a marked
element, it can change by utmost one over
square root of N in euclidean distance.
And so, what that implies if you work
through it, is that, is that the chance
that your measurement outputs, a different
value than it did in the case of the
empty, empty haystack or the new marked
element.
Is, is very small.
It's, it's smaller than constant over n.
It's smaller than some constant times
this, the square of this value.
Okay, and that shows that one quantum
query cannot possibly help.
So now, what we'd like to do is, we'd like
to generalize this, this, this particular
argument to many steps.
So suppose, suppose our algorithm now
makes, so our quantum algorithm makes t
steps, for sum t.
Now, how does, how does the success
probability of the algorithm vary?
You know, how, how does it increase as T
increases?
So, what we are actually going to show, is
that the probability of success is going
to, is going to grow only as T squared
over N.
And this is why, if you want any
significant success probability you'll
have to use T to be about square root of
N.
Okay, now the, the argument for doing this
is very similar to what we did, in the in
the previous case where we, where we had
only one, query.
So what we're going to do is perform the
test run with the empty haystacks so no
marked element.
So run, you know whatever algorithm we,
we, w have, We are going to show there is
some, some marked element.
Such that if, if, you know some location
so that the marked element is there, then
this algorithm is going to do badly.
It's, it's going to succeed with
probability at most or the t square of N.
So what do we do?
We do the test run with empty tester, with
no marked element.
Now, we find that element which is queried
the, with the minimum squared amplitude.
So, we, we look in every step and we see
with what squared amplitude does, does the
location x get queried over all these T
steps?
And I find that X for which this, this is,
is minimized.
And now we put the, you know we call that
particular x, x star and we make that the
marked element.
And now what we'd like to do is we'd like
to show that, in fact, if we, if we now
run our algorithm on this, on this
particular table, with this particular
marked element, then the quantum algorithm
is unable to distinguish this from the
empty haystack, case.
Except with very small amplitude.
So the final state of the algorithm is
almost indistinguishable from the case
where there was no marked element.
Now, the difficulty in doing all this is
that, is that the subsequent queries,
query amplitudes, change depending upon
previous answers.
So, so you know as, as the algorithm runs,
it doesn't make, you know its, its
subsequent queries do not act as the same
way that they did.
The, the queries don't look, look like
what they did, when we did the test run.
They now diverge more and more, and in
fact one might even suspect that they
diverge exponentially.
So, so what we have to do is show that
the, the queries, you know somehow the,
the run cannot diverge very much.
Okay so, so I don't want to spend too much
time on this argument but I'll just give
you the gist of it.
So this is what's called the hybrid
argument.
It's probe by what's called the hybrid
argument.
Which is one of the very basic arguments,
you know ways of, of pounding, running
times of quantum algorithms.
So, the first thing we do is we spread out
the quantum circuit.
So, so that only one gate is being applied
at a time.
Now, of course you know, in the quantum
circuit maybe there many gates acting in
parallel, but then we can always delay
some of the gates.
So if there five gates acting in parallel,
we could just have one of them act, act
first and then the second one and then the
third one and it makes no difference to
their actual workings of the quantum
circuit, it only delays the output, you
know it makes it run slower.
So, but we don't care, we have plenty of
time.
So, here's our quantum circuit.
It, it applies some unitary U1 and then
some unitary U2, U3.
U sub T.
But now, there's one other aspect that we,
we, we really must, fix which is, is this
a test run or is this, is this the real
run of the algorithm?
So, so let's say that we say that we have
our function F which is identically zero,
so this was our test run.
And then we use this to identify a
function F prime such that F prime of X
star equal to one, and it's zero
everywhere else.
So, this was our real run of the
algorithm.
Okay.
So, so let's, let's say up here we have
the test run.
So, this is, so whenever it calls in
Oracle, whenever it calls F, so that's,
that's the test run.
And then down here, we have, we have the
real run of the algorithm.
Whenever we make a query, we make a query
to F prime.
And what we'd like to do is we'd like to
say that, that, the output here, the
output state here, psi prime is very close
to the output state here, psi.
These two are not very far from each
other.
And so the way we'll do this is we are
going to modify the test run into the,
into the actual run one step at a time.
So what I mean by this is that we'll do a,
a run where everything is like the,
everything looks like the test run.
Okay?
Except for the last step is done, as
though we were doing the real one at the
algorithm, okay?
So now what we want to do is we want to
say, how different is, this outputs psi
one from psi?
And the answer is, well, it's very much
like, you know so well, there's only one
query that's changed between, between,
between these two runs.
But we know how to analyze one query.
All it does is it changes the output state
by roughly one over square root N.
So, so in other words, what it did was, if
this was the output state psi.
Then, then what it did was it changed it
to some new state which is roughly one
over square root N of a from the, from the
old one.
In some direction we don't know, we don't
know in which direction the change is, but
it's, it's at most one over square root of
N.
So, now we repeat this process.
And we do one more run which still looks
almost like the test run.
Except, now the last two steps look like
the real run of the algorithm.
So we make queries to F prime.
Okay.
So now, how different is this output psi
two from psi?
Well, in order to analyze that, let's just
understand how differences psi two from
psi one.
Well, the only difference between these
two, of course lies in one step.
Okay so we know what, how different the
output of this one step is in these two
cases at most one over square root N.
But this is not the last step of the
algorithm.
For surely this is a different situation.
So, so we can say that before the last
step of the algorithm, the, the, the, the
input to the last step of the algorithm in
these two cases differs by at most one
over square root N.
The, the input vectors in the two cases
differ by at most one over square root N.
But now remember there's, there's this
crucial fact about quantum computation,
which is quantum evolution is unitary,
meaning this last step, whatever it was,
it's the same in both cases.
We are applying the same unitary
transformation.
So if you give two inputs which, which
make a certain angle with each other, then
this last step is going to preserve that
angle.
So it's going to preserve the distance
between the two vectors.
So psi one and psi two are going to differ
by at most one over square root N.
Again, we don't know in which direction,
but we know that they can be at most one
over square root N apart.
So we proceed this way, making one change
at a time until we get back to the
original, you know the, the actual
circuit.
And we realize that, that we that, that
our state moves in t steps, the each step
changes the state by one over square root
N.