So, let's continue. This is a quantum technology course of Teleschool. I am Roman Dushkin and today we have our third lesson, which is dedicated to quantum sensorics. Last time we have quite deeply immersed into the world of quantum mechanics, so, you already have some understanding of what is happening on the micro level. Today we will study. the first practical aspect. It is not as interesting, as, for example, quantum computations, though quantum sensors will be of a great value for you. So, let's study them.

Theory

We will start from the definition. Quantum sensor is a quantum-mechanical system, which can be used as a measuring tool. Remembering our last lesson, you need to ask the question, how this is possible if the measurement of parameters of the quantum system has the most catastrophic effect on the system. And if you remember about decoherence, it becomes unclear how to use microscopic systems to measure anything. But this is the whole point. Quantum systems interact with the environment very easily, and the environment changes their state. But if so, such quantum systems can be used as sensors! It turns out that since the system is very sensitive to the impact of the environment, it is possible to measure the impact of the environment with its help and, in this way, to measure the environment’s characteristics indirectly. This is what we need for creating sensors.

In fact you can obtain the value of any physical parameter with the help of measuring quantum systems. First of all, of course, we are talking about different fields — electromagnetic and gravitational fields. Other parameters that can be measured with the help of quantum technologies are time and energy. More complex parameters are computed analytically with the help of the values obtained when measuring the basic physical parameters. Quantum sensors have two important properties that make them so interesting. This is a very high resolution in space and time. Space resolution is responsible for the accuracy of measurement in space, and timing resolution is responsible for the measurement frequency. It goes without saying that the high resolution is a consequence of the very small size of the quantum sensors.

Quantum sensors have one more important property. It’s non-invasive measurement. In fact, there are many non-invasive measurement technologies, but it seems that using quantum sensors is the most obvious way for such measurements. Let's look at two examples. Here, let's say, there are all kinds of artificial structures — buildings, bridges, overpasses etc. It is necessary to check their condition, so that, for instance, the bridge will not fall. For this purpose an inspection is from time to time carried out with the removal of material from the bridge pillars for laboratory study. This is an invasive monitoring technology, which destroys the bridge pillar itself. In fact, no one applies this method, but nevertheless, such methods were widely used before. Another example. For reliable cancer diagnostic, it is necessary to perform a biopsy of the tissues where the cancerous growth is supposed to be located. In the process, the tissues are damaged, and the cancer cells, as the most aggressive ones, «spread» through the damage channel. In this case, invasive monitoring technology leads to worsening of the condition. Quantum sensors will allow carrying out these and many other measurements in a non-invasive way, without disturbing or weakening the object of measurement.

Let's think about other spheres, where quantum sensors can help. It is important that quantum sensors have such microscopic dimensions that they can be applied at the molecular level. In fact, these are nanomachines, which can, for example, penetrate the body cells and measure the parameters of their vital activity. Such sensors can be mounted directly into the various materials on the production phase in order to transmit signals about what is happening to such material and determine the deterioration rate. It opens the widest possibilities for managing any object, since obtaining the information about the state of a controlled object is one of the important principles in control theory.

###p atomic clocks or quantum clocks are widely used. In fact, it is a quantum device for a countdown of an extremely high accuracy, which is now used in all processes, where particular accuracy in time measurement is required, such as marine navigation, cosmonautics, geolocation and so on. But modern quantum clocks of particular accuracy are quite bulky, that is why now the researches are aimed at quantum clock miniaturization. Therefore the existence of particular accuracy quantum clocks contributes to the possibility of measurement of other values that are expressed through time. In particular, the units of distance measurement are determined much more precisely with the help of quantum clocks, then with the help of the «standard» ones. So, the most accurate geolocation will be possible when miniature quantum clocks are embedded in every device for position determination.

###p laser use are the most.

Practice

Well, let's move on to practice. As I said, we will not deal with any quantum technologies but quantum computations at our practical lessons, so perceive my previous words about quantum sensorics as a short introduction into the subject. Today we will continue to develop a framework for work with quantum algorithms and our main aim for today is the implementation of the functions for quantum gates coherence into the quantum algorithm. What does it mean from the point of view of mathematics and computer studies?

Well, we need to implement the operator, which receives a qubit, and we remember that it is a list of complex numbers, and also a quantum gate, i.e. a matrix which also consists of complex numbers. The result of the operator implementation must be a new condition of qubit, which we get after we apply gate to qubit. From the point of view of mathematics this is the operation of vector and matrix multiplication. The input qubit, which is represented by the list, is also a vector. In this case we need to multiply the matrix by a vector, because the operation of multiplication is not commutative for matrices. As a result of such multiplication we also get a vector, i.e. a list, i.e. a qubit. Needless to say, you can send it to the next gate, that is, again to multiply it by the matrix. Since all the matrices are square, the dimensions do not change, everything is quite simple.

The next thing we need to implement is the measurement operation. The measurement is applied to the qubit, and returns the value of this qubit. If you recall everything we discussed in the last lesson, it is pretty simple. The qubit is represented here as a list, each element of which is a complex-valued coefficient in the quantum state. If the moduli of all these coefficients are squared, as a result, we get a probability of finding a qubit in the corresponding state. In other words, the measurement operation must take a qubit and return one of its states with a probability equal to the square of the modulus of the corresponding coefficient. This is quite easy, so you will find an implementation in the source code for this lesson, where you will have to understand and perform some tasks.

Well... Today we studied the main point and areas of application of quantum sensorics, and also supplemented the framework with the new operations for applying the gate to the qubit and for the measurement. This is very cool, because now we can implement quantum algorithms with the help of this framework. Well, at the next lesson we will begin to study the theory of quantum information transfer. Stay with us. See you.

Hello, my friends. This is a course in quantum technology in Teleschool, my name is Roman Dushkin and today we have our fourth lesson. In the last lesson we have more or less thoroughly studied quantum sensorics. We will leave this topic, because now quantum sensors mostly remain at the level of theoretical research. And today we will move on to the application area, which already has the very direct practical achievements. This is a quantum information transfer. Are you ready? Let’s plunge...

Theory

Let's think about the way the information is transmitted. Imagine, as usual, two actors — Alice on one side and Bob on the other side. Alice wants to send a message to Bob. If the evil Eve is between them and in one way or another controls the channel of information transfer, then she will be able to seriously affect what is happening between Alice and Bob. For example, Eve will be able to substitute messages and, thus, manipulate both members of the information exchange. For instance, Bob sends Alice a message: «Come to the hayloft tonight» and Eve substitutes it for: «Today I'm leaving to another city for long». Frustrated, Alice replies: «Well, I'll be waiting for you» and Eve transmits: «No, everything is over». Well, that's how the wars begin...

Well. Let Alice and Bob be old conspirators. They can use the cipher. But Eve is not stupid, too. She can often decrypt the messages by cracking the cipher. Today there is a struggle between cryptographers and cryptanalysts, and we can’t say who is winning so far. Now there are encryption schemes that can give more or less reliable protection against direct hacking, but the appearance of a universal quantum computer, which we will talk about in the next lesson, will tip the scales in favor of cryptanalysts, and no information transfer, encrypted by modern means of cryptography will be considered fully protected. It’s all because modern methods of information protection are based on unproven hypotheses about the practical impossibility of solving certain types of mathematical problems. In particular, such problems include factorization and discrete logarithm.

