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.