"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!
Computability and Algorithms
Loading...
Из курса от партнера Saint Petersburg State University
The Introduction to Quantum Computing
38 оценки
Из урока
Intro
Познакомьтесь с преподавателями
Сысоев Сергей Сергеевичкандидат физико-математических наук
Кафедра системного программирования
In the last lecture,
we discovered some shocking news.
It appears that there is
a physical limit for the current computing technology.
At some point, we will not be able to construct
a smaller transistors and the growth of
our computing power will eventually stop.
This along can distress us, but there's more.
I already mentioned the word universality.
Now, it's time to dig a little bit deeper,
understand what does it mean.
To do that, we first need to define
what is the goal of computation.
Computation transforms information.
That's true. But why?
Can we give a general answer to this question? Yes, we can.
If you reflect a bit
on any computation you ever performed in your life,
you will probably agree that
you computed the value of some function.
Again, it is just another way of
saying that computation transforms
information because it maps some input data to
some output data and so does any function.
So, why do I need this another definition?
Why do I need to employ this notion of function?
Because functions have a strict mathematical definition.
I can define, for example,
the whole set of functions which transform natural numbers,
map actual numbers to one bit.
This set is infinite,
but it is well defined.
Now, I can ask myself,
if I can compute any of these functions.
For this question to be correct,
I have to define first what does it
mean that I can compute a function.
For example, for a function f,
I can compute it that if for any x,
natural x, I can compute f of x,
but there's an infinite number of such inputs.
So, how can I be sure that I can do that for any of them?
I can be sure if I have an algorithm for computing this function.
But again, I just explained one clear thing through another.
What is algorithm?
The answer to this question was
given by the English mathematician,
English scientist, Alan Turing in his PhD thesis in 1936.
Algorithm is deterministic Turing machine.
Before that definition, there was
some understanding that algorithm
is something which works for any input data,
it has infinite number of steps
and it requires no thinking effort.
But Turing gave us this strict mathematical definition.
So, algorithm is deterministic Turing machine,
DTM and it is as you probably remember,
is infinite tape market into squares and infinite alphabet,
symbols of which can be written on
these squares and read-write tape which
can read and write one symbol at time on
each step and infinite number of states,
including the initial state and final states
and infinite number of
rules which control the behavior of this abstract model.
So now, algorithm is
a finite tuple of finite set and sets elements.
This is a very powerful model because it allows
us to define the universal Turing machine,
which is the deterministic Turing machine,
which accepts another Turing machine as it's
simple and emulates it's behavior.
So, this universal Turing machine can do
anything that any other deterministic Turing machine can do.
There are the time in 1936,
a hypothesis was from weighted
which is now known as Church-Turing Thesis,
which states that there is
no other deterministic computing device if
the report are larger than that of
deterministic of the universal Turing machine.
So now, this question,
if we return to the question of computability,
now this question about these functions,
which transform natural numbers to one bit.
Now, this question makes sense.
We can ask ourselves,
if all these functions are
computable and we can try to reply to this question.
So, are they computable?
Because for any function to be computable,
now it means that there is
a deterministic Turing machine which computes this function.
To answer this question, we first,
we'll count how many deterministic Turing machines are up there.
Of course, it is an infinite set,
but we are going to find out which is the cardinality of this set.
Since any deterministic Turing machine is
a finite tuple of finite sets and elements,
it can be encoded as a finite string in some alphabet.
For example, in the alphabet of ones and zeros.
So, any deterministic Turing machine,
we can represent like this.
Some finished string of zeros and ones.
Any of such strings can be mapped to two natural numbers.
First is the number of leading zeros and the
second is the number represented by
this string in binary encoding.
This set is countable, so now,
we can conclude that we have
only a countable infinity of deterministic Turing machines.
Sounds good. Now, let's compute how many functions
of this type are there.
To do this, we are going to define the following procedure.
I will take some function from this set.
For this function, I am going to write a string,
again of ones and zeros.
I'm going to write one,
zero, then there's no comma.
Then, I'm going to write one bit,
which is f of one.
The next bit is f of two,
f of three, etc., up to infinity.
This infinite string of ones and zeros represents some real number
on the interval from zero to one and different functions
map to different numbers from this interval and
different numbers from this interval defined
in this way, different functions.
We perfectly know that there are continuum of such numbers,
of real numbers on the interval zero, one.
So, there is continuum of these different functions of this step,
which means that there are uncomputable functions.
Even more if we take a function from this set at random,
then the probability of the event we can compute it is zero.
We can compute almost nothing in
this mysterious and beautiful world.
Okay. Maybe it's not so bad.
Maybe all these uncomputable functions are bizarre and useless.
It appears to be not true.
In the same paper where
Turing defined this deterministic Turing machine,
he provided us an example of a very useful function,
which is uncomputable and this example is
now known as the halting problem.
Mention a function, for example, we'll call it H,
which the deterministic Turing machine,
some algorithms as its input
and the input for this deterministic Turing machine.
This function returns zero
if this machine will stop,
will eventually stop on this inputs at some point
of time and provide us some result.
It returns one if this Turing machine hangs on this input.
So, for this input,
it has some infinite loop.
So, this function H,
it analyzes in some way the machine on its input and
gives us an answer if it has
an infinite loop for this particular input or if it does not.
Turing proved and this is a quite an easy proof
that this function H is uncomputable.
So, it means that
deterministic Turing machines cannot
analyze deterministic Turing machines.
If Church-Turing thesis is correct,
then we're deterministic Turing machines and
we are not able to analyze every computer program,
which means that there can exist,
can be written a computer program
which we will not be able to understand or
to predict its behavior
at deterministic computing computer program.
Isn't that amazing?
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2019 Все права защищены.