But there is one encryption scheme that can’t be hacked theoretically. This is the so-called «one-time pad». The nature of the scheme is very simple — the length of the key should be equal to the length of the message, and the key itself should be absolutely random. This scheme is used today for top secret communications in the field of intelligence activities. But the distribution of keys is a problem. Since the length of the key should be the same, as the length of the message, intelligence agents and spies must have entire books with sequences of random characters, and each has his own. The distribution of such books, that is, one-time pads, is very difficult — the agent must come to the center and secretly receive his copy. The problem was more or less solved with the help of Diffie-Hellman key exchange, but this protocol is based on the tasks of discrete logarithm.

But is it possible to do so that the very nature of our reality protected the channel from the surveillance? If you remember the lesson before last, it should be completely clear for you that there is one thing that can help here. Stop the video now and think, which of the principles of quantum mechanics that we discussed can help protect the channel from the surveillance or, at least, give Alice and Bob the opportunity to understand that the channel is compromised. Stop the video and reflect on it for a while...

Well ...Have you reflected on it? Do you have any ideas? If you thought about Heisenberg uncertainty principle, then you are wrong. If you thought about Pauli exclusion principle…Ah, no. We have not studied it yet. We’ll do it later. Well done, those who thought about the measurement of the state and the collapse of the wave function. This is exactly the process that underlies modern protocols of quantum information transfer. The thing is that the collapse of the wave function is an irreversible process. If the state of the quantum system collapsed, then it cannot be returned. This characteristic formed the basis of the first quantum information transfer protocol BB84. Now we will consider it.

So, the BB84 protocol, as its name implies, was introduced in 1984 by Charles Bennett and Gilles Brassard, and its physical implementation in very limited conditions was carried out only in five years. This protocol is used not for sending messages, but for distributing keys. In fact, with its help, Alice and Bob create the same secret keys. They can use the one-time pad scheme with the help of these keys. This should be explained — all existing quantum information transfer protocols are used for keys distribution, and not for encryption of the information. Information is encrypted using one of the stable schemes, most often with the help of a one-time pad.

In the framework of the protocol, information is transmitted with the help of qubits. But two different qubits are used. Let me tell you the essence on the example of photons. Since photons can be considered as waves by virtue of the wave-particle duality, they can be polarized in various ways. We will make qubits from photons on the basis of polarization. Let’s call one way of polarization vertical-horizontal, and the second way is diagonal. The trick is that the diagonally polarized photons in a vertically horizontal basis appear as an equiprobable superposition, and vertically and horizontally polarized photons appear as an equiprobable superposition in the diagonal basis. This is important, since if a horizontally polarized photon is measured on a diagonal basis, it will accept a value of either right-to-left or left-to-right with the probability of fifty %. And this applies to any combination of such measurements for these two bases.

Well, let's look how it works. Alice and Bob should get two identical bit lines to use them later as a key. The key must be random. And then Alice sends Bob a random sequence of bits, bit zero being randomly encoded by one of the two qubits, and bit one is also randomly encoded by one of two qubits. In other words, Alice sends Bob a random sequence, consisting of four different symbols, the pairs of which are encoded by ordinary bits. What does Bob do? He makes measurements of the qubits obtained, randomly choosing the basis of measurement. As a result, he receives a random sequence of bits. Now he needs to call Alice through the regular channel and tell her which bases he used to measure the qubits, and Alice should tell which measurements were correct. The final key is obtained after deleting all the bits that Bob measured with an incorrect basis. Alice and Bob got two identical lines of bits.

What will happen if evil Eve surveilles the channel? She also does not know which basis Alice uses to form qubits, so she has to measure the incoming qubits in a random basis. After the measurement, Eve must send the measured bits back to the channel in the direction of Bob. She encodes them randomly. And it turns out that about half of the qubits, sent by Eve, are encoded not in the basis that Alice originally used. Bob will measure the accepted qubits, and the trick is that after he and Alice check the coincidence of the measurement basis with the basis of the sent message, it will turn out that about a quarter of Alice’s and Bob’s coincidences do not coincide. To control channel purity, Alice and Bob must compare a certain number of bits, and if at least one does not match, then the channel is compromised. They will know for sure that Eve was between them. The more bits Alice and Bob check and find out they coincide, the less likely is that Eve surveilled the channel. With each bit checked, the probability drops, but it will never equal zero. The BB84 protocol is considered to be reasonably stable, because by selecting the number of bits to be checked, it is possible to bring the level of credibility to the transfer to any given degree.

So, the quantum information transfer protocol BB84 is intended for the distribution of random keys, which can later be used to encrypt the messages with the help of one-time pad method. Using the protocol, you can create a random length key and then check the channel for the presence of an evil surveillant. But this is theory. In theory, everything is fine, and if in practice we had the opportunity to send single photons, then the protocol would work as expected in theory. However, the practice is always rougher, and this allows implementing various types of attacks on the protocol. So, when implementing, it is always necessary to look thoroughly what attacks can be carried out because of practical implementation.

Practice

Let’s move on to practice. We will set aside the framework developed on the previous two lessons. Today we will devote ourselves to developing a simulator for the BB84 protocol. We need to implement primitives to represent quantum information, its transfer between the actors and measurement. The practice we have had before will help us, so let’s start.

So, what do we need to do today? We need to implement functions to generate a random bit sequence for Alice. Then this sequence should be transformed into polarized photons. The choice of a basis for polarization is also made randomly. The sequence of photons should then be transferred to a measurement function, which bases are also randomly selected. After that, the measurement results should be sifted for the coincidence of the coding and measurement bases. As a result we should obtain a bit line, the same for Alice and Bob. In the appendix to this lesson you will find a file with source codes that fully implement what I have just listed, and your task will be to add the function of Eve absence test to the source code, which receives an acceptable level of input credibility. The impact of Eve should be implemented as a separate function, interfering with the transfer. Go for it.

So, today we worked nicely and studied the first quantum communication protocol BB84. We also wrote a code necessary for its simulation. Well, in the next lesson, we will continue to study the theory quantum information transfer and see what new protocols exist, because it has been a long time since 1984. See you later, bye.

Hello and welcome to Udemy. This is a course on quantum technologies, and today we have our fifth lesson. Last time, we started studying the quantum protocols of information transfer and dived into the BB-eighty-four protocol in detail. Today we will continue this topic and consider what other quantum protocols and their possible implementations exist. In a practical lesson, we will deploy Quipper, the language of quantum programming. Are you interested? Then go ahead.

Theory

