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.