TechnologyThe gin and tonic metaphor: what is a quantum algorithm and why...

The gin and tonic metaphor: what is a quantum algorithm and why are they so powerful?


Gin Tonic in a balloon glass.

We are told that quantum computers are already here and that they are much more powerful than conventional ones. In particular, that in a short time they will be able to break our cryptographic keys. Many countries are investing in this technology to be the first to achieve what is known as “quantum supremacy.” But do we know how a quantum computer calculates and what is the reason for the power attributed to them?

Let’s start with memory. In a traditional computer its minimum unit is the bit, which can contain a 0 or a 1. In a quantum computer it is the qubit – short for quantum bit – which can contain a 0 or a 1, but also any combination of these two states basic. Physicists call this characteristic “superposition of states” and tell us that this is normal in the world of the very small. A particle – such as a proton – has, for example, a property called “spin”, related to its magnetic properties, which can take two basic values ​​called “up” and “down”, although the usual thing is that his state is a combination of both. We can put as a mundane analogy of this superposition a gin tonic, which will have a certain proportion of gin and another of tonic. The relevant information that the qubit stores is the pair of proportions to and b of each state, that is, two numbers (for greater precision, it is also two complex numbers). This already gives us an idea of ​​the storage power of a qubit (any ratio of gin and tonic) with respect to that of a traditional bit (only gin, or only tonic).

Another characteristic of the physical world is that the states of two quantum particles can be entangled, meaning that they are linked to each other. This allows us to build memories with several entangled qubits. Thus, two qubits would be in a superposition of the four basic states 00, 01, 10 and 11. As a consequence, two qubits store four numbers and, in general, n Interlaced qubits store 2Λn (2 raised to n) numbers. For example, in five bits traditional memories store a single integer between 0 and 31, but five interlaced qubits store 32 complex numbers. And there is an exponential gain there.

Now let’s go to the computation: the qubits operate with each other through the so-called “quantum gates”. For example, there is a gate called X that, applied to a qubit, turns a 0 into a 1 and a 1 into a 0. But, that gate X is somewhat more complex: applied to a qubit with proportions a and b of 0 and 1, goes to a state with proportions b and a of 0 and 1. In our analogy of the gin tonic, gate X would exchange the amounts of gin and tonic.

Scheme of a quantum circuit.
Scheme of a quantum circuit.

As we do with conventional computer circuits, by linking several quantum gates, a complex function can be calculated. A quantum algorithm is, in essence, a circuit formed by quantum gates, which transforms the state of a set of qubits from an initial superposition to a final one. Where, then, does its supposed greater computing power come from?

Imagine a function implemented with quantum gates, such as the integer square root of a number. Suppose that n qubits are sufficient to contain the input number. Using quantum gates, it is easy to get the n qubits reach a state that is a superposition of all possible n-bit states. Following the previous example, with five qubits we would achieve an overlap of 32 states. This is where the greatest power of quantum computers comes in: the quantum circuit would calculate the square root at once for the 32 possible values ​​of the input and leave the 32 square roots as an overlap on the output qubits. In other words, it can do in a single step what a conventional computer would take up to 32 steps to do.

But, not everything is rosy in the quantum world because it has some “quirks”: the proportions of the superposition – the ratio of gin and tonic – belong to the “inner life” of quantum particles. If an observer tries to measure the state of the qubits, their superposition is destroyed. This is what happens in physical reality, although no one knows why: if the spin of a proton is measured, the superposition is destroyed and the observer will obtain one of the two states, “up” or “down”, with a certain probability each, depending on the values ​​of to and b. It is as if, when we drink our gin and tonic, the mixture it contains is destroyed and we drink only gin or only tonic, without being able to anticipate which of the two we are going to drink.

Quantum algorithms require human ingenuity to extract more information from the output superposition. A common way to proceed is to interfere with the calculated results with each other by additional quantum gates. For example, we could calculate the sum or the product of all of them or determine how many of them are even and how many are odd. The most famous of the quantum algorithms, the one that decomposes an integer into its prime factors – due to the mathematician Peter Shor, in 1994 – uses techniques of this type.

Quantum algorithms are here. Now we only need quantum computers with hundreds of qubits to run them.

Ricardo Peña Marí He is Emeritus Professor of Computer Languages ​​and Systems at the Complutense University of Madrid

Chronicles of the Intangible is a space for the dissemination of computer science, coordinated by the academic society SISTEDES (Society for Software Engineering and Software Development Technologies). The intangible is the non-material part of computer systems (that is, software), and its history and its evolution are related here. The authors are professors at Spanish universities, coordinated by Ricardo Peña Marí (professor at the Complutense University of Madrid) and Macario Polo Usaola (professor at the University of Castilla-La Mancha).

To consult the chronicles of other years, click here.

You can follow EL PAÍS TECNOLOGÍA at Facebook and Twitter or sign up here to receive our weekly newsletter.