Let's start with the theory. Let's look at a few more quantum information transfer protocols that have been developed since that time. In nineteen ninety-one, the E-ninety-one protocol was introduced by Artur Ekert. It is based on the Einstein-Podolsky-Rosen «thought experiment», or the EPR paradox. This is also a key distribution protocol, like the BB-eighty-four. Its peculiarity is that three different EPR pairs are used to encode bits sent to Alice and Bob by a third trusted party, both Alice and Bob measure them using a randomly chosen basis of three possible ones. Accordingly, only a third of the bits will be measured by Alice and Bob in the same bases and will become the key. But the main thing is that the discarded bits are used to control the absence of an evil surveillant in the channel. Alice and Bob take chains of discarded bits and specifically check them for Bell’s inequality violation. If the Bell’s inequality formulated for this protocol is not violated, then there is a «hidden variable» in the channel, that is, the channel is being surveilled. Despite the fact that this is also a probabilistic assessment, there are protocol modifications that lead to a degree of confidence in the purity or discredity of the channel to one hundred per cent. But there is one problem — the presence of a trusted third party, i.e., it is a centralized protocol.

Oh well. Let's continue. Charles Bennet, already known to you, did not stop. In nineteen ninety-two he introduced a new quantum key distribution protocol, now called B-ninety-two. Strangely enough, now this protocol is based on Heisenberg uncertainty principle, but at the «second level» the protocol can use both qubits and EPR pairs. It means that it absorbed the features of both: the first protocol of the BB-eighty-four and the E-ninety-one protocol. To transmit information, photons are used in two different polarizations — horizontally-vertical and circular, and these polarizations depend on each other, which introduces uncertainty in the measurements. The keys distribution is carried out in an exactly the same way as in the BB-eighty-four protocol, with an adjustment for the possibility of a loss in the channel, that is, Bob may miss some photons when receiving. But the check for the presence of the evil surveillant is made in the following way. Alice and Bob choose a random subset of the received bits and check their parity, that is, the sum of the bits must be either even or odd for both actors. This allows us to determine the purity of the channel with the necessary degree of confidence. It turns out that this protocol is also probabilistic.

The next developed protocol was SARG-zero four protocol, introduced in two thousand and four as an extension of the BB-eighty-four protocol, which is resistant to the attack of the division of the number of photons. The thing is that in theory the BB-eighty-four protocol requires the use of single-photon signal sources, while in practice a weak coherent impulse of a multiphoton source is applied. If Eve detects several photons in the signal, she sends everything to Bob, takes one photon for herself and tangles it with her photon. Then she waits for Alice and Bob to exchange measurement bases through the open channel. After that she will measure all the photons without interfering with the transfer. So, in the SARG-zero four protocol, Alice does not send Bob the information about which bases were used for coding the qubits through the open channel, and instead Bob receives this information logically as a result of the state measurement. The thing is that Alice sends not just qubits, but two-qubit systems, in which the first qubit determines the bit of the secret key, and the second qubit is intended to help Bob determine the basis. Because of this evil Eve has to store multiple copies of each qubit, and this reduces her capabilities for the described attack. But in general, the protocol has the same power as the original protocol BB-eighty-four.

Well, let's look at another protocol. As you saw in the example of the previous one, the researchers and scientists in the new century began to pay closer attention to information security related to practical implementation. And in two thousand and five a group of Chinese developers introduced the Lo-zero-five protocol, which is based on the transfer of special quantum states («traps») to the channel, the purpose of which is only to reveal the evil surveillant in the channel. In fact, this is a multiphoton extension of the basic protocol BB-eighty-four, supplemented by these traps. Such traps are used to make Eve change channel parameters, which are known to Alice and Bob and depend on the channel-forming equipment. Actually, Eve only needs to change one trap to reveal herself. Well, I should say that now this protocol is mainly used in practice for quantum data transfer.

So, here are the protocols that we have studied: BB-eighty-four, E-ninety-one, B-ninety-two, SARG-zero four and Lo zero five. As you now understand, all quantum protocols are designed for key distribution. Actually, they do not even distribute the keys, but create new random sequences of bits that can be used as keys in the process of their application. Practical implementation of the protocols implies that errors can occur during the transfer of qubits in the channel. They can appear due to the malicious actions of the third party or due to regular distorting actions, but to increase the level of security it is always considered that these are the actions of a third party. After obtaining the same sequence of bits, Alice and Bob must implement two more steps — information reconciliation and privacy amplification. To do this, they apply certain methods, which allow to say with a high degree of confidence that Alice and Bob have the same lines, and Eve does not have such a line.

Well. It's all great. Altogether we currently have, at least, five quantum protocols for key distribution. But, what's next? Do they still remain at the level of theoretical research? That’s not true. There is a large number of implementations, and the widely advertised Chinese experience is not the first one. There exist entire ready-made commercial solutions produced by companies from the US, Switzerland, France and Australia. That means that anyone can buy a quantum system for keys distribution and use it. Banks are particularly interested in these systems. Nowadays the banks are the main force for progress in this sphere, since they are the main customers. They understand that a universal quantum computer will bring the entire financial sphere down if it is not protected. So banks work proactively. In Russia, too, there are large orders from Gazprombank, Sberbank and Vneshekonombank. So we will keep track of what is happening here, since the problem is that there are still no reliable quantum routers and repeaters that will make it possible to build a network.

Practice

Excellent. Now let's move on to practice. Today we have a rather simple practical lesson — we are going to download and deploy the Quipper programming language distribution package. To do this, we will go to the official site of this programming language and get the distribution package in the «Download» section. This package is intended for Haskell Platform, and there is an instruction on how to deploy it on the website. After installing the package, it will be available in the Haskell development framework. You can also download several examples of quantum algorithms that are there on the site, then run them and check the performance.

So, we have seen that five quantum algorithms for key distribution have been developed, and they are already being implemented in practice. We have installed Quipper, the language of quantum programming, and are ready to work. In the next lesson we will learn what a universal quantum computer is and what technologies are being considered for its construction in detail. Stay with us and see you. Bye.

Hello and welcome to the Quantum Technologies course in Udemy. I am Roman Dushkin, and today is our sixth lesson. At the previous lesson we have finished the consideration of quantum protocols of information transfer, or to be more precise, quantum protocol of key distribution. Are you interested? Then go ahead.

Theory

So, the universal quantum computer. Why am I talking about universality? Well, the thing is that today there are quantum computations devices. Of course you've heard about the quantum computer D-Wave, which costs millions, works in very cold environments and contains more than two thousand qubits. Now this computer solves only one problem — this is a problem of discrete optimization, and it is solved by the method of quantum annealing. In fact, it is an analog device controlled by a conventional digital computer that first generates input data, then installs the settings for the quantum computer in a special way and starts it for execution, then reads the result and uses it in its further calculations. If the problem can be reduced to quantum annealing, it can be successfully and efficiently solved on a D-Wave computer.

What is a universal quantum computer? Curiously enough, it is also an analog device that is controlled by a conventional computer, but it can be used to solve any problem, that can be solved using universal Turing machine, by means of qubit manipulation. Here I should add that one needs quantum Turing machine, and indeed, such a model exists. However, it is proved that the quantum Turing machine has the same computational power as the universal machine. In other words, a universal quantum computer is a physical device that implements the model of quantum computations on physical qubits effectively, and not by means of simulation. This makes such a device, required for increasing efficiency in solving certain problems. I repeat— the universal quantum computer does not solve any problems that cannot be solved within the framework of a conventional computational model. It only solves some problems more effectively.

