In an age during which everything is digitally recorded, logged and stored for who knows how many years, privacy – or lack thereof – is one of the hottest topics in the political landscape. Of course, one could install a bunch of digital hurdles to keep intruders such as the infamous NSA out of their system; the reality of it is that one of the most potent tools to bypass all of these precautions finds its origin in our beloved mathematics. Most of you, like me, will shiver a little at the sound of this technique, but the time has come to dive – or just dip a toe – into the world of quantum computing.
Let us first establish some basic idea of what quantum mechanics actually is. Most of you will have heard of Schrödinger’s cat at some point; that is not what we will be discussing at all. In this article, we will be introducing a radically different example, aptly named “Schrödinger’s phone”. Suppose, someday, you are fiddling around with your new smartphone when you suddenly drop it on the floor and you are unable to see whether its screen is now broken or not. At this exact moment, the phone will both be broken and not broken, since you have not observed its state. This state is known as a quantum superposition. As you might imagine, this state stops being a superposition when observation takes place: once you pick your phone back up to check for damages, it is either broken or not broken.
Are you not confused yet? Do not worry; we will go one step further. In the discussion below, we will use a situation from physics, in which quantum mechanics are commonly applied. Consider an electron with two possible configurations: up or down. Then the most general state is defined as
where and are coefficients and is Dirac notation for the quantum state that will always give the result ‘up’ when converted to classical logic by observation; likewise, will always be converted to ‘down’. The coefficients and dictate probabilities for the system to be in either configuration when observed. The probability for a specified configuration is given by the square of the absolute value of the coefficient and – like always – the probabilities should add up to one. Then, we have:
Now, continuing with the example: if the electron can be in state up and in state down, in quantum mechanics, it can also be in the state where it is in ‘up’ and in ‘down’, since . In this description, only the relative sizes of the different components matter, as well as their angle to each other on the complex plane.
In classical computers, data is encoded into long sequences of binary bits, each of which is always in one of two definite states: either 0 or 1. Quantum computers, however, use quantum bits (qubits) which can be in superpositions of states. So, similar to the way your phone was both broken and not broken, these qubits are both 0 and 1 – and everything in between. In general, this means that a quantum computer with qubits can be in any superposition of up to different states simultaneously; a normal computer can be in only one of these states at any one time. By now, you might be wondering how one could possibly use these strange, seemingly undetermined qubits to do anything useful.
This is where the quantum computer works its magic. The qubits are set to a controlled initial state that represents the problem at hand in some way, after which the qubits are manipulated by a fixed sequence of quantum logic gates, called a quantum algorithm. At the end of this algorithm, the state of the qubits is observed, which collapses the system into exactly one of the states, quite similarly to the way your phone became either broken or not broken, when you picked it up. Of course, there is still much, much more detail to discuss, but to keep you sane until at least the start of next year’s lectures, will leave the technical discussion here and consider some of the applications.
What is widely accepted as one of the most effective ways to encrypt some string of binary bits is known as the RSA scheme, which is based on prime factorization. The RSA algorithm involves a public and private key: the public key can be known by everyone and is used for encryption of a message. The idea is that messages encrypted by the public key can only be decrypted within a reasonable time with the private key , which will never have to be transmitted. The basic principle is to find three large positive integers , and , such that for some binary message , equivalent to some positive integer , it holds that , so that even if one would know and or even , it would be extremely difficult to find . Naturally, an approach that will always be effective is simply trying all possible combinations, of which there are exponentially many.
Of course, trying all possible combinations is something that computers are quite good at. The problem is that it takes an exponentially growing amount of time to do so: for large numbers with many large key primes, it can take up to tens of years to break a single number, with the current state of technology. This, in turn, allows the sender/receiver plenty of time to change up the set of key primes frequently enough, so that no-one will ever be able to decrypt their communication in time. This is very much a recurring theme in the collection of encryption techniques: they are mostly built on the premise that decrypting anything will simply take too much time to be relevant.
However, the development of quantum computing might change all of that, via clever use of quantum algorithms. For example, the – currently only theoretically applicable – quantum algorithm, known as Schor’s algorithm, is able to solve the prime factorization problem in polynomial time, which means that the time it will take to crack a number will grow relatively slowly when the size of the number you are trying to crack increases. In other words, all of the information on your computer, smartphone and tablet that is currently being protected by simply delaying intruders past the point of relevance, will become vulnerable when quantum computers become operational, simply because they are much, much faster.
Interested in the RSA algorithm and other cryptography methods? Take a look at the Cryptography Special in Nekst 1 2013-2014!
But the uses of quantum mechanics do not stop there! At the TU Delft, Ronald Hanson and his team of researchers have recently proven that one of the most counterintuitive theories in quantum mechanics is actually reality, by showing that two particles that were 1.3 kilometers apart shared the same properties. To a simple econometrician such as myself, this did not sound like such a big deal. However, there is one very important thing to remember: the qubits in a quantum computer are also based on particles. Hence, if the qubits in two quantum computers would share the same properties (and thus convey the same information) we would in fact be able to ‘teleport’ information from one computer to the other, without the use of internet or any traditional means of data transportation.
Theorizing a little further, this would mean that it would potentially be possible to transfer information across large distances without any time passing, which would be faster than the speed of light. This, in turn, means that theoretically, we would be able to receive information about some event that we are physically unable to have observed yet. One cannot even begin to imagine the effect of such a technology on modern day trade and espionage.
While quantum computing is still in its infancy, we can very well conclude that one of the most powerful tools in modern-day espionage has definitely been born in the form of quantum computing; even still, it might be a while before Q is able to fit this one into 007’s box of toys.
Text by: Pepijn Wissing