Quantum Computing in Action

Intro

Preben Thorø: My name is Preben. I'm CTO at Trifork. And with me, I have Johan Vos, author of the brand-new book, "Quantum Computing in Action." And this is the GOTO Book Club. Welcome, Johan.

Johan Vos: Thank you very much for having me.

Preben Thorø: In front of me here, I have a few books about quantum computing, and I guess at least one of them, I would say, is a must-read within our industry. But your book is different from all the books here. Why, and how?

 

The evolution of computers

Johan Vos: Well, I think there are a number of great books about quantum computing. And that's very important because the work of quantum computing could not be done so swiftly as it's being done now if there was no sharing of information. Many people are active in the area of quantum computing, and they do different things. And if you look at how classical computing evolved, then in the early days, it was mainly about the hardware and about how to create a computer. And gradually, the focus also moved to not just the hardware, but also the software.

And then we had different computer languages. And on top of the computer languages, we created new computer languages, and then we created software patterns, and new declarative languages and so on. So the moment that the root problems are more or less under control, then people tend to go higher up the stack. And if we want quantum computing to be very useful in the end, I believe we need to do a similar evolution.

And that means that we have to slightly add more focus to the software aspects of quantum computing, by which I mean, how can we deal with existing software applications and still leverage quantum computing? So, at this point, there are tens of millions of developers worldwide using different languages.

And then the main question to me, and that's what I tried to address in the book, is, how can we allow these millions of developers to take advantage of quantum computing without requiring them to get a Ph.D. in Quantum Physics or so? So I really want all those developers to be able to leverage all the great work by people that wrote the other books, and that they are working on different aspects of quantum computing.

 

A kick-start for quantum computing

Preben Thorø: You said there are tens of millions of developers out there working with different languages. You decided to go with Java here. Why?

Johan Vos: Java is the language that I'm most familiar with, and it's still one of the most popular languages in the world. It's been around for more than 25 years, and it's still around. So I think it's a safe bet for the future. There are other languages that come and go faster. And I want this book to have a long lifetime, so Java is in that sense a safe bet.

It's also that there are about, at the last count, more than 12 million Java developers worldwide. And Java is used in many critical enterprise applications. It might seem strange that you want to use an enterprise language for a topic that's mainly popular in research areas, but I think if we want quantum computing to succeed, it means that it has to reach the level of enterprise software.

Throughout the years, Java learned a lot from being used in the enterprise. So, if we want quantum computing to be leveraged in enterprise software, then it definitely helps to use it together with a language that knows all the in and outs of enterprise software, that knows how to deal with security, scalability, code maturity and that also has a large developer base. And those Java developers are very familiar with a number of concepts. By bringing quantum computing to those concepts, I think we can give 12 million developers a kick-start.

That is not to say that there are no other languages that can benefit from Java, and I definitely think that C, C++, or C# are very good candidates as well. Python is obviously a great language to do research with quantum computing. But if we really want to bridge the gap between research and enterprise software, then I think Java is a safe bet.

 

Full Circle

Preben Thorø: If we draw a line back to the books I mentioned before, they seem to be centered around the cross field between maths and physics, maybe even philosophy. May I ask, what is your background?

Johan Vos: I have a Master of Science in Civil Engineering. Actually, I'm a mining engineer. And I have a Ph.D. in Applied Physics, which was done at the Faculty of Aerospace Engineering. So my Master of Science is deep under the ground, and my Ph.D. is high above the ground. So that's funny, and it actually means that my background is in combining different things.

When I started to do my Ph.D., that was on acoustic wave theory, I needed to do lots of calculations because there was lots of data, and I needed to do strong visualizations of this data. So I was searching for a language that could help me with this. And right at that moment, Java was released. I looked into Java and I wanted to do this on my Linux stations. There was no Java for Linux then, so I joined a small group called the Blackdown Team where we ported Java to Linux. And that's how I got into software.

I turned into software because I needed it for my scientific research. Then I got stuck in the software world and I went from one challenge into the other, mainly software related. But the real background on why I wanted to do this is to be able to process scientific data, to visualize it and to move things forward, that is something that I always liked. And with this book about quantum computing, with the strange quantum computing simulator that I wrote, I think I've gone full circle.

 

How much physics & math is needed to understand the book?

