A Brief Introduction to Quantum Computing [Part 1]

Have you ever heard about quantum physics and wondered if you could understand what this is all about? We see it in movies, in books, but why is it so popular? In this article, I will attempt to explain from a computer scientist perspective the basics of quantum computing and hopefully show that this is not as inaccessible as it might seem. I will assume basic knowledge about mathematical notation, computer science and programming.

Since a few years, we hear the terms “quantum physics” or “quantum computing” a lot more in the news. This is due to the fact that there have been some major advances, and mainly because some companies were able to build the first quantum computers! Suddenly, this brought a lot of attention to the field, especially from the media, and there are now many people who are interested to know more about it.

My goal in this article and the next one is to present the main ideas in the field so that you can:

• Learn the fundamentals of quantum computing.
• Register on the IBM Q Experience platform which will enable you to use an actual quantum computer.
• Create your first quantum programs using the Python programming language.

The Fundamentals of Quantum Computing

Computers help us in our daily lives to perform all kinds of computations and we often don’t think about what happens behind the scenes. In fact, millions of operations are being performed every second which allows the user to have a good experience.

However there are some tasks where computers tend to be slow. In particular, some mathematical problems are known to be extremely hard to solve even with the most powerful computers. This is what pushes researchers to always improve the speed at which computers solve problems. They try to improve the hardware used or the algorithms used.

Another way to solve that would be to rethink entirely how we compute. Could there be another way of computing which enables us to solve problems more efficiently than using just a simple computer? Well, quantum computers do have the potential to bring a kind of computing power that cannot be achieved classically, and this is why they are so interesting.

Quantum Bits

In the classical world, we use bits to represent information, 0’s and 1’s. With those two symbols, we can represent anything we want, which is useful as long as we attach meaning to each sequence. In quantum systems, we use qubits to represent the information. They act like the bits in classical systems except that they follow the laws of quantum mechanics. Also, the notation is a bit different. Instead of writing 0 or 1, we will write |0⟩ and |1⟩, the usual notation in quantum physics.

You may ask, why would these qubits be so useful for anyway, can’t we already compute things with classical bits? Well you are totally right, except that qubits do follow the laws of quantum mechanics and this enables them to potentially be a lot more powerful than simple bits. In particular, as mentioned earlier, there are some problems which are extremely difficult to solve with a classical computer, while a quantum computer is much more suited to the task and can yield a better answer.

To mention an example of a difference between bits and qubits, recall the story of Schrödinger’s cat. In this thought experiment, a cat is put inside of a box together with a radioactive source. Following the laws of quantum mechanics, what happens is that if we wait an hour, then there is an equal probability that the cat is alive or dead, so as long as we don’t open the box to verify it, the cat is both alive and dead. This is the concept of superposition, and the same can be done with qubits.

Superposition

So a qubit can not only be 0 or 1, but a mixture of both! In that case, we say that a qubit is in a superposition of these two states. So let’s say that we have one qubit, call it . Then the general way to write its state as a superposition of 0 and 1 (according to quantum mechanics) is , where are complex numbers. As a not-so-precise interpretation, this tells us that with probability (the modulus squared of ), our qubit is equal to 0, and with probability it is equal to 1. Since 0 and 1 are the only two outcomes, we of course need the probabilities to sum up to 1, that is we need .

For example, consider the qubit . In this case, we have that and , so that . This means (roughly) that with probability half, the qubit is 0 and with probability half, the qubit is 1.

Also as a side note, we said before that a qubit can generally be represented as , so a linear combination of 0 and 1. But this can be seen in the language of linear algebra simply as a vector . In fact, linear algebra is an essential tool in quantum computing, which is great news if you come from a computer science background. Indeed, there will be no need to understand too much of crazy physics theory, as everything can be abstracted to linear algebra. So get ready to use those matrices and vectors, we will need them! 😉

Measurements

Quantum is cool, but we understand things only on a classical level, with our classical bits. How to make sense of qubits in the classical world? If someone comes to you with a qubit, that is great but how can that information be useful if everything is in superposition? We do not have the capability to read such information. That is when measurements come into play. They allow us to measure the qubits by forcing it to “collapse” into either a 0 or a 1, a classical bit.

But then why bother with all this quantum machinery if in the end we get back simple bits? The answer is that we can perform operations on qubits, compute things using the power of quantum mechanics and in the end recover the solution to a problem in classical bits. This is this extra power which is useful to us compared to processing information only in a classical manner.

More Qubits

So far, we presented everything under the perspective of a single qubit. Of course, any meaningful system will handle more than one, potentially millions or billions of qubits! Thankfully, everything we presented earlier holds also in this case, the difference here is that the system can be in a superposition of not only 0 or 1, but much more complicated sequences. Let’s see this through examples.

First, consider a system with two qubits. In that case, there are four possible states of the system: 00, 01, 10 and 11. But recall that the system being quantum, any superposition of these states is possible (as long as the probabilities sum up to 1 of course)! So we could have the state , an equal superposition of the states 00 and 11. But we could also do an equal superposition of the four possible states and get the state .

In the same way, we can extend to three qubits or more, and get states such as . Note that in all these examples, the coefficients are always chosen so that the sum of their modulus squared sum up to one. In the last example, the three coefficients were , so that , so all good.

I let you make more examples with more complex systems in your head, but you should get the idea!

Entanglement

Ok, so this is a big one, entanglement. Wish me luck in trying to explain what this is. As a first attempt, let us display what Wikipedia says about entanglement:

“Quantum entanglement is a physical phenomenon that occurs when pairs or groups of particles are generated, interact, or share spatial proximity in ways such that the quantum state of each particle cannot be described independently of the state of the others, even when the particles are separated by a large distance.“

Source

Ok… If that is clear on the first read, I bow to you! Instead of trying to make sense of it just like that, it will be easier to go through an example.

So suppose one considers a two-qubit system and prepares it such that it is in the superposition . Then each qubit is given to two people, call them Alice and Bob. Each of them receives one of the qubit that makes up the system.

There is something particular about the state we have chosen. If we were to know that the value of one of the qubit is 0, then we would automatically know that the other one is also 0! Indeed, since the system was in a superposition of the states 00 or 11 but not anything else, we can deduce the value of one qubit from the other one. So in our little example, if Alice measures her qubit and gets a 0, she will already know that Bob will measure a 0. This is illustrated below.

Hopefully, re-reading the definition from Wikipedia will make a little bit more sense now. Basically, when a system of qubits is said to be entangled, this means that the state of a specific qubit depends on the state of other qubits in the system, it is not independent. Even if the qubits constituting the system were billions of kilometers away, we would still be able to get information about other qubits when measuring a specific one.

Next Time

Alright I will stop here for this article. I believe it is better to write smaller articles that are easier to digest, let me know what you think about it!

Today we saw what qubits are and how different they are from classical bits. In particular, we have seen that even if they are very similar to usual bits, there are concepts such as superposition or entanglement which only exists in the quantum world.

The question now is how can we harness the power of these new effects to solve problems more efficiently? How do we design programs to solve problems in a quantum way?

Next time, we will see how we can process qubits to actually compute meaningful things and you will also create your first quantum programs! See you in the next article… 😉

References

If you want to dive deeper in quantum computing, I recommend you to check out the following books:

• Quantum Computation and Quantum Information, written by M. A. Nielsen and I. L. Chuang
• Quantum Information Theory, written by M. M. Wilde
• Quantum Computing Since Democritus, written by S. Aaronson

These are great to learn the basics and go much further than that. There are also exercises which help get a good grasp of the content, so it makes it even better to learn. Of course there are a lot more books in the field but those are some of the most well-known ones.