Greetings everyone, welcome to

the last week of our course.

Up to this point, we have

discussed several quantum algorithms.

One of them of extreme use which

was the main topic of the previous week,

and we can see that

some quantum algorithms perform

better than classical ones.

Now, it's time for us to raise

some more general questions about

quantum computing which are

rare capabilities and boundaries in general.

Let's do it. Now, when we went this far,

many of you possibly ask yourself,

"Are quantum computers always

better than classical ones?"

Since all the algorithms we

already consider it may make us think that they are,

but we never prove that,

and can we imagine a case when

a quantum computer performs worse than classical one.

Another question is after

this amazing result of Peter Shor

which shows us to solve

very hard for classical computing problem,

which is itself from the class NP.

So the second question may be,

can we effectively solve any problem from class NP?

If a factoring problem was

proved to be NP complete then there will

be no such question because ability to solve

any NP complete problem

also has to solve any problem from NP,

but for factoring problem this was never proved.

We don't know yet if it is NP complete or not.

So this question here is, can we do it,

can solve any problem from NP

including these NP-complete problems,

and we never discussed in this course yet,

any of the NP complete problems and that's for a reason.

Now, many problems that we discussed,

the function there was an Oracle,

so we did not dig in its internal structure.

So maybe we can expect

something like this for NP complete problems,

or for any problem from NP.

If we implement some function

as an oracle and maybe there

is an algorithm which solves

a problem from NP is

the function implemented as an oracle,

so that is the question,

is there such algorithm?

The answer to the second question was given in 1996 by

an Indian and later American mathematician Lov Grover.

Lov Grover dealt quantum algorithm

which was able to solve any problem

of NP independently of its structure.

Imagine that you have an old telephone book,

and you need to find a particular entering it.

This quite a common task.

You have a person's name and you search

for his or her number.

Now, since this task is so common,

all the telephone books are organized in the same way.

They are sorted by the names of the phone owners.

So it starts with names which starts with A,

out of these names there are names which starts

with B, and C, etc.

So you can use

the binary search to

find the telephone number of any person,

but I mentioned that the task

now is completely different.

That you have a telephone number,

but you need to find the person's name.

For example, somebody called you and you need

to identify this person by his,

or her telephone number using this book.

So if you start to solve this task,

you will find very soon that it is very difficult

because you need to examine every entry in this book,

and to compare the phone numbers for this entry,

and the phone number of interests

since this book is not sort by the telephone numbers,

and you have no clue to simplify the search.

Of course you can stop the such as soon

as you've found this number,

but this depends on your luck,

and if there is N entries in this book,

you will need on average N divided by

two quires to this book,

and we might call it oracle.

So quires stores this oracle,

and this is our average complexity for searching for

the person whose number we know using this book.

This type of search called the brute force search,

apparently is applicable to any problem from

NP since if you have some candidate for an answer,

you can easily check this candidate,

but if you don't have

a candidate then you have to find it.

Then the problem becomes hard.

Imagine for example the traveling salesman problem.

So you have a graph,

a fully connected graph,

and if you have some path in this graph,

you can easily check the length of this path.

You can easily compute it and see if it fits your needs,

but if you don't have the path and you have

only the desired length then,

the problem becomes complicated and

in the worst case you will need,

if n here is the number of vertices.

You will need this number of tries of both to

be checked to compute

the length and to find the path that you need.

So this problem seems to be

very similar to this phone book problem.

If we have some candidates,

we can easily check it,

but if we don't we have to search for it

and often we need to employ the brute force search.

But honestly this traveling salesman problem and

the phone book problem

are not completely the

same because in the phone book problem,