Preben Thorø: So you ported Java to Linux. We need to have a conversation about that one day. Sticking to your book, how much physics, how much math do I need to read it and to understand it?

Johan Vos: That's a good question, and it's a question that I was asking myself every other week or so. When I started the book, Manning wanted to have the description of what I call the MQR, the Minimal Qualified Reader. So, what does the reader needs to know? And I know that if the basic requirements from a mathematical point double, then the potential reader target will be divided by four or so.

I tried to avoid the mathematical requirements, and not just because I want to have more readers, but also because I don't think it does matter to most of the developers. You don't need to have a mathematical background to read the book and to run the samples. You don't need to know much about physics, everything about quantum physics. But for the interested reader, there is more background in the book about, why are things the way they are.

For some developers, it doesn't matter. They just say, "Okay. So, with this algorithm, I can search through a structured list in polynomial time,” for example, which is not entirely true. And for others, they want to know, "Why is this quantum approach much faster than the classical approach?" And then it is explained with some very basic mathematics. But we don't go deep into the mathematical details.

In order to write the book and the software behind it, I had to deep-dive into mathematics and physics myself. And that's actually the best way to learn it. As I just read another tweet from the Richard Feynman Twitter account. And he says, if you want to understand something, then teach it. So, if you really want to deep-dive into the algorithms in the book, then the book will also help you with the mathematics, but it's not required.

I think that many Java developers, or many enterprise developers, are interested in it, but it’s mainly something that they do out of interest and not because they need it to get the job done.

 

Polynomial time and exponential time

Preben Thorø: I completely agree. The best way to learn is to teach. Yes. Let's dive a little bit into the material of the book. What is polynomial time? What is exponential time?

Johan Vos: That is one of the major aspects of quantum computing, that it can deal with some problems that will typically take exponential time, where quantum computing can deal with polynomial time.

To try and explain it briefly: If you have a problem, and you have an algorithm that will solve the problem, then typically, the bigger the problem, the longer it will take before you have a solution. For example, if I have to sort 10 numbers from high to low, it will take some time. If I have 100 numbers, that will obviously take much more time than solving the 10 numbers. And the amount by which problems become more complex if the input parameters become larger, is expressed in the time order of that problem.

There are some problems that are of exponential time with the best known classical algorithms, which means that if you have a classical computer and it can solve a given problem in two minutes, then by making the problem three times as hard, it will require, for example, eight times more time. And by making it four times as hard, it might require 16 times more time.

I think most people understand by now what exponential behavior is, because of the coronavirus, unfortunately, also multiplicates itself using exponential behavior. And, again, unfortunately, most people now realize that if something seems to go slow in the beginning, it can go extremely fast when things get more complex.

This is a bad example of exponential behavior, but a good example is, for example, in cryptography. When we want to create cryptography keys we see that if we make them very small it's easy to hack them. But if we add a few bits, then it becomes harder and harder, and it becomes exponentially harder. So that is a problem that we can, I'm making some shortcuts here, define as exponential time behavior.

Now, on a quantum computer, some of those non-polynomial problems might be executed still in polynomial time, which means that we make the problem harder, and the quantum computer will need more time to solve it, but not exponentially more time. For example, if we make the problems four time as hard, it might take eight times more time. But if we make it 8 times as hard, then it might take only 16 times the original time. It will still become more complex, but it won't behave like this exponential curve that we all know so well now.

That is a game-changer, because some problems are known to be of exponential complexity, and they cannot be solved with even the biggest supercomputers in the world. Even if all the classical computing power is combined, those problems are too hard to solve. And a quantum computer might be able to solve these very, very hard problems.

A typical example of this is encryption. I want to stress that this is a very important example, but it's definitely not the only application of quantum computing. With the best classical computers, it's nearly impossible to break strong RSA encryption. But with a quantum computer, it is possible once the quantum computers are powerful enough, which may take a long, long time. And more important, by adding a few bits, the classical problem would become exponentially more complex, but in quantum computing, just adding a few bits is not gonna make you exponentially more secure.

It's a thing that's hard to explain. And, therefore, I use the example of encryption and the coronavirus because I think people can somehow understand what it means if a problem is exponential.

 

Difference between classical and quantum computing

