Understanding Quantum Computing for Software Developers

Quantum computers are a new generation of computers based on the principles of quantum mechanics. It is a technology that is still very much in its infant stage but has the potential to have a severe impact in areas like cryptography, drug development, machine learning... It promises to solve problems that are impossible to solve using our current computers. They are claimed to have the potential to be "millions of times more powerful than today's most powerful supercomputers". That's a pretty bold statement. But how?

Most articles online that explain quantum computing, either rely heavily on math or limit themselves to meaningless high-level statements like "a qubit can be 1 and 0 at the same time". If you are anything like me, then you are left with a million questions: "What does that mean to be both 1 and 0 at the same time? What does such an algorithm look like? How does this parallelism work? Why can't a traditional computer simulate this?" I hope to answer these questions: this article is for today's software developers who want to understand what quantum computing is about and how it works. 

Qubits

The basis of a quantum computer is called a qubit. It is the quantum version of the classical binary bit. Although they seem similar concepts, they are quite different.

One main difference with traditional computers is that the performance of a quantum computer is typically not measured by the speed of its CPU, but by the number of qubits it has. Unlike with the computers we know, qubits are an actual physical entity in a quantum computer. IBM's Q 53 computer for example has 53 qubits. Such a physical qubit is created in a few different ways: e.g. the polarization of a single photon or the spin of an electron.

For completeness, other things like the qubit's coherence time and the computer's fault tolerance also matter, but I'm not getting into details about these topics though because they are not crucial to understand the performance of a quantum computer.

A classical bit can have two values 0 and 1, that we all know. A qubit has equivalent states that are represented like |0> and |1> (this notation is called a ket, but just think of them as the quantum bit equivalent of 0 and 1). A qubit, however, can be in a superposition of both states at the same time, and once measured, it will collapse to either |0> or |1>. Let's explain these concepts in more detail because they are crucial to understanding why quantum computers are claimed to be so much more powerful.

Superposition

"A qubit can be 0 and 1 at the same time and is like a spinning coin" is an often-used explanation for the concept superposition and I hate it. It's so vague and meaningless and it doesn't help in any way to understand how quantum computers work. Let's try a different explanation.

Superposition means that the value of a qubit can be in a state where it just has some probability that it would return |1> when measured, and some probability that it would return |0> when measured. These probabilities are what is played with. You really must take the term probability literally here: if we would measure two qubits in identical states, they would not give the same result!

The easiest way to visualize the state of a qubit is by using a Bloch sphere. The top of the Z-axes represents |0> and the lowest point of the Z-axes represents |1>. Any state of a qubit can be described as a combination of two vectors inside this sphere. Any state above the equator is more likely to return |0> and any state below the equator is more likely to return |1>. When the state is on the equator, the qubit has a 50/50 chance of returning |0> or |1>.

Image source: Wikimedia commons

Mathematically this is represented using the following formula |??> = ??|0> + ??|1>. |??> is just a symbol to represent the value of a qubit and ?? and ?? are each time complex numbers called the probability amplitudes. Their values indicate the likelihood of the qubit becoming |0> or |1> when measured.

These probability amplitudes are complex numbers, so ?? and ?? can be negative as well. The probability can be calculated from a probability amplitude by doing the square of its absolute value (so |??|2 for ?? and |??|2 for ??). And yes, as you would expect for probabilities, the sum adds up to 100% like this: |??|2 + |??|2 = 1.

Oh and by the way, we will come back to this later, but you can immediately see why we can "store" more information in a qubit then in a traditional bit. I can fully describe the state of a traditional bit by simply saying that it is 1 or 0. To fully describe the state of a quantum bit, I need to give you two complex numbers: ?? and ??.

Measurement

We have mentioned the word "measured" a couple of times by now, but what does it mean? In a traditional computer, we "measure" or "read" a bit constantly. Without reading it, we can't perform operations like AND, OR, NOT. We couldn't possibly AND something if we didn't know its value!

In quantum computing, this works differently: during the execution of a quantum algorithm the value of a qubit is in this superposition state (where it has certain probabilities to become |1> and |0>) and gates (which compare to operators as we know them) perform operations by manipulating and rotating these probabilities. When your algorithm is finished and you need to get the result out of the system, you need to read or measure your qubit, and by doing so its value collapses to either |0> or |1>; all other information is lost.