However, the quantum Turing machine is just a mathematical model, rather abstract and ideal. When it comes to practical implementation, we come across numerous technological and engineering limitations. As you should understand, physical qubits are rather fragile systems, and they decohere from the slightest interaction with the environment. That’s why the main task of the developers of a universal quantum computer is a complete isolation of a system of qubits, which is possible only at temperatures close to absolute zero at the current level of modern technology.

Only in such conditions one can try to make an entangled system of qubits, which is able to perform quantum computations. And then we come across the following technological problem. In different technologies, physical qubits are represented by different quantum objects. Some of them have a very short lifetime, and some decohere because of interaction with each other. In addition, no matter how we try to isolate the system, it still interacts with the environment.

Well, for example, high-energy cosmic rays, or something else, can destroy a qubit. Here the problem of quantum correction of errors has to be solved. Current methods for solving this problem involve the use of physical qubits redundancy. Well, let's say, ten physical qubits represent one logical qubit. So now you know the main secret. When Google claims to have made a quantum computer consisting of 70 qubits, it is necessary to study the question thoroughly and figure out which exactly qubits are meant. If they mean physical qubits, then you need to make a discount for error correction.

Well. Let's see what are the potential technologies for creating a universal quantum computer. Let's consider only those of them, which are the most promising in my opinion. I will briefly describe each of them, and also tell about the current achievements and reveal the names of companies, where the relevant technologies are explored. Be very attentive, because now there will be a lot of different interesting data. And of course, look through the additional materials for this lesson — there is a comparison table and a presentation there.

The first technology is Penning traps. The qubits are created on charged ions in a one-dimensional chain of traps, created in a vacuum by a certain configuration of the electric field. They are monitored by infra-red lasers. The main advantage is a relatively simple individual control of separate qubits. The disadvantages are the following: the need to create ultra-low temperatures and ensure the stability of the states of ions in the chain. But the most important trait of this technology is almost unlimited lifetime of physical qubits, and at the same time the level of accuracy reaches zero point nine hundred ninety nine. Nowadays it is known that fourteen coherent qubits have been created using this technology. In the world this technology is actively explored by the company IONQ, and in Russia, active research is being conducted at Moscow Engineering Physics Institute.

The next technology is quantum dots. Basically, a quantum dot is an electron in a semiconductor that is limited in space across all three dimensions, and which properties are subject to some more limitations. Another variant of the quantum dot may be the absence of an electron. That is, a quantum dot is a certain charge state in a semiconductor. It is controlled via external potentials or by means of a laser impulse or microwaves. Quantum dots work stably, show a relatively high time to decoherence, and have high accuracy, but require ultra-low temperatures. In addition, while it is known about two coherent qubits on quantum dots, however, the technology looks promising. Intel specialists continue to develop it.

The third technology is superconducting elements. On their basis, the qubits are structured by using the state of the presence or absence of the Cooper pair in a certain spatial area. Control is carried out by means of an external potential or magnetic flux. Such things as Josephson effects, superconducting quantum interference devices, and others can be used here. The problem is that the wave functions of such superconducting elements collapse easily, the qubits are very unstable, but they work very fast. Currently we know about nine coherent qubits. Curiously enough, this technology underlies the development of such companies as Google, IBM and QCL.

The fourth technology is called a macroscopic ensemble with nuclear magnetic resonance. The molecule of an organic liquid is a set of coherent qubits. Control is carried out by means of nuclear magnetic resonance over the macroscopic volume of the liquid. The sequence of radio-frequency impulses acts as quantum gates. Measurement is carried out over an ensemble of molecules. The decoherence time is a few seconds, which is very much. Room temperature is required for this work. But here the number of qubits is unlikely to be more than ten, so today this technology is set aside.

Finally, the fifth technology, which we will consider, is topological qubits based on photons. In general, topological quantum computation is a relatively recent proposal, and so far there is little research in this sphere. However, the technology seems very promising, since all the necessary hardware is available, the ambient temperature is suitable for this technology, it works almost without errors, so the correction is not required. But the problem is that so far the technology exists only in the form of a theoretical model, and existing prototypes in the form of overlapping wave guides for now solve only one narrow problem from the area of linear algebra —  the calculation of the matrix permanent. Suh companies as Microsoft and AT & T are engaged in the studies in this sphere.

There are several other potential areas of research, but today they have become more or less marginal. You can find references to them on the page of this lesson, and also there is a table with a comparison of the technologies I listed. Well, now I will repeat my words — sooner or later someone will build a quantum computer. There are no fundamental obstacles to this. And the one who makes it first, will gain an unprecedented advantage in all spheres of life. The quantum «arms race» is already underway, and we are still catching up with it.

Practice

So, today is the sixth lesson, and it means that we will have a rest from practice. It’s better to devote this day to reading of additional materials, and also skimming of all the previous lessons, that will help your memory in accordance with the Ebbinghaus forgetting curve. Well, today we have studied different technologies, by means of which a quantum computer can be created. Remember, that there are no fundamental obstacles for it, so we are going to live in the post-quantum era. In the next lesson we will learn about the model of quantum computations and its supremacy. See you, bye.

Hello, friends. This is a course in quantum technologies in Udemy, my name is Roman Dushkin, and I invite you to the seventh lesson. Last time we studied what a universal quantum computer is and what physical technologies can underlie it. As you understand, a quantum computer is just a hardware, which, without algorithms and programs, is merely lifeless devices and instruments. The true quantum supremacy is achieved in the connection of the computer and its software, so today we will study the model of quantum computations. Let’s go...

Theory

Today, let's take a brief look at everything that concerns the theoretical foundations of quantum computations, and in the next lesson we'll turn to the main basic algorithms. So, quantum computations is a new computational model, roughly the same as the well-known Turing machine or the lesser known lambda calculus model. As you should already know, this model was introduced by Richard Feynman in nineteen eighty-one, but the theoretical foundations of the quantum computer and the method of its computations were laid earlier by Rolf Landauer, Yuri Manin, Paul Benioff and Stephen Wiesner.

In nineteen sixty-one, Rolf Landauer from IBM formulated the principle, which today is named after him, that in any physical computer system, with the loss of one bit of information, at least some joules of heat are released. If to translate into a simple language, it means that computers generate heat during the computation process. It happens not because they are arranged in such a way, but simply because some information is lost during the computation of certain operations. In other words, this principle connects information entropy with thermodynamic entropy. But why is it necessary from the point of view of practice? If we make a computation device, and if it performs irreversible computations, then there is the lower limit to the amount of heat released, and no matter how hard we try - it can’t be lower. This means that the computational model itself must become different. This is how the idea of reversible computing emerged.

###p billiard balls model. It’s an amazing idea. So, why is there a problem with quantum computations? Let's recall the wave function of Schrödinger. It describes the dynamics of the quantum system's change in time in the absence of «measurements», that is, decoherent effects on it. This dynamic has an important property — it is reversible in time. In other words, the wave function can describe a reversible computational process. And this property underlies quantum computations. There it is.

