Hello everyone. So, in this lecture we'll talk about
unstructured quantum search or what's called Grover's algorithm for database
search. So, the problem we are trying to solve is
one of looking for a needle in a haystack. Of course, in this case, we, our haystack
and needle are digital. So, what does a digital haystack look
like. So, think of you this way.
You're given a table with, with n entries, and one of these entries is marked.
So, there is, there is a particular entry. If you, if you look inside this entry
you'll know, you'll know this is the entry you are looking for and your goal is to
find this, this special marked entry. Now, how can you try to solve this
problem, of course classically you might, you might try probing every entry in turn
and this would take you n steps. But instead, you could do a little better
if you probe random entries. Well then, the expected amount of time
before you hit the marked item, assuming there's a single one, is n / two tries.
So, the question we are, we are going to be asking here is, is there a way of doing
this, solving this problem, much faster than this, using a quantum algorithm.
Okay. So, this is the image that we have in
mind. You know, that there's, that there's some
way that you could look, you know, instantly get into this haystack and find
the, the hidden needle. Okay so, before we do this we want to you
know let's, let's try to understand what the, what the relevance of, of this
looking for a needle in a haystack is. Well, it turns out that there are a lot
computational problems. In fact, a typical computational problem
has this structure of looking for a needle in a haystack.
So, there is this whole class of problems called NP-complete problems, and there are
thousands of these, these kinds of problems that, that have been that have
been identified as being and proved as being NP-complete but identified as being
extremely important problems. Okay.
In fact, there was, there was, you know, there was some compilation which said that
over the last decade or two. There have been, there have thousands of
these problems that have been identified in the physics and chemistry literature
alone. So, what are these NP-complete problems?
These are computational problems for which finding the answer is difficult to this
computational problem. But once you have, once you've found it,
it's easy to check that you found the correct answer.
So, here's the iconic example of an NP-complete problem.
It's called satisfiability. So, You're given a Boolean formula over n
Boolean variables. So, it's a formula which says either x1
or, is true, or x2 is false, or x3 is true.
And, x2 is true or x5 is false, or x6 is true, and so on.
You know, there are a number of clauses of this kind.
You have, n such variables. And you want to know, is there an
assignment of true and false to, to your n variables which makes this formula
evaluate to true. Which makes every clause evaluate to true.
So. So, notice that there are two properties
of, of this kind of a problem. First is that, the first is that the
number of possible answers is very, very large.
It grows exponentially in the number of variables.
So, it grows like two^n. Because each variable can be assigned
either true or false. The second property is that.
Once you actually find a solution. So, if you find an assignment that
satisfies every clause, then it's easy to check that you have indeed found the, the
answer. And so in this sense, solving this problem
is like finding a needle in a haystack. Okay, but how does the, how does the
satisfiability problem correspond to this searching of the, of the digital haystack
or of this unstructured search problem? So, well, let N be two^n.
So, that two^n possible truth assignments that you can make to, to your n Boolean
variables. So, think of, think of each entry of this,
of this table as corresponding to a particular truth assignment x.
Okay, and now mark each entry, let, let, let the, let the contents of each entry
be, either that the, that the assignment is a satisfying assignment, or that it's
not a satisfying assignment. So, now the kind of question we are, we
are asking is. Well, the marked items correspond to those
assignments which satisfy this Boolean formula.
And what we are looking for is one such assignment.
So we are looking for a marked entry in this digital haystack.
Okay, so, how would you go about trying to solve this quantumly?
Well, here's a tempting thing. Why not try to use this, the fact that you
have an exponential super position to probe all these two^n entries in parallel.
In different quantum universes so to speak.
So, in other words, we all know that, that we could, we could take n qubits, you know
n qubits where two^n = N and we could put them in the, in an equal superposition
over all n-bit strings. So, you know, all numbers between zero and
N-1. So we, we, we start in this, you know, we,
we could use a Hadamard transform. And create this superposition, sum over
all y. Y= zero to N-1 of one / square root N, Y.
And now, we go ahead and, and probe the yth entry of our, of our table.
If you want, re, remember what, what, what, what this digital haystack
corresponded to. So, so let's, let's write it down here,
so. Remember, we had some, some Boolean
formula f(x). We're thinking of x as, as x1, x2 through
xn. As N and this and f(x) with some Boolean
formula which, which was say x1 or x2 bar or x3 and so on and so on and so on.
Okay, so it's in and of a bunch of clauses and we think of f(x) as being either zero
or one. And so now we, what we would do is, we
just feed this into some circuit, which computes f.
And our output would be of course, of course, is a superposition over all y of y
f(y). Right, and now.
Okay, looks like we've computed f in super position and now, could we reach and then
and pick out a satisfying assignment, a y such that f(y) =one.
But think about it. That's not how quantum mechanics works,
right? Remember, we have our rules of
measurement. So, if we do a measurement, so what
happens if we measure? What happens is, what's the chance we see
f(y) = one. Well, remember our rules of measurement.
It's the same as though we measured everything.
We measured all our inputs, all, you know all our qubits and then it's a chance that
f(y) = one if we measure all the qubits. But what happens if we measure all the
qubits? Well, when we measure all the qubits, we
see a random, a uniformly random y. So, we each see each y with probability
one / two^n. And so, the chance we see f(y) = one is
exactly the same as the chance we, that, that we, we a, we find this satisfying
assignment if we probe the random entry of the table.
Now, the chance of we see, see a marked item if we probe the random entry of the
table. So, so unfortunately, this way of doing
things is no better than probing a random, a random entry of the table.
Okay, so remember what, what give quantum algorithms all its power was not just the
fact that we could get a superposition that, that, you know, that was spread over
two^n different choices. That's not yet enough because we can do
something like that probabilistically. So, if we pick a random entry if, if you
sample uniformly. We could think of that as, having a
probability. A probability spread out uniformly over
all, and, you know, all these exponentially many choices.
What makes quantum computing unique, what, what gives it its power is not only the
ability to do that. But also then later to get constructive
and destructive interference. So, we want to get constructive
interference only at, at those strings which correspond to answers to the problem
that we are trying to solve. Okay, so this is, this is what we're
really trying to do next. So, what we want to know is, can we
actually come up with a better kind of algorithm, much, you know, an algorithm
that, that, that quantumly somehow probes this digital haystack.
In time, which, which grows not like N / two, as in the, in the, in the, in the
classical case. But, but like log of N or [inaudible] in
n. Right?
That would be, that would be the ultimate goal.
Unfortunately, there's a theorem. Okay.
That, that we can prove. Which says that any quantum algorithm to
solve this problem of finding a needle in a digital haystack must take at least
square root of N time. Where square root of N is now two^n / two.
So, it's exponential times two, even though that it, you know, this, this is,
okay. So, so, you know, two^n / two is still
exponential in little n. So this is something that we actually
proved way back in 1994. Around the same time as Shor's factoring
algorithm. So, given this theorem.
Which, which says that there's, there's really not much, you know, that, that you
cannot get an exponential speed-up for searching for a needle in a haystack, and
to the extent that the NP-complete problems are really well modeled by
digital haystacks that you cannot get an exponential speedup for NP-complete
problems. Then Shor's algorithm for factoring was
somehow the best we could have hoped for. So, it came as a really pleasant, an
unexpected pleasant surprise that quantum algorithms were this powerful.
This was, this was really a remarkable discovery.
Okay, a couple of years later there was this beautiful iris that was discovered by
Grover which, which showed that in fact. You could get this quadratic speed-up.
So, you can't get an exponential speed-up for unstructured search.
But you can get a quadratic speed-up over the best classical algorithm.
And you can solve this problem in the square root of N steps.
So, let's, you know, let's again be clear about the problem we are solving.
So, if the problem is, we are given a function from zero, one through, zero,
from a domain of size capital N to zero, one.
And the challenge is to find an x such that f(x) = one.
The hardest case, of course, is when there's exactly one needle.
So, you're looking for you know, there, there's exactly one x such that f(x) = one
and you're looking for that one. Okay.
So, so once again, the way to think about this, this, this, this problem is you're
given a program for, for computing f. So, you're given some, some circuit.
C sub f, which takes as input. N bits, and outputs a single bit f(x).
So, it takes as input x, outputs f(x). And equivalently, of course, you can, you
can transform this. Into a quantum circuit, U sub f.
Which takes us and put x output x. It takes a input x and zero, and outputs x
and f(x) Or if you want, you can, you can actually let the input, you know, you can,
you can say it more generally, and if this answer bit initially was B, then your
output bit as B exclusive or f(x). So, it toggles the bit if and only if f(x)
= one. What we're assuming here is that you
cannot look inside the circuit. The circuit is given to you as a black
box. And you cannot look inside this quantum
circuit, either. So, all you can do is give it an input and
see what the output is. Of course in the quantum case, you can not
only give it an input x, but you can also give it an input sum over all x.
So superposition of all x. And then your output is a superposition.
The same superposition over all x, of x, f(x).
Okay, so in the next video we'll see how, how to actually get this quadratic speed
up for this search problem.