This works because a quantum operator doesn't need to measure a qubit to act on it! Using these operators, you can do things like rotating a probability some degrees, but the laws of quantum mechanics prevent you from reading its value! In a way, you can push it in a certain direction, but you can't know where it was. We'll talk more about that later. For now, simply assume that if you define a quantum algorithm, you typically would only measure the value at the end of the algorithm. Measuring is something you do to get the result of your quantum algorithm. In programmatic terms, think of it as the return value of a function.

Entanglement

Quantum entanglement is a phenomenon of quantum mechanics where two particles (e.g. electronics) are shared or linked in such a way (no matter how far they are apart) that their state can no longer be seen as separate. If you read the value of one, that the value of the other one is automatically known.

A classical and intuitive analogy that is often used is that of a pair of gloves. Suppose you have a pair of gloves and without looking you keep one and you give the other one to a friend. If you then look at your glove and you notice that you have the left glove, you know immediately that your friend will have the right glove. You could, therefore, consider the two gloves in that pair to be entangled.

The same principle can be applied to qubits and although it may seem like a pointless capability, it's this feature that gives a quantum computer the ability to process much more data than a traditional computer can.

I won't get into the math here (I recommend that you go read Dancing with Qubits for that), but I'll try to explain the essence.

Suppose you had three qubits that aren't entangled. Let's call these qubits |??> (psi), |Ω> (omega) and |Φ> (phi). As you've learned earlier, each qubit can be described using a formula like ??|0> + ??|1> where ?? and ?? are each time a complex number. So basically, if we run an algorithm using three non-entangled qubits, we have 3 x 2 = 6 complex numbers to work with.

But as soon as these three qubits are entangled, we can't describe their states individually anymore. You can no longer say that there is a certain probability you'll get a particular value out of a particular qubit. You have to look at all three qubits as a whole. All you can say is that there is a certain probability that you'll end up with 000, and a certain probability that you'll end up with 001, and with 010, and so on! Mathematically this can be written like this:

Where the a-coefficients each time represent the probabilities to get this combination of values. Notice that we no longer have 6 complex numbers, but now we have 8. So, by entangling three qubits, we gained 2 complex numbers.

The number of coefficients grows exponentially with the number of qubits: 1 qubit has 1^2 = 2 coefficients; 2 qubits have 2^2 = 4; 3 qubits have 2^3 = 8; 15 qubits have 2^15 = 32768 coefficients... Suppose we created a computer with 1000 qubits, then we have 2^1000 = 1,07E301 coefficients at our disposal. That's a 1 with 301 zeros behind it, an insane number.

This also explains why it is impossible to fully simulate a quantum computer using today's computers. To simulate qubits, you would need to store all these probability amplitudes. Assuming we use 32 bits (4 bytes) per probability amplitude, to simulate a quantum computer of 53 qubits (which already exists today), we would need 2^53*4 = 32768TBs of RAM.

Note that you should not think of a 53-qubit quantum computer as a machine with that much RAM. All this information only exists during the execution of the algorithm and irreversibly gets lost the second you measure it. You can't use these probabilities in the same way as you would use variables in your code today.

Also, all this information makes a quantum computer much more sensitive to the influences of the outside world. These influences come from magnetic fields, electric fields, warmth... and lead to a problem called quantum decoherence. It's this thing that currently only makes it possible for us to reliably maintain a state of a qubit for a few dozen microseconds, after that the information is lost. For example, IBM's Q System One had a coherence time of 73μs in March 2019. In the same article, they also describe that they need to aim for a coherence time of 1 to 5 ms to achieve an error rate of less than 0.01%.

Gates

The equivalent of boolean operators in classical computers (AND, OR, NOT...) are called quantum gates. The key difference between quantum operators and operators in a traditional computer is that they are always reversible and… this is key… don't need a measurement to perform their operation (as explained earlier). A gate manipulates and rotates the probabilities inside the Bloch sphere and the result is a new superposition state of the qubit with new probabilities.