Let's think about what the process of quantum computation might look like. We already know that quantum computations are performed over quantum bits, that is, qubits. The qubit is a superposition of two orthogonal quantum states. You should remember this from our practical exercises. So, the evolution of a quantum system in time describes the so-called unitary transformation. Because of this the quantum computations are reversible. And this very unitary transformation «twists» the superposition of a qubit in its Hilbert space. Each unitary transformation is representable by a Hermitian orthogonal matrix, and every application of a unitary transformation to a qubit simply once again «twists» in the space of possible states. This is the essence of the model of quantum computations. And at the end, a qubit is measured, when it is projected onto one or another axis of measurement, and a specific value is obtained. If we have a coherent state of several qubits, then the dimension of the corresponding Hilbert space equals two in the degree of the number of qubits. Everything is simple.

Well, that's great. If we have one qubit, then the unitary transformation simultaneously works with its two orthogonal states. If we have one qubit, then the unitary transformation simultaneously works with its two orthogonal states. If we have two coherent qubits, then the unitary transformation simultaneously works with their four orthogonal states. Ten coherent qubits give simultaneous work with one thousand twenty-four orthogonal states. But what does it mean simultaneous? Since the system of qubits is in a superposition, then it contains all possible states of this system with different amplitudes in it. And, if we apply a unitary transformation to such superpositions, it means that we drive all possible states of a quantum system through this transformation, and as a result, a superposition of states is obtained. Actually, this is a simultaneous start of computation of function in all possible values of its arguments. Only the result is a superposition of the range of the function.

Fine, just fine. We can drive all the values of the input parameter through the function for one function invocation. This is called a large-scale parallelism. But what happens next? At the output, we get a superposition of all the results of the function on all input variables. What should we do with it? And here is a problem. We cannot obtain all the values of the function that it computed. If we measure the qubits in which the values of the function are written, then we will collapse the quantum state from the superposition into one particular state from the set of orthogonal ones. And the result of the measurement, in general, is probabilistic. To study the results of a function, it is necessary to conduct a whole complex of measurements, called «ensemble». But then it seems that there is no quantum supremacy. However, a superposition of the results of a function can give us information about the properties of a function. And this is an important aspect of quantum computations, on which almost all algorithms are based.

So, we realized that quantum computations are reversible. In fact, this means that, together with the input qubits, the output qubits immediately translated into the quantum state | 0> are also inputted to the function. After performing a sequence of quantum gates, the same input qubits appear at the input in a certain state, as well as the output qubits, containing the result of the function computation.

Since the model of quantum computations is Turing-complete, one can compute the values of any function, that can in principle be computed, using it. Normally this does not give any supremacy, but sometimes it is necessary to convert classical functions into quantum ones to include them in the composition of quantum algorithms, that is, in a sequence of gates. There is a general technique for transforming an arbitrary binary function into a quantum oracle, and in the next lesson we will study it in detail. But I repeat that the simple transformation of a function from ordinary to quantum usually has no advantage.

Therefore, I always say that creating a quantum algorithm is a kind of intuitive insight. There hardly exists algorithm for developing quantum algorithms. All existing examples of quantum algorithms that demonstrate quantum superiority are the result of the powerful insight of their developers. However, if you peer at quantum mechanics, quantum mechanics will start to peer at you, and so, after studying the technology of transformation an arbitrary function into a quantum oracle, we will devote the remaining lessons to the end of the course to studying various quantum algorithms.

Practice

Okay, let’s move on to practice. Today we have a very interesting task. We will «touch» a real quantum computer. Since we already have prototypes with real tangled qubits, and they are available in the cloud, we can use this function for studying. So, visit this link https://goo.gl/GJHuv1 and register. You can quickly use Google+, GitHub, LinkedIn or Twitter account. This is a cloud twenty-qubit quantum IBM computer.

Let's see what we can do with this quantum computer. For programming, four blocks of five qubits are available. This means that only five qubits can be entered into an entangled state at a time. But this is enough for experiments. At the top of the screen, these blocks are shown. At the bottom left there is a «musical staff» for the location of quantum gates. And at the bottom right of the developer panel there are all available quantum gates. If you click on the «Advanced» tick, all gates that this quantum computer has will be added to the panel.

Let's see how to create quantum algorithms. To do this, you need to drag the pictograms of quantum gates to the musical staff, thus performing qubit transformations. The gates U-one, U-two and U-three are physical gates of a particular quantum computer, and therefore, in the light of universal quantum computations, are uninteresting. So we will not consider them. The id gate is an identical qubit transformation, so it does nothing. It is intended only for superposition with other gates, when some qubit from a set of coherent ones should not undergo transformations. The gates X, Y and Z rotate the qubit by a pi angle around the corresponding axes. These are the so-called three Pauli gates. The Gate H is the Hadamard gate, which introduces a qubit into an equiprobable superposition of basis states. This is a very important gate, there is not a single quantum algorithm without it. The S, ST, T and TT gates rotate the qubit phases, transforming its axes. For example, the gate S transforms the X axis into the Y axis. You can peek the detail using the prompt on the website of the quantum computer. These gates are not as interesting as CNOT Gate (looks like a plus), which influences on two qubits. This is the so-called "Controlled NOT". When the first qubit is in the state | zero>, the second qubit does not change. If the first qubit is in the state | one>, then the NOT operation is applied to the second qubit, that is, the quantum gate X. In fact, this gate constitutes a one-way basis - all functions in quantum computation can be expressed through the CNOT gate. And, finally, the measurement operation. It is applied to one qubit and translates it to a specific bit value.

After the quantum algorithm is ready, it must be saved, and then run. To do this, use the buttons above the panel with the gates. If you click on the «Save» button, the system will ask you to enter the name of the algorithm. After that, it will be available on the list of saved algorithms, which is at the very bottom of the page. From the same list, algorithms can be returned to edit and restart. You can launch them with the «Run» button. By default, the algorithm will be launched one thousand twenty-four times, after which the statistics for the measurement will be available. Keep in mind that the algorithm is usually in the queue for execution, as the table says. This is due to the fact that there are already too many people who want to play with a quantum computer. But when the algorithm is executed and the statistics are collected, you will receive a letter with a notification. And you will be able to check the results. So try it.

Good. Today we did a great job. We learned about the quantum supremacy of the model of quantum computing, and also played with IBM's cloud-based quantum computer. Of course, we are not familiar with quantum algorithms, so we could not do anything difficult, but we’ve got a glimpse of it, so in a few lessons we will be able to return. Well, in the next lesson we will learn how to transform an arbitrary binary function into a quantum oracle. Stay with us, and see you soon.

Hello my friends. This is a Quantum Technology course in Udemy. My name is Roman Dushkin and today is our eighth lesson. During the last lesson we started to immerse deeply into the model of quantum computations and learned about quantum supremacy.  We have even tried IBM quantum computer. And today I want to demonstrate you universality property for quantum computations models, so we will learn to transform an arbitrary binary function into a quantum oracle. Be attentive and let’s start…

Theory

I have already mentioned several times that the quantum computation model is universal. This means that it is possible to compute any computable function. Moreover, the model itself is not more powerful than the traditional Turing computations model, so it cannot compute what cannot be computed by a universal Turing machine. The quantum computations model computes some functions more efficiently than the traditional one, as long as we do not have effective algorithms for such tasks in the traditional model. But, by the way, it is not proved that there are no such algorithms. So, all quantum supremacy is still based on the hypothesis that there are no effective algorithms for some problems in the traditional computational model.