Preben Thorø: And I think it's important to emphasize that the quantum computer is a calculator. It's not just a supercomputer, it's a calculator. And it's very suited for specific types of mathematical problems. So the idea is that you have this problem with a huge complexity. It can transfer it or turn it around, move it into the quantum space, and then it becomes solvable for the quantum computer. And in order to do that, we need to understand quantum gates, for instance. What is a quantum gate?

Johan Vos: Like a classical computer consists of a number of gates, a quantum computer consists of gates as well. In classical computing the high-level programming languages are built on top of low-level languages, and on machine coding, and ultimately it's based on the flow of current that passes or not passes to a transistor. The gates there are then, for example, the NOT gate that will invert zero into one, and vice versa, or an AND gate, XOR gate, and so on.

In quantum computing, we have gates as well. That concept can somehow be compared to the concept of classical gates. The main difference, though, between quantum computing and classical computing is that in classical computing, we use bits, where a bit can have the value of zero or one. Zero means no current, and 1 means maybe 5 voltage or so.

In quantum computing, we don't use bits, but we use qubits, where a qubit can hold the value of zero, it can hold the value of one, but it can also hold a linear combination of zero and one. And that's not to say that it can be, for example, 0.7. It actually means that when I would measure this qubit, there's maybe a 30% chance that I will measure a 0, and a 70% chance that I will measure a 1. So you can measure zero or you can measure one.

Whereas in classical computing, it's always clear that it's either one or the other, and in quantum computing, we talk more about probabilities. The gates that operate in quantum computers deal with these probabilities. Therefore, if you apply a gate to a qubit, the qubit is still there, but instead of just two states, the qubit can be in many states.

That makes the gates a bit more tricky to create in quantum computing than in classical computing, but it also offers performance improvements, because what you said is exactly the point. Quantum computers are no supercomputers. It's not that they do more calculations. It's just that, and this is scientifically not really correct, they are able to do many computations in parallel. 

 

In quantum mechanics, everything is reversible

Preben Thorø: That leads me up to the next question here. So, quantum gates need to be reversible. Is that a quantum mechanical property or is it more like a definition that we have made?

Johan Vos: It's actually what nature dictates us. And that is another important difference between quantum gates and classical gates. A classical gate is more or less human-made. So, we created, in biological terms, a huge device named transistor, which is a few nanometers, but it's huge compared to the world of very small particles. And the elements that we have in quantum computing are elementary particles.

In quantum mechanics, everything is reversible. Well, it's because of the laws of quantum mechanics that the equations hold in both time directions. And as consequence, if you want to use the fundamental cornerstones of nature to create a computer, whatever we do there must be reversible, as well, because the elements that we use are reversible. If we are thinking about a gate, we have to take into account that if we want to create this gate with building blocks from nature, that the gate needs to be reversible, otherwise we can't construct it.

It is a challenge because it makes some gates harder. For example, a classical gate, an AND gate, has two inputs and one output. We can't have that in quantum computing. If we don't have the outputs, we can't go back to the two inputs because there are many, in the case of two input bits and one output bit. And if one of the input bits is zero, the other is one, the output is gonna be one. But you can't go back and say that the first input was one or the second input was one. That information is lost if you apply the classical gate.

Therefore, that is something where that gate is impossible to realize in quantum computing. Of course, you can do arithmetic in quantum computing, but then you need slightly different gates with two output qubits, for example, where the second qubit has the information that otherwise would have been lost.

 

Quantum black box

Preben Thorø: And I need to say to the readers here that all of this may sound very abstract, but trust me, if you read the book, it all makes sense. Talking about the gates, it leads me into another question, and that is the oracle. What is an oracle?

Johan Vos: Apart from being a software company, an oracle is very relevant in quantum computing because it is sort of what I call a quantum black box. It is something that is given to you by someone else or by a phenomenon in nature and you don't know what is inside it. And you actually are not interested in what is inside it, but you want to know its characteristics. You can't open that black box, but you can query it, which means you can provide some input and you can measure the output.

When you know a quantum oracle, for example, has five input qubits and has also five output qubits, you can try different combinations of qubits, and you can then measure what that oracle gives as an output. Based on the input/output parameters, you can more or less understand what is happening inside that quantum oracle.

