"Quantum Computing" is among those terms that are widely discussed but often poorly understood. The reasons of this state of affairs may be numerous, but possibly the most significant among them is that it is a relatively new scientific area, and it's clear interpretations are not yet widely spread. The main obstacle here is the word "quantum", which refers to quantum mechanics - one of the most counter-intuitive ways to describe our world. But fear not! This is not a course on quantum mechanics. We will gently touch it in the beginning and then leave it apart, concentrating on the mathematical model of quantum computer, generously developed for us by physicists. This doesn't mean that the whole course is mathematics either (however there will be enough of it). We will build a simple working quantum computer with our bare hands, and we will consider some algorithms, designed for bigger quantum computers which are not yet developed. The course material is designed for those computer scientists, engineers and programmers who believe, that there's something else than just HLL programming, that will move our computing power further into infinity. Since the course is introductory, the only prerequisites are complex numbers and linear algebra. These two are required and they have to be enough. Happy learning!
Computational Complexity
Loading...
En provenance du cours de Saint Petersburg State University
The Introduction to Quantum Computing
22 notes
À partir de la leçon
Intro
Rencontrer les enseignants
Сысоев Сергей Сергеевичкандидат физико-математических наук
Кафедра системного программирования
Okay. Let's put aside
this non-computable functions and leave it to philosophers.
We're now going to concentrate only on computable functions.
It appears that these computable functions are not all the same.
Some of them are easier to compute and some are harder to compute,
and the reasons of these differences are not exactly clear.
Honestly, it is not clear at all.
Imagine two very similar problems.
Each of them takes some graph as its input.
So, you have some vertices,
some edges, and a graph.
The question for the first problem is if there is
an Euler's path in this graph?
The question for the second problem is if there is
a Hamilton path in this graph?
The Euler's path is the path which visits
every edge exactly once and
the Hamilton path is the path which visits
each vertex exactly once.
The first problem is known to be easy.
We have an effective algorithm for solving it.
The second problem is believed to be hard.
We don't know an effective algorithm for solving it and there are
reasons to believe that
this effective algorithm doesn't even exist.
Now, I, again, use
some unclear theorem and effective for a good algorithm,
assuming that if there are effective or good algorithms,
there also exist ineffective or bad algorithms.
Here, I allude to
some hidden parameter which allows me to estimate algorithms,
and to say that some of them are good,
some of them are bad, and some are worse.
There are actually plenty of such possible parameters,
and here I use time or number of steps of
deterministic turing machine needed to perform the computation.
So, here for these two problems which are quite similar,
we have very different results for one problem.
We have an algorithm which requires not much time.
For the second problem, we don't.
Let's consider another example.
For example, we have two integers,
two, maybe, natural numbers,
a which has n digits,
and b which also has n digits.
Now, we're going to add these numbers,
a and b, using the column addition method we learned at school.
This method will require at most two n of elementary additions,
and elementary addition is just the addition
of one digit to another digit.
So, we see that the complexity,
the number of steps we need to perform to accomplish the result,
depends on this n,
the number of digits.
We can say that the complexity of the problem is O of n. So,
it's linear regarding the number
of digits in the numbers we have to add.
Now, imagine that we have to multiply these numbers.
So, instead of summing them,
we have to multiply them.
This will require approximately n square
of elementary or table multiplications which
means that the complexity of
the multiplication problem is O of n squared.
We can see now that if when n grows,
the complexity of multiplication grows
faster than the complexity of addition.
Anyway, we don't consider multiplication problem to be very hot.
Actually, any infinite power
here tells us that the problem is not so bad.
All the problems for which we have
a polynomial complexity algorithm,
we consider them to be tractable.
All such problems form the infinite class called b.
So, all these problems for which we know or for which can
exist an algorithm with polynomial complexity defined like this.
A set of this class of tractable problems which we call
P. There is another interesting class
of problems which is called NP.
Here, P stands for polynomial,
and NP for non-deterministic polynomial.
The problems from the class in P are those problems or
those functions for which we can
easily or polynomially check and answer.
The ability to check the answer is important.
Imagine one day, one of your friends come to you and says
that he or she developed a computer program,
a chess player computer program which cannot lose.
Now, can you easily check this statement?
I believe that, no, you cannot because, actually,
you will have to play all possible chess games with
this program to understand if it can loose or it cannot.
Now, imagine another situation that
this friend came to you and tells you
that he or she found a Hamilton path on some graph.
Now, can you check this statement? Yes, you can.
You can just follow this path provided to you by
this friend and see if it visits every edge exactly once.
So, the complexity of this check will be O of n
where n is the number of vertices in this graph.
So, this statement is easily checkable,
and the finding of Hamilton path in some graph is,
thus, an NP problem,
because maybe it's hard to find this path,
but if somebody finds it,
it is easy to check if it is correct.
Out of those that P belongs to NP, because,
for any problem from P,
we can easily check the answer just
by solving this problem with polynomial algorithm.
But the stronger assertion,
if P is less than NP,
is one of the most famous,
most important unproven theorems in modern complexity theory.
Because this theorem is not proven,
we still have to consider these two options on the slide here,
if P is not equal to NP,
here, and if P equals to NP.
So, you see class P here, class NP.
Nowadays, it is believed that there are problems which
belong to NP but do not belong to P,
though we cannot prove it.
One of such important problem is factoring problem.
Imagine that you have found two different big prime numbers,
p and q, each like 10,000 digits.
You multiply them, and you get the product.
Both these tasks are like finding big primes and
multiplicating them is feasible for modern computers.
Then, you give me this number n,
and you ask me if I can find these original factors.
We both know that there is only one set of such factors.
So, theoretically, I can do this, but, in practice,
I cannot because for all algorithms to solve this task,
we know by now,
they all will require too many steps,
and with the reasonable assumptions
about the growth of our computing power,
I will not finish the execution
of these algorithms until my death,
or even until the Solar System's death.
As I said, they require too many steps.
So, this problem of factor is theoretically solvable.
It is computable.
But it is intractable because,
in practice, we can not solve this problem.
To finish here on a brighter note,
in 1994, an American mathematician,
Peter Shor, designed a quantum algorithm
which solves this factoring problem in polynomial time.
So, now quantum computers can
solve problems that are intractable for classical computers.
All of them? Well, probably not.
Here on these diagrams,
you see another interesting class which is called NP-Hard.
These are the problems for which any problem from
NP are polynomially reducible which means that,
if you have some magic black box which solve
some problems from here effectively,
with this magic box,
we can polynomially solve any problem from here,
from the class NP.
In 1972, an American-Canadian mathematician,
Stephen Cook, proved that the intersection of
this class of NP hard problems with the class NP is not empty.
Now, this intersection is
called NP-complete or the class of NP-Complete problems or NPC,
which are the most difficult problems in the class NP.
So, if you find an effective solution for some problem from here,
we can effectively solve any problem
from the class NP with this solution.
Unfortunately for factoring problem,
it is not yet proved that it belongs to NP-Complete problems,
and, actually, it is believed that it does not.
So, it's somewhere here.
But for all these problems,
for NP-Complete problems, in general,
we have a better general solution
for quantum computers than we have for classical ones.
For these problems from here,
we still cannot say anything reassuring
yet which means that maybe you
will be the first mathematician who will find,
who will develop some quantum algorithm which
effectively solves some problems from here, some NP-Hard problems.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2019 Coursera Inc. Tous droits réservés.