Well, about universality. As I said, any computable binary function can be transformed into a quantum oracle. This does not automatically mean that the function will be computed more efficiently. It means that it will be possible to put a superposition of input values in it, and it will return a superposition of the results. So let's study the method of such a transformation today, since some quantum algorithms require to provide an oracle.

Let's recall one more property of the quantum computations model. Any computational process in it is reversible until a measurement is made. In other words, when converting a function to a quantum oracle, it is necessary to ensure that the computation of the function becomes reversible. But it is natural that an arbitrary binary function is irreversible. For example, if we take a function that computes the logical AND, then it is clear that it is irreversible in the sense that it is impossible to unambiguously restore the values of the input parameters for the result of the function zero. The simplest way to make a function reversible is to transform it, so that it returns the values of all its input parameters. But in quantum computations, the number of qubits at the input should be exactly equal to the number of qubits at the output, which means that auxiliary qubits, in which the result of the function will be recorded, should be input. Altogether, the function receives input values and a set of auxiliary qubits, and returns the same input values and the result of its computations.

So, we need to create a quantum gate, which transforms the sequence of values of qubits. In the point of fact, this is a square matrix. Since we are now considering binary functions, it turns out that there will be only zeros and ones in such a matrix. This simplifies work a bit, though you should remember that complex numbers are used in an arbitrary quantum gate. So, a quantum oracle corresponding to some binary function is a square matrix which consists of zeros and ones. The dimension of the matrix is two in degree equal to the sum of the number of input bits and the number of output bits of the original function.

The procedure for transforming a function into a quantum oracle is simple on the one hand, but on the other hand it is rather difficult to explain it in words. But I'll try. Let's look at an example. For example, let's create a quantum oracle for the logical operation «Exclusive OR». Its truth table looks like this:

What do we need to do now? We need to make such a complicated table. The first two columns correspond to the input qubits, and the third column to the output qubit. In total, we get three columns, which means that the number of lines in them is eight, that is, two raised to the power of three. We add one more column in which the result of the function will be recorded, as well as one more column with the result of the application of the oracle. In the first three columns we record all the binary numbers from zero-zero-zero to one-one-one so that each cell contains one figure. That is, the first row in the three columns will contain zeros. In the second row, the first two columns contain zeros, and the third column contains the figure of one, and so on until the eighth row, in which each column will contain the figure of one. So we filled all possible variants of input qubits. You should also remember that the output qubit is now also the input one, to ensure that the computations are reversible. You should get this table:

Now fill the remaining two columns. Record the result of the function in the penultimate column. In our case, this is Exclusive OR, so in each cell of the fourth or the penultimate column there should be zero if X-one and X-two are equal, and one, if they are not equal. Okay, we filled it. Remember that the penultimate column must consider only the input qubits, that is, in our example, the first two columns. Now go to the last column. Here we need to record the result of applying the Exclusive OR operation to the penultimate column that we have just computed, and the value of the output qubit Y. I shall emphasize, and you should remember that we apply the exclusive OR not because we have such an example, but because the penultimate column is always computed using this operation. Whatever function we transform into a quantum oracle, the output qubits at the output must be computed by applying the Exclusive OR to the result of the transformed function and the output qubits before the oracle is used. As a result, this table should look like this:

Now this table needs to be transformed into a quantum oracle. A quantum oracle is always a square and Hermitian orthogonal matrix. You should keep this in mind. But the table is not square. How to be? Here it is necessary to apply the next procedure. First, we throw out the extra columns — in our example these are the third and the fourth. As a result, only three columns should remain — the input qubits and the result of the quantum oracle. Secondly, we convert each binary number into a decimal number. In fact, this is not necessary, but it's easier to explain now. The number zero-zero-zero becomes just zero, the number zero-zero-one becomes one, the number zero-one-zero becomes two, and so on to one-one-one, which becomes seven. And thirdly, now every decimal number is converted into a sequence of the figure of one and seven zeros, where the figure of one stands at the place, which means the number being converted, if zero place is the first on the left in the eight-digit number, and the seventh place is the last. This is how it looks:

###p

Before we move on to practice, let me briefly outline the steps in the procedure for transforming a given binary function into a quantum oracle. Let’s suppose we have a function with P input qubits and Q output qubits. We build a table in which there are (P + Q) columns, and the number of rows is two by the power of (P + Q). We fill this table with binary numbers from zero to two by the power of (P + Q) without the figures of one, that is, in the first row there will be only zeros in all columns, and in the last row there will be only the ones. We add another Q columns to the table, where we record the result of applying the function on the input qubits. After that, we add another Q columns to the table, where the bitwise application of the «Exclusive OR» operation is entered to the values in the columns for the output qubits and in the columns with the results of the application of the function. Next, we leave only the first P and the last Q columns. Now we convert each row into a decimal number from zero to two by the power of (P + Q) without the ones. Finally, we make a bit line of zeros and figure of one to each such number where the figure of one stands at the place that the corresponding number denotes, with zero place being the first on the left. As a result, we obtain a square matrix with dimensions of two to the power of (P + Q), filled with zeros, in each row and column of which there is one figure of one. This is the quantum oracle corresponding to the original function.

Practice

So, let’s move on to the practice. Who could imagine that your task for today is a creation of quantum oracles. Let’s take sixteen binary functions, that receive two bits and return one. Today we have already studied one of them – Exclusive OR operation. There are fifteen more others. Create a quantum oracle for each of them and after that try to summarize what you have. Find a consistent pattern that stands out in every sixteen obtained quantum oracles.

I hope you will not rush to make the task using a pen or a pencil, though it’s also possible. The easiest way to do it is using the same framework, that we have already started to implement. Write a function that receives a truth table on input and returns a quantum oracle. The more generalized such function will be, the easier it will be to program quantum computers. Though, in the process of implementation of such a###a href="https://en.wikipedia.org/wiki/Higher-order_function"> higher-order function you will surely have to sit with a pen and a pencil to define the general principle of quantum oracle creation and feel it deeply. So, go for it.

That’s it for today. We have studied the way of arbitrary function transformation into quantum oracle for its further use as a gate in the quantum algorithm. We have also trained to do it with the help of our framework. Starting from the next lesson we will learn the existing algorithms. See you. Bye.

After Richard Feynman has formulated the idea of a universal quantum simulator, the development of the quantum computations field was neither good nor bad. It was difficult for the researches to shift the paradigm; they were in search of formal descriptions and methods developing. And in nineteen eighty-five David Deutsch introduced a quantum algorithm for the first time, representing quantum supremacy over the traditional computational paradigm. This is a quite primitive algorithm for primitive problems, but it was a breakthrough.

Theory

David Deutsch offered such a task. Let’s consider a binary function of one variable. Only four of such different functions exist. The first one notwithstanding the argument value returns zero. The second one always returns one. The third one returns an argument value without change. And the fourth one, as you have probably already guessed, converts the value of its argument. The first two functions are called constant functions, two others are balanced functions, as they have the same amount of zeroes and ones. Attention, Deutsch’s task. There is a function. How to define whether the function is balanced or constant using just one function call?

