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, you don't have clues which can simplify the search, but in the traveling salesman problem, you have this graph and you may hope to solve the problem easier. You may hope to find an algorithm which uses the information stored in this graph, to solve the problem with less support. Here you can't, but if you can simplify this brute force search which is applicable to the phone book problem, then you will simplify the brute force search for any problem which is solvable with the brute force search. So this is what we want, we want to simplify, or make it more effective this brute force search with a quantum computer. In other words, if you have some easily computable oracle function F here, and we can search for a similar image, so a and b. We can find a then we can solve any of these problems. For example, in the phone book case a is a name, and b is a phone number. For traveling salesman a is path and b is its length. So if we have b for example length and we search for path, and if you have a phone number and we search for name with a brute force, and for the phone book problem, the brute force is our only option because phone book is itself an Oracle. It's not included in the problem description. Here it may be not our only option, but if we can solve this one effectively, we will be able to solve this one effectively too. So we need to speed up the brute force search, but can we do it? Surprisingly yes, with a quantum computer.