And that is, well, comparable with the black box. A basic example for this, which is discussed in the book as well, is, suppose that you have a classical function that will always be either balanced or constant. This means that it will either give half of the times as the result of an operation zero and half of the times, it will give a one. In that case, we call that a balanced function. And a constant function is when it will always give a zero or it will always give a one.

When we are given a function, but we don't know if it is a constant or a balanced function and suppose that we have eight different input scenarios. Then we need to do at least five evaluations of this black box function before we can tell with certainty if the black box is hiding a constant or a balanced function. Five evaluations because after four evaluations, we might still have four times zero. But it can be either the fifth, sixth, seventh, and eighth will give a one, in which case it is a balanced function.

You can create a quantum oracle that's mimicking this classical function. But you can prove that you need only one evaluation if you have two qubits and it adds to that. But the thing is that in quantum computing, you can send, instead of trying first all zeros and then all zeros, and one, and then different combinations, you can send more or less all combinations at the same time by putting the qubits in what is called a superposition, which is the qubits then have as value, a linear combination of zero or one.

They can be measured as zero or they can be measured as one. If all those qubits are in a superposition, you send them to the oracle. I know that if there are real scientists reading, they might say, "No. It's not really happening," but I tried to make it visually more comprehensible by taking some shortcuts.

I would say that you can compare that the oracle is evaluating all the possibilities at once, and it will then give one outcome. And that's where the speedup comes from. Instead of evaluating all zeros and then all ones, or so, it evaluates all options simultaneously. And that is why a quantum oracle is often used for dealing with complex applications because you can understand what is happening inside the quantum oracle by feeding it a specific configuration of qubits where superposition is extremely important.

 

Quantum simulator

Preben Thorø: And, trust me once again, all of this makes sense once you read the book. I'm going to leave this as a cliffhanger here that this is very important for one of the most famous algorithms, Grover's search algorithm, understanding quantum oracles. And all of this has been supported beautifully by the code examples in the book, which leads me to your claim pretty early in the book, that by using this quantum simulator, we will be able to write programs. And the day we have quantum hardware, it's pretty much just changing a variable, and then it runs on real hardware. Is that really so?

Johan Vos: Yes, absolutely. That was one of the most important design goals. I think it is extremely important, and it is very well possible now because of the long history that we have in classical computing with computer languages like Java. In Java, you do not program against a specific implementation, but you program against APIs and interfaces. So the Java developer uses the top-level Java APIs to write an application, and it does not matter then if that application is ultimately being executed on a Windows system, or a Mac, or Linux, or an embedded device or mobile device. It's under the hood.

The instructions from the developer are translated into low-level machine-specific instructions. And this holds with Strange as well, the quantum simulator that I wrote. It will, by default, search for the quantum simulator that it's bundled with, but it can also run your application on a different execution environment, which is called the quantum execution environment. And those execution environments will translate your application into something that's specific for a specific execution environment.

An execution environment can be a real quantum computer, which I don't have right now, but it can also be a quantum simulator that is running on your local desktop, or it can be a quantum simulator that is running in the cloud. That is what makes it powerful and future-proof, that the moment that a real quantum computer is available, your application does not need to change. Because the gates that your application is using have representations in both simulators, cloud computers, as well as real-world quantum computers. That is actually the root idea of Java, WORA, write once, run anywhere. And that is what we bring now to quantum computing as well.

And that is not extremely new, by the way. One of the other projects that I'm the coordinator of is the OpenJFX project where we define the Java APIs for user interfaces. The implementation of that project will use the GPU if there's a GPU available on the device that you're using, on your laptop, or desktop, or phone, or so. And if there's no GPU, it will use the CPU and will do software emulation. That principle is exactly the same as what we do in Strange with quantum computing.

We could search if there is a real quantum processor, and if so, we are going to use it, and otherwise, we use the software fallback. That is something that we learned by doing software many, many years, and that we can now leverage to make quantum computing already possible even before we have real physical quantum computers. Which is extremely important, in my opinion, that we start working on quantum computing now, and not just wait until the moment that there are many powerful quantum computers.

 

Be ahead of times

Preben Thorø: That is actually my next question. You revealed that we don't have quantum computers yet. So, why should we care now?

Johan Vos: There are a couple of reasons for it. I think it's important to realize that even if you're extremely smart, it will still take a while before you come up with the best ways to introduce quantum computing in your applications. You need to think in a different way than you think when solving classical problems. It is a totally new way of thinking. 