You can say «What’s the point of this strange task»? And it really looks highly odd. Firstly, it does not have any applied significance. Secondly, it can be solved easily on a usual computer. The only thing you need is to compare the results of a prescribed function with each other and if they coincide, the function is constant, and if not – balanced. What’s the essence of it? The essence is that this algorithm shows quantum supremacy. Any algorithm in traditional computation paradigm needs two calls of a function we are checking. And Deutsch’s algorithm needs only one call. Yes, with one call it can determine whether the function is constant or balanced.

It’s obvious that everything is not that simple. Deutsch’s quantum algorithm doesn’t call the function, but uses an oracle based on it. And here is a question: how is the quantum oracle creation more effective than double call of the function in an ordinary algorithm? For Deutsch’s algorithm the question surely remains open. If we use an oracles library, the choice of one is a very effective process. If the oracle is created based on the function on the fly, this is more burdensome process. But for other quantum algorithms an automatic oracle creation is a more effective process. The more difficult the function is, the easier it is to create an oracle for it, than to call it within the ordinary computation model.

Let’s get to the algorithm itself. In Deutsch’s algorithm two qubits are used – main and intermediary one, both are in the original state. First of all, an intermediary qubit is affected by gate X, a quantum analog of NOT operation. After the action of this gate an intermediary qubit transits into |one> state. Then both qubits are simultaneously affected by Hadamard gate H that transfers qubits from basic quantum states into equiprobable superposition and back (it rotates qubits in bidimensional Hilbertian space for forty-five degrees). Now it’s time to call a function, transferred into a quantum oracle. After this single call the first qubit is again affected by Hadamard gate (and we don’t need the second qubit anymore, because it’s an intermediary one) after that it’s measured. Here we have two possibilities. If after the measurement we get zero – the function is constant, and if one – it’s balanced.

Isn’t that great? Despite the artificiality of the problem and simplicity of the algorithm itself, back in days it made a disturbance and a paradigm shift for many scientists and researchers. That is why it is studied first in quantum computations courses. But let’s think how we can expand this algorithm and make it more universal. Deutsch’s problem solution is not interesting. And what can be more interesting within such formulation of the problem?

In nineteen ninety-two David Deutsch and Richard Jozsa offered an expenditure of the original Deutsch’s algorithm for binary function of N variables. The function still returns one bit, but takes a few variables simultaneously. Within one call of the corresponding oracle you need to determine whether the function is constant or balanced. The algorithm scheme is absolutely the same as in the original Deutsch’s algorithm. But the thing is that this quantum algorithm will work for non-balanced and non-constant functions as well. It will show something like imprecise degree of confidence that the function is constant. The more zeroes and ones the result has, the higher the level of such confidence is.

Practice

Let’s move on to some practice. Our today’s goal is an implementation of Deutsch–Jozsa algorithm on the basis of Deutsch’s algorithm that is already implemented in the original code I’ve attached to this lesson. Since you have created a lot of oracles in the last lesson, start from them. Take a look how Deutsch–Jozsa algorithm works on binary functions with two input bits. After that you can try to create an oracle for a few binary functions that get three input bits and see how the algorithm will work on them.

We can call it a day, I think. I hope you felt the essence of real quantum algorithms on your fingers during the practical part. Because everything we did before this lesson in fact was a part of quantum information, but not quantum algorithms. And now you became familiar with them. It was Roman Dushkin. See you soon.

Hello, friends. We continue our course in quantum technologies in Udemy, and today we have second quantum algorithm, which made so much noise a while back.  I am Roman Dushkin, and I continue to guide you through the recesses of quantum reality. Let's deepen our understanding of quantum algorithms today and find out how you can easily find a needle in a haystack. Of course, we’ll do it using a quantum computer. Let’s go.

Theory

Grover’s algorithm was proposed by the American mathematician Lov Grover in nineteen ninety-six. In general, this algorithm is aimed at solving the equation f (x) = one by method of brute-force search for an arbitrary function f of X variables. As usual in quantum algorithms, this function is given in the form of a quantum oracle, which can be asked questions like «What is the value of the function f on the given values of the arguments». As you must understand, the solution of this task in the classical computing paradigm by method of brute-force search requires N, equal to two raised to the power of X computations.

A huge number of applied issues can be reduced to this simple task. For example, it is the search for information in the database by value, and not by a key. If we have N records, the search of a certain record by brute-force method on the usual computer will take N / 2 iterations at the average, and on the quantum computer it will take approximately the root of N iterations. It's not a great improvement of the effectiveness, but at least something. In addition, this algorithm allows you to solve arbitrary inverse problems, that is, find the values of the arguments of the function from the value of this function. And that is why this algorithm is valuable.

Let me explain on the simplest example. Let's say you have a phone book. It is sorted alphabetically by the names of the subscribers. If you want to call me, then find my surname quickly, and you will learn the phone number. This is a direct task, and it is solved quickly, when the surname, that is, the input argument, is sorted. And what if we have a phone number, and it is necessary to find out the surname of the subscriber? I should emphasize, that the phone book contains all the records, but they are sorted by surname, and there is no possibility to sort by phone number. So you have to look through all the records one by one and compare the phones. This is the inverse problem.

The algorithm itself is quite clearly expressed in the language of mathematical formulas, but now I will not give them to you. If you are interested, you can look for additional sources and study them thoroughly. In addition, this algorithm is described in detail with examples and implementation in my book on quantum computations. But now let me explain what happens during its application at the tips of my fingers.

Quantum oracle, which is created for the function involved in the Grover’s algorithm, allows you to identify the target state. We already know that if we send an equiprobable superposition of all possible values of the argument to such a quantum oracle, then there will be a superposition of the values of the function on the output. After that the so-called Grover’s «diffusion gate» is applied to the result of the work of the quantum oracle. This gate blurs the non-target values of the function, but amplifies the amplitude of the target values by means of interference. It is proved that if the quantum oracle and this gate are applied a certain number of times, proportional to the square root of the number of possible arguments, then the amplitude of the target value will be maximum. After that you can measure the input qubits, and as a result the solution will be most like returned.

Interestingly enough, if you apply the quantum oracle and the diffusion gate one more time after the implementation of the required number of iterations, everything will fail, and the probability of obtaining the correct result will be inverted relative to the average. This means that before running a particular quantum oracle, you should test it on known values to determine the exact proportionality coefficient for the root from the number of records. After this, the algorithm will be ready for operation.

Interesting enough, this algorithm will work also in case when the equation f (x) = one has several roots. In this case, you need to make the number of iterations equal to O from the square root of N, divided by the number of roots, and the algorithm will find some root of the equation. As a result of measurement, the wave function of the quantum system will collapse to one of the roots — equiprobably between all the roots. So, Grover's algorithm must be run over the ensemble of quantum systems to obtain the roots, and then the total number of runs will be the same O from the square root of N, as in case of a single solution of the equation. Everything sorted itself out.

Practice