Mathematically gates can be represented as a matrix multiplication of the state of the qubit with another matrix. Below are some examples of gates, but there are plenty of articles online if you want to learn more about them. Don't worry about what they mean or do at the moment. Just remember that every gate rotates and changes these probabilities in some very specific way.

Quantum Algorithm

The next image is an example of what a quantum algorithm looks like. We won't be describing this in detail, but I'll just explain the main components.

screenshot from IBM's Qiskit tool

On the left, you'll see that we're dealing with a 5-qubit algorithm. Typically, the main phases of an algorithm involve the following steps (this is highly simplified, but it was enough for me at least to create a mental picture of how it works):

1. First, each qubit is initialized to some state. In this example, the Hadamard gate is applied to put the qubits in a state where you get a 50/50% chance of returning either a |1> or a |0> if you would measure it add this stage.
2. During the algorithm, some or all qubits may be entangled. this is done in this case using the CNOT gate (that's the gate with the +-icon)
3. Also, other gates and Oracles (we'll discuss oracles later) are used to perform rotations on the superposition states. Each gate changes the probabilities of the qubits.
4. Eventually, measurements are done at which moment all superposition states collapse to their base states (thus returning a |1> or a |0>). These base-states then represent the result or output of the algorithm.

It's obvious to see how such an algorithm returns its values. It probably still is unclear to you where this algorithm gets its input-values from. Partly this could be done by setting the qubits into some initial state, but that has limitations. Read on, this will become much clearer when we discuss Grover's algorithm as an example.

To benefit from a quantum computer you have to find an algorithm that allows you to leverage the fact that a qubit can be in this superposition states. That means that not every problem can be solved more efficiently using a quantum computer. Only those problems, for which you can come up with an algorithm where you can reduce the number of calculations that you need to do by leveraging these superposition states AND where you can get the final result in such a way that it is something we can measure using these base states (meaning something containing only 1's and 0's), can benefit from a quantum computer.

How does this parallelism work?

As developers, when we hear parallelism, we tend to think of it as what we know and develop every day: multiple threads, processes, machines... all executing the same logic at the same time, but they all do it independently of each other. But when you look at any quantum algorithms you won't recognize any of these parallelism patterns, so how does it work?

Parallelism in quantum computers works differently. There are no multiple "threads" each calculating a particular value. Instead, the parallelism comes from the fact that a qubit has all the values between |0> and |1> at the same time but each with different probabilities and gates manipulate/rotate all these probabilities at the same time. To leverage this parallelism, you need to find an algorithm which manipulates these probabilities in such a way that the chances that the final answer is the right one is as high as possible.

This is why a quantum algorithm looks completely different from any algorithm as we write today. You can do an operation on all values of a qubit at the same time, but you shouldn't think of these operations as the same operations that you work with daily. They are not. The toolset that you have at your disposal to build your algorithms is completely different, and it's way more different than just a different syntax. You need to build using entirely different concepts.

When to use a quantum algorithm?

So not every problem can be solved better using a quantum computer. If you can't come up with an algorithm that benefits from these superposition states and whose result can be defined by the basic states for your problem, then it can't be solved more efficiently using a quantum computer.

That's why quantum computers will not replace traditional computers. There are only certain problems that are going to be suited to be solved using a quantum computer. Most of the things that you do on a computer (e.g. watching a video or reading this article….) can't be done better using a quantum computer. If anything, it would be slower, more expensive, and more unreliable to try to do that using a quantum computer.

The performance gain of a quantum computer does not come from the fact that it can do operations quicker. It comes from the fact that you use completely different algorithms that can find an answer to a problem in much fewer steps.

Example: Grover's Algorithm

Suppose you have a list of N items and you want to find this item in the list that satisfies a particular function. Today, we would solve this problem with code looking like this:

We could speed this code up by running it in parallel or even distributing it over multiple computers, but at the end of the day, you may have to do N-calls to this function f to find the answer. Grover's algorithm promises to do this in √N calls to this function. So where you would need to do 1000000 calls to f today, a quantum computer would need only 1000 in the future.

Note that Grover makes no statements about what that function is supposed to do, it's just a framework that can be used to solve these kinds of problems. This function is typically referred to as the oracle or a black box. As far as the Grover algorithm is concerned, it doesn't matter what that function does.

Btw, most articles online just glance over the oracle, but other than calling it a "black box" nobody ever goes into any detail, leaving me with an unsatisfactory feeling because all the magic seemed to simply have been moved in that thing. We'll talk about the oracle more in a second.

An example use case is that of password cracking. In this case, the values-list contains the passwords we want to test, and the function is the hashing algorithm which is supposed to return 1 for that password who's hashed value matches a particular hash. In this case, the logic to hash all passwords + the hash that you are decoding should be encoded in the Oracle.

How does Grover's algorithm look like?

Let's see how the algorithm works from a high-level perspective:

① First you need to figure out how many qubits you need. At the end of the algorithm, the qubits will contain the index of the matching item in the list. Just like with traditional computers, to encode a number with a maximum value of N, you need roundup(log2(N)) bits. E.g. if your list contains 1000 items, you need 10 bits (because 2^10 = 1024). In the example above, the list would be the passwords we're brute-force-testing.

② Next, all these qubits are put in a superposition. This means that, if we would measure these qubits at that moment in time, we would have a 50/50% chance for every qubit to get either 0 or 1

③ Next, all qubits are sent through the oracle (the function) and this thing is supposed to do the heavy lifting. Using a single call to this function it evaluates all values simultaneously and it inverses the amplitude of the index of the matching item. There are some pretty big assumptions being made about this oracle which we'll explain later.

④ In the Amplitude Amplification phase, the probabilities are rotated so that the amplitude of the matching value is inversed again while amplifying the amplitude of the matching item (and thus the amplitudes of all other items are shrunk).

⑤ Next, the previous steps are repeated several times (up to the square root of N) so that, on every run, the amplitude (probability) of the matching item each time gets bigger and bigger. The higher this amplitude, the bigger chance we have that the matching value will be returned when we do measure. We're never certain though.

⑥ Finally, the measurement is done. At this point, all qubits collapse into one of the base states (|0> or |1>), but because they are entangled, this happens as a group so we eventually measure something like |000>, |001> or |010>... The value returned by all the qubits is likely to be the index of the item we are looking for. Likely, but not for certain, we're dealing with probabilities after all.

Talking about the oracle

As you've read earlier, this oracle is somewhat of a magical thing, but nobody ever seems to go into any detail about it, which left me with a lot of questions.

But here's an important catch that took me a while to realize! For Grover to work, you need to have a quantum algorithm for that particular function. That means that it needs to be possible to come up with an algorithm for that function where you can benefit from the fact that you can put qubits in a superposition state! If you can't do that, Grover's algorithm offers no benefits over traditional algorithms. Few articles explicitly point out that developing these oracles is a huge challenge on its own and that many real-life use cases would require potentially hundreds of qubits to solve.

For example, take the example I used earlier of password hashing. In this case, the oracle would have to be "backed" by some quantum memory containing all the passwords stored in qubits in superposition states. It would then have to be able to calculate the hashes of all these passwords simultaneously and find that password that matches a particular hash. A highly complicated task that is nowhere near possible today. It is not even sure if we will ever be able to find a quantum algorithm to solve this problem.

Quantum Database Searching

Often when you read about Grover's algorithm, you'll find that it is often also being referred to as the quantum database search algorithm. It is this that originally tickled my interest in this algorithm.

The database in this case, however, is not a database as we know it at all! Because of that, the use of the word "database" is in my opinion badly chosen. They mean some virtual database where all the values of that database are somehow encoded in qubits in superposition states. An existing database can't be searched using Grover's algorithm because the information is not stored quantum.

Start playing

If you want to start playing with quantum computers and try building your circuits, here are two great resources to do just that:

• Microsoft Q# language: https://docs.microsoft.com/en-us/quantum/
• IBM Quantum Experience: https://quantum-computing.ibm.com/docs/

Conclusion

Developing code for a quantum computer requires a completely different way of thinking and of approaching the problems. It's a much bigger paradigm shift than moving from procedural to object-oriented or functional programming.

At the time of this writing, the technology is still extremely immature, and you can't solve any real business problems with it yet. But the size of its promise and the magnitude of the shift in thinking it requires, really justifies jumping into this technology early.