Learning quantum programming in Python with examples. Yandex Report
- Hello everyone, my name is Rishat. I have been working on Yandex search quality for almost three years. But today I want to talk not about work, but about what I do in my free time. I am engaged in quantum informatics, but in fact - a variety of computational models, including quantum ones.
Quantum computer science is an interesting field now. A lot of effort is invested there, a lot has been done. In the report I will try to interest one of you. Maybe there is a cool ML engineer among you who wants to engage in quantum machine learning, or just a strong algorithm specialist who can invest his efforts in this direction. It will be great, because the future will come soon.
I must say that I'm not a physicist. Surely there are people among you who in the physics of all these processes understand more than I do. Therefore, I will not say almost anything about physics.
I expect from you that you remember algebra quite a bit, remember what a vector is and how to multiply a vector by a matrix.
How will my report be built? First we’ll talk a little bit about history, about where everything came from in order to look confidently into the future. Then we’ll see where it can be applied, what the state is now, whether something can be done with your hands right now. We will write the first Python program that can be run on a quantum computer. And then, as a bonus, I will show you some examples of algorithms in which quantum computing helps to achieve an incomparably better performance compared to classical ones.
How did it all start? Here from this young man. This is Alan Turing, he can be safely called the father of computer science or computer science, the one through which we all live, make money. In the 1930s, Turing came up with a computational model that we would now call a programmable computer. Does anyone recognize this person?
Already more difficult. His surname very often goes next to the surname of Turing. This is Alonzo Church, he also dealt with computability problems, and even a little before Turing he came up with his own computation models. But Turing's works became more popular. And in general, Church was at one point Turing's supervisor of studies. Taken together, their surnames are usually associated with this thesis.
Church-Turing thesis says: any process can be effectively modeled on a Turing machine. This is the end of the 30s - the beginning of the 40s, and everything is very good. For about 30 years, everything is very good, until these two people appeared. Does anyone know them?
This is already the 70s, very close to the present. Their surnames are often found in cryptography courses. These are Robert Nightingale and Volker Strassen. These two people are famous for the fact that they came up with a probabilistic algorithm for checking numbers for simplicity, the Solovey-Strassen test.
And this is a very important point for us, because so far we have said that any algorithmic process can be modeled on a Turing machine. But now it turns out that their algorithm cannot be modeled. It is probabilistic; there is nothing of the kind in the Turing machine.
I had to make a quick fix and say that any process can be modeled on a Turing probabilistic machine. This is not very cool, for sure one of you in the chest also pinched. You thought: how so? Now we say "probabilistic", in ten years they will open something else, they will have to edit something else. This is not very nice. But we, of course, are not alone.
There was another young man - David Deutsch. And he also wondered: how so? How to live? He is a physicist by training, devoted his whole life to physics. And I decided to deal with this problem precisely from the point of view of physics. He said: let's try to justify, to get some such that nature itself tells us that this is exactly so. And nature already said then (and we still believe) that it is quantum-mechanical. Therefore, we began to search for the answer in quantum mechanics. And it was with David Deutsch, with his first algorithms, that quantum informatics began.
This is such a small digression into history, so you understand: it did not come out of the blue. In this region there are real problems, theoretical, of course, which torment the people with whom it all began.
But is everything only at the level of theory? By and large, from the point of view of mathematics, there were no problems. From the point of view of mathematics, we know everything about how a quantum computer should work. Now there are already real quantum computers of various configurations, working differently. And this, by and large, is an engineering task.
For example, we have an entire department at the institute that deals with quantum informatics. There are both mathematicians and physicists. Physicists are now very closely engaged in the problem of long-term storage of quantum information. This is very similar to our hard drives, but I want quantum information to be stored there.
What can be the applications of this whole economy? Of course, the first thing that comes to mind is the modeling of processes, because the world is quantum-mechanical. And if we use a quantum computer to simulate processes, chemical reactions, or anything else, it will cost a lot cheaper in terms of computation.
The second and very large section, which is now devoted to a lot of forces, is quantum machine learning. There is a great hope that quantum computing will help to speed up the learning process itself and improve the algorithms. There is a lot of work. Now, for example, our quantum group is working with a scientist from China. He is a very strong ML engineer, and we are a little quantum-minded, trying to come up with something together.
The third thing a few months ago was a bit hype. Now, maybe the hype has already slept, but there is even a whole quantum blockchain. It was invented by my good friend and great friend. This is so, I say a little proudly.
But we do not have a quantum computer. Unfortunately, we cannot come home and it is as easy as we program in Python to run programs.
What to do? About what to do, I was thinking in my third year when I was writing my first term paper. I wrote a quantum computing emulator. Of course, everyone writes emulators and everyone uses them somehow. In my fourth year, I wrote an emulator that simulates interference, noise, and all that jazz. And then I got tired.
I tried searching in a search engine and realized that there were many emulators. Here are a few links, they are quite simple and interesting:
But I want to focus on qiskit. He is special, stands out from everyone. What?
It works in two modes. The first is, like everyone else, a regular local emulator. The second is running your program on a real IBM Q quantum computer that looks something like this.
Now it is a whole barrel in which an extremely low temperature is maintained - about three millikelvins. It is very cold. And IBM provides the ability to connect and run your code directly on this machine using cloud technology.
Of course, he compiles commands and everything else in a special way. How does it even work? For general access, there are several installations of such a computer. One of them is 5-qubit, there is 15-qubit, 16-qubit, even 20 qubits are available to us. This is about 20 bits of ordinary, classic information, but already something.
Here, for sure, many of you think: everything, I want! But you have to remember a little math. A bit of algebra, but just a little bit, as I promised.
To start programming on a quantum computer, you need to understand what qubit is. It is just a vector in two-dimensional vector space. But since we are talking about vector spaces, they have a basis.
The basis looks something like this. There are two vector columns and a single basis, the standard one, in algebra courses it is denoted as follows:
. And there is a standard notation in Dirac notation, here in such angle brackets.
That is, so that you do not get confused, I will continue to reduce so.
And since this is a vector, its state can be written as follows. The qubit q is a superposition of two basis vectors, where α and β are complex numbers, but not quite any, and so that the sum of the moduli of their squares is equal to one.
If we try to draw this thing, we get that the qubit is a vector on a three-dimensional sphere. An infinite amount of information can be stored in one qubit, because this is just a vector, of which there is infinitely much.
You can not pay attention to the picture, it's just a way of visualization to attract attention.
We talked about qubits. Most importantly, a qubit is a vector. Vector in complex vector space. What can you do with it?
The first thing we used to do is try to calculate the value of our variable, for example, in Python. We want to read what state the qubit is in. But we will never know the exact value of α and β.
If we try to look at the qubit, read, then we will get either a zero or one with corresponding probabilities. Probabilities are simply projections onto the corresponding basis vectors.
The second thing we can do is, for example, clone a qubit. We call this the assignment of one variable to another. In the quantum world, this cannot be done, unfortunately.
There is no assignment operation, and this is very related to what I just said: we won’t even be able to see the exact value. This is a fundamental result. He proved to be very just : literally two lines of comparisons, on the contrary.
There is a qubit that we cannot read, cannot clone. What can you do at all?
The qubit is a vector. The vector can be taken and twisted around the sphere. To spin, you can come up with a matrix that does this rotation. All operations on qubits are matrices. They are called unitary.
Unitary - in order to fulfill such a condition, it is written down here in a cunning way. This icon means transposed and complex conjugate matrix. The property is very important, it means that for any operation there is the opposite. That is, no matter how we twist the vector, we can always return it to its previous position. There is always the reverse operation.
Let's see what operations can be. What we are used to in the classic case. There is a toe, you can turn it into a unity and vice versa.
This is the negation operator, it is very simple. It is recorded here with such a matrix. If we try to multiply, we get exactly what we want.
I have even drawn here. Nothing complicated. The negation operator has a standard notation, the X operator. If you think about it, it's just a rotation around one of the axes. And there are operators Y and Z, rotation around other axes, but this is not so important right now.
And we can already run our first program on a quantum computer, which will do the negation of qubit.
But we in quantum computer science, of course, very rarely write in Python. More often we use schemes.
The circuit usually looks like this. Horizontal lines are just qubit values. I have five of them painted here. And in the block - the operation that we will do.
The first block. Here is a measuring device. This means that we just want to measure what is in the first qubit.
If we run this thing, we get that with a probability one we have a zero there, because they are initialized in this state and we did not do anything else with them.
Such a thing can be written in Python using the qiskit library. Let's take a look at the lines of what is happening here. First, we start a quantum register. Here I am bringing him from one qubit. And the classic register. A classic register is needed in order to record the measurement result somewhere. That is, I make transformations with a quantum register, the result is a classic - zero or one. And then I create my own scheme, in which there is this quantum classical qubit. I just say: let's measure the qubit q in C. Run this whole thing, and everything will be fine.But an attentive reader will see: it says here that my backend is a local emulator.
You can do the same with IBM Q, but there is a bit more code. There’s all sorts of noodles about choosing a device that will respond to us as soon as possible, some tokens should be passed, that's all. But there is nothing tricky.
The same can be done with the negation operator. This is operator X, as I said. It looks exactly the same in the diagram, run the same thing.
Now, with the probability of unity, we get the unity, as planned. No magic.
The code is the same. Just here, I still apply the operator X to qubit q.
Ok, let's try to go further.
There is a very tricky thing here. Let's try to get such a state. This condition is very interesting. We get such a superposition. If we try to measure it, then with a probability of ½ we get either a zero or one. That is, it will be such a uniform superposition, we can get anything.
We can draw an analogy that this is a quantum coin toss. We will say that okay, with a probability of ½ we get a zero and one. The matrix looks like this.
It’s easy to check, but we certainly won’t. Let's draw a diagram. Operator H in honor of Hadamard.
Measure and get about what we expect. Approximately with probability ½, zero and one. A little more, a little less, but it just so happens.
Here is the Python code, just to be, we are at the Python conference.
There is such a superposition. We apply the Hadamard operator to it and measure it.
But a coin can be thrown twice, we are all used to it. If you throw a coin twice, nothing will change. Let's try to do this in the quantum case.
We apply the Hadamard operator two times in a row and always get a zero.
That is, if you drop a quantum coin twice, you will always get a zero, because the Hadamard operator is inverse to itself. If you multiply yourself by yourself, you always get one. Here is such a thing.
So, with one qubit you can do something. You can twist, twirl and measure. Let's try adding more qubits. What are we used to doing in the classic world? Take and perform simple logical operations, "or" and "and."
This cannot be done in the quantum world, because they are not completely reversible. That is, getting zero in the operation “and”, we can never find out what the initial values were.
And in the quantum world, as I said, an operation is a unitary matrix that is always reversible. How then to program? Everything we are used to is crumbling. But a new hero appears, this is the operator of the so-called controlled negation.
If we wrote in Python, it would look like this. If the first qubit is one, let's invert the second qubit. This is not a matrix, this is how the operator looks. But in principle, what I said is written here. Where there is one in the first qubit, the second is inverted.
The matrix is already four by four. For two qubits, it looks like this. I’ll leave the task with an asterisk to multiply and see that this is true.
This thing can even be programmed. No rocket science. You just need to take, create a circuit with two qubits, with two classic ones, and make, not CNOT, but CX, controlled negation.
Negation was the operator of X, so basically everything is logical. And you can draw a diagram. The scheme is as follows.
That is, controlled negation is such a plus on the qubit that we want to change. And the dot, which is the control. Here, if the qubit is in the unit, then we will change the second.
Here I intentionally first invert the first so that it is one, and then measure both and get the result | 11⟩. Everything is as we expected.
But now is the time to use all our knowledge together.
Let us take all three or four operators that we know, we will patch into one scheme. That is, we apply the Hadamard operator to the first operator. We invert the second, then all together, make a controlled negation and measure it.
Let's not run it yet, but try to guess what happens.
If we apply the Hadamard operator to the first qubit, and negation to the second, we get such a superposition. I don’t want to waste time checking now, it can be easily multiplied. But the position is very interesting. Firstly, it is very similar to uniform, and secondly, now this state is called confusing, if we take a controlled negation.
The condition is confusing. And why? Let's try to make a measurement. Look, if I measure the first qubit and it is in my state of zero, then I can say that the second qubit is necessarily in the state of one.
That is, if I make such a transformation with my qubits, I will give one qubit to my friend, he will fly to New York, and I will measure the second qubit at home, I will know exactly what state his qubit is in. This is called the effect of quantum entanglement or quantum connectedness. And this is the main mechanism by which quantum computing works. It will change, they are connected very tightly, and during the measurement we can only get | 00⟩ or | 11⟩.
On this occasion, there is a very interesting illustration in favor of one scientist, Austrian, in my opinion, who was very absent-minded.
The distraction was that he always wore different socks. And colleagues joked about him: if he enters the room with one foot and we see that the sock is pink, then we can say for sure that the second sock is not pink. So it goes.
If we run this thing, we get exactly what we want. It is already quite funny happened. The probability is exactly 0.5, but this is a coincidence.
If we honestly run on a quantum computer, we get this picture. It seems that we say: the state | 00⟩ can never turn out and the state | 11⟩ can never turn out. But it still turns out: the current state of technology is such that there are noises that can not always be easily suppressed. And they are fighting it.
But if you recall classical computer science, the same thing is there: codes that correct errors and all that. Just the qubit is still too small to spend extra bits for fixing errors.
Now, as I promised, a few examples of algorithms. But these will be just unsubstantiated examples without analysis of the algorithms so that you look, think, become interested.
The first algorithm is just connected with Deutsch, which we spoke about at the beginning. This is the Deutsch-Yogi algorithm. And he does the following. Imagine that we have a Boolean function of n variables. And we know for sure that it is either constant or balanced. Balanced means that it is equal to zero on exactly half of the arguments, and to unity on the other half. Let us try classically to check whether it is constant or not.
To do this, we need to check at least half of all possible options: 2 n – 1 +1 option. The quantum algorithm allows you to do this for n calls to the function itself, for n calculations of the function itself. This is an exponentially lower number of hits.
The second example is probably well known to everyone, because of it they say that quantum computers will break all cryptography: we can factor numbers very quickly quantum.
Here are estimates of complexity, and there is just a fantastic example. In 2011, the number 15 was factorized on a real computer. It took seven qubits.
But not everything is so scary. In case quantum computers reach a level where RSA can be broken, there is already post-quantum cryptography. It is built on learning with errors. This is when a small error is introduced into the tasks so that it was very difficult to find the answer. Usually these are some kind of equations or a system of equations. Here is an example algorithm. Whoever wants to can read more.
Most interesting: the New Hope algorithm is based on this thing, a new hope for all of humanity. In 2016, Chrome had enabled support for this algorithm. There is a link to the blog. This is not what I came up with, everything really is. The future is here.
At the end, a few links:
- A great tutorial to get you started: Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information. The book is very thick, it is in Russian. There you will definitely find answers to all questions.
- IBM Q: quantumexperience.ng.bluemix.net
- IBM Q User Guide: quantumexperience.ng.bluemix.net/proxy/tutorial/full-user-guide/introduction.html
- Qiskit: qiskit.org
- A bit of science:
That’s more or less all. I just want to add that about 50 years ago, when Deutsch started doing quantum computer science, computers were big. They were made by several companies. They were the size of a closet. And now about the same companies are making large quantum computers. And what will happen in 50 years, of course, we don’t know.
If you try to drive in your favorite search engine, then today you can find vacancies for a quantum programmer. Of course, there is more research, but nonetheless. Thank.