That’s it for the theory. Let's move on to practice. Your task will be to implement the Grover’s algorithm for a function with several roots. I have prepared the necessary oracle for you, but your task is an analytical computation, or an experimental selection of the number of iterations of an oracle with a diffusion operator. After that, you need to issue some kind of a report in which you describe your observations about how the probability of obtaining a correct result changes after the implementation of the Grover’s algorithm with a given number of iterations, and also the conclusions — why this happens. Go for it.

We can call it a day. We have studied Grover's algorithm, another quantum algorithm that shows the supremacy over classical algorithms. The supremacy is not so great, nevertheless it exists. And in the next lesson we are going to study the algorithms that show a significant, exponential advantage over the classical ones. So, stay with us and see you again. Bye.

Hello, my friends. We continue to study quantum technologies in Udemy and today we have the final lesson in quantum computations. We have already learned to represent an arbitrary function as a quantum oracle, studied Deutsch’s quantum algorithms and Grover search algorithm. Though everything we have learned so far doesn’t show us that vaunted quantum supremacy. So, today we are going to learn Shor's algorithm that exponentially exceeds any algorithm realized in traditional paradigm. And that's an actual supremacy. Let's take a closer look…

Theory

Peter Shor has developed his algorithm in nineteen ninety-four. For seven years it was only theoretical phenomenon until in two thousand one in IBM company its work on a seven-qubit quantum computer was shown, by factorizing fifteen into three and five. The algorithm itself is a combination of classical and quantum computations and for factorization into prime factors of some number N, O (log N is needed) qubits and O (log three N) of time. It's much more effective than any other known classical algorithm, as the most effective of them factorizes the number for subexponential time. So, Shor`s algorithm has an exponential supremacy.

Why do we need Shor’s algorithm? As you already understood, it allows us to factorize numbers. It allows you to factorize very large numbers, and it does it really quickly. And the modern methods of cryptography are based, among other things, on the hypothesis that it is impossible to factorize numbers quickly. Some cryptographic methods are based on this assumption. In particular, the RSA method of asymmetric encryption, which is now used universally, is based on it. And if the quantum computer is large enough to implement the Shor’s algorithm for arbitrarily large numbers to factorize them, then all cryptography based on this assumption will be immediately compromised. The same applies to the problem of discrete logarithmation. The Diffie-Hellman secret key exchange protocol is based on its practical unsolvability. Shor's algorithm with some modifications allows us to solve this problem, that is, compromises the Diffie-Hellman protocol. That is, two basic primitives of modern cryptography will be compromised. It's terrible.

The Shor’s algorithm itself is quite complex, so that it can be explained orally. You need to read its description on your own and work through the source code of this lesson to obtain a deep understanding. Well, I’ll briefly explain how it works here.

Shor’s quantum algorithm, in fact, consists of two parts — classical part and quantum part itself. During the classical phase, certain parameters of the algorithm are selected for the factorized number, and a quantum oracle is created. This is performed quickly using known formulas. The task of the classical part is to prepare everything that is necessary to run the quantum algorithm. If you remember the general scheme of the quantum computers work, then this will not be a discovery for you.

When the parameters of the quantum algorithm are selected, it is launched. And it should be done several times on different ensembles of qubits, as we remember that quantum algorithms are often probabilistic. However, it can be done sequentially — as a result of the execution of the quantum part of the algorithm, factors of the number will be obtained, which can be multiplied and compared with the number itself. And if the result is unsatisfactory, that is, the required factors are not found, then the quantum part of the algorithm is started again. Actually, this is essence of NP-complete problems, which include the factorization problem - it is difficult to solve the problem, but it is very easy to verify the solution.

The quantum part of the algorithm searches for the period of function for which the quantum oracle is prepared. The period of function is a certain number. If it is multiplied by any natural number and added the resulting product to the argument of the function, then the result of the function will not change. Well, that is, if there is a function F, then F (x) = F (x + ri), where i is an arbitrary natural number, and r is the period. The quantum part of the Shor’s algorithm finds this period. After that finding simple factors of a number is a matter of technique and is quickly executed on a classical computer.

In general, the Shor’s quantum algorithm is not so simple, but it is quite possible to understand it. Re-read its description, and then go on to the practical task. And then, in the end, it will come together for you. I'll give you links to some additional materials at the end.

Practice

Let's finally move on to the practice. Your task for today is to gain insight on Shor`s algorithm, initial code of which I give. You should download a module with the implemented algorithm and then conduct the following experiment. You need to gather data on how many times you need to run the algorithm itself and how many times you need to run the quantum part for the factorization of the given number. We will choose a number twenty-one, because the power of every modern computer will be enough to simulate the needed quantity of qubits for its factorization. Draw a 3D graph based on the research findings — the correspondence of the possibility of a correct answer finding from the number of the algorithm launches and the quantum part launches.

That's it for today. We have discussed one more quantum algorithm, and now you can not only transfer arbitrary binary function into quantum oracle, but also complete three algorithms — Deutsch-Jozsa’s, Grover’s and Shor`s. Now you are more skilled than you were before this course. It was Roman Dushkin. See you soon.

Hello, friends. Today is our last lesson of an introductory course in quantum technologies. That’s great. Today you have more knowledge than you had two weeks before. I am glad about this, and my name is Roman Dushkin. Let’s summarize and I will give you a piece of advice…

For the last two weeks we have briefly immersed into four quantum technologies that are taking place in our life right now, right in front of us. Let’s list them to recall and repeat them. They are quantum sencorics, quantum transfer of information, quantum computers and quantum computations. Of course, it’s impossible to become an expert within such a short period of time, but today you can confidently orient in any piece of news and information connected with the theme. But for all those, who desire to immerse into this incredibly interesting theme I recommend to continue learning.

You need to start studying the basics of quantum mechanics. It’s not that difficult, as it seems. If you haven’t studied it at the university or somewhere else, I recommend you to start from the watching different Youtube videos, revealing the mysteries of this science. There are a lot of animated learning videos without any formulas. Watch them until you understand all terminology without the need to search in some additional sources. And while you don’t understand, watch videos and constantly address to Wikipedia. It’s the easiest and the most available way, which is also very effective. When I start learning any new topic, I do exactly like that.

The next step is specialized courses on such MOOC-platforms as Coursera, Udemy or EdX, where there are a lot of courses in quantum mechanics and even quantum computations. Moreover, there is a course on quantum computations from Umesh Vazirani on YouTube. One of quantum algorithm is named after him, and back in my days I have learned a lot from this person. I highly recommend his lectures. You need to know English on a very high level to understand them, but there are such courses in Russian as well.

By this moment you should already have the whole complex of needed associative links in your mind, to fully understand theses of quantum mechanics and quantum computations. To broaden it and make it simpler for yourself, start reading specialized books and self-teaching books. There is a huge amount of translated literature in quantum computations in Russian. And for future quantum programmers I recommend my book «Quantum computations and functional programming». It has one very important peculiarity – it’s written by a programmer for the programmers.

So, that is the end. We have studied for two weeks and you have learned the secrets of quantum technologies. That’s great. From now on the world will not be the same for you. You will see quantum effects surrounding you everywhere. Continue to study and you will reach new frontiers. Roman Dushkin and Quantum Technologies course in Udemy was with you. Don’t forget that we have many other courses, so check the website from time to time and continue to learn. See you.