And you need to understand when quantum computing can be applicable and when it is not applicable. So that's also something I want to make clear. Quantum computing is not applicable to all kinds of problems. So there are definitely problems that a quantum computer will never be able to solve in a good way.

To find out which parts of your existing or new software should benefit from quantum computing is gonna take time. And time might be critical. For example, it's not certain yet, but if quantum computers will one day be able to crack RSA encryption, then you don't want to wait until that point before you start looking into your encryption. You can use quantum computing to create secure communication, but you can't switch overnight.

For example, if it's announced, and I don't think there will be a big announcement when a company, or a government, or a nation has a powerful quantum computer that can breach RSA encryption, and the next morning, your encryption is not using classical encryption standards anymore, but is using quantum encryption. That's gonna take a long, long time. And even if it's gonna take a long time before quantum computers can do that, it will also take a long time before your organization will be ready for it.

I often compare that with the Y2K bug, the Millennium bug, where it was clear that at December 31, 1999, there would be a problem. Companies didn't wait until December 26, 1999, at least most companies didn't wait. Some waited a bit long, but most were prepared ahead of time. That effort started years in advance and it was actually very needed. The reason that we didn't see many problems with the Y2K bug is that exactly these companies started to prepare years in advance, investigated their existing software, searched for vulnerabilities, and came up with solutions ahead of time. There was the advantage of you could predict very well when the Millennium bug would happen. It's a bit harder to predict when quantum computers will be powerful enough to break encryption.

But it's not only a negative story, it's also a positive story. Imagine that there are quantum computers powerful enough to do great things in medicine, healthcare, chemistry or physics. You don't want to wait until that moment before you start thinking about, "And, how can I then write software that will take advantage of this?"

Therefore, it's already good to start thinking about the software now, start writing algorithms and run them on a very small scale, or on a quantum simulator. Because if you can prove that the new algorithm on a quantum computer will require polynomial time instead of exponential time as we discussed in the beginning, then you know that you're on the right track.

Then you know that once quantum computers are there, that your software will be very, very usable. So, there's no reason why this software research cannot be done in parallel with the hardware evolutions. And if you want to get a head start for when quantum computers are really available, then you better start yesterday working on the software.

 

The billion-dollar question

Preben Thorø: So let's stop circling around the big question. Let's go into it. When will we have quantum computers?

Johan Vos: I keep circling around. This is the billion-dollar question. Actually, the unfair answer is easy. We already have quantum computers today. There are a number of quantum computers. IBM even has a few quantum computers in a public cloud that you can access. Google has a quantum computer.

Preben Thorø: Do we have useful quantum computers? Let's put it that way.

Johan Vos: This is the point where I will be crucified later probably. I think, between 5 and 10 years from now, we will have quantum computers that will really be able to solve problems that are totally unsolvable today. And that will be a complete game-changer. But between now and then, there will be other applications of quantum computing that will be very useful. I personally think that in the not too distant future, we will be able to benefit from the quantum internet. And that combined with small quantum computers can drastically change the way we think about encryption.

For example, at Delft University of Technology, there is a consortium working on the quantum internet, where entangled qubits are sent to two different computers. Even if those computers are very small quantum computers, because they are connected with each other on a quantum internet, they might become more powerful. And especially there are many things that you can do even with just a few qubits. I think that it won't take five years before we are going to see practical applications on a limited scale of quantum computing.

The big things like, for example, solving the protein folding problem, or breaking RSA encryption, it cannot take more than five years, I think. But you never know what's going to be invented. That is also one of the main reasons why I really want all those tens of millions of developers to look into quantum computing and to learn about it, because maybe one of these readers has an idea and says, "Hey, but if we can actually find the periodicity of a function with this algorithm, we also might use this for this or this problem."

That will then be a dramatic boost in some material design or in some medical investigation. And so it's a new world, the world of quantum algorithms, and the more people are working on this, the better. Some of these problems require thousands or millions of qubits, but maybe some can be useful with fewer qubits. I believe that there will be problems that will lead to immediate benefits without requiring millions of qubits.

Preben Thorø: Thank you. It has been so inspiring speaking with you, and just as inspiring reading your book. Thanks a lot. Thanks for joining us.

Johan Vos: Thank you very much for having me here. It was great.