To better understand the quantum computer and the technological race it spawns, we offer here the first article in a series that will continue with other ideas in the coming weeks.
On January 21, 2021, the “Quantum Plane”a national strategy with a budget of 1,800 million euros, after the Parliamentary report “Forteza” of January 9, 2020 entitled “Quantum: a change that France should not miss”.
Eventually, quantum technologies could make extremely fast and powerful computers possible. These could revolutionize everything that currently depends on information technology, from financial exchanges to cutting-edge research, justifying the massive investments and the race for technology by the states and the GAFAM.
But today, these promises remain largely theoretical. So why all the enthusiasm for the quantum computer? How do we come to combine these two terms from disciplines that a priori have nothing to do with each other?
To understand the origins of this hybrid creature, between physics and computing, we will go back a long way, almost to the beginning.
The soul of all computers: the Turing machine
In 1936, the British mathematician Alan Turing, one of the founders of computer science, describes the “Turing” machine that will be the “mold” of all our computers. This machine can be programmed to solve problems in the following way: we give an input, then the machine calculates in several stages until it stops to return its output as an answer.
The first idea of this machine is to model a human with a paper and a pen, which has been given very precise instructions, the famous “computer”, in the language of Turing. Surprisingly, the many other proposals that have been made for the same purpose have turned out to have the same power as Turing machines. This is summed up in the Church-Turing Extended Thesis, which reads as follows:
“Any reasonable computer can, at best, solve the same problems and with the same efficiency as Turing’s machine. »
This thesis is not a rigorous mathematical statement that one can hope to prove, but it can be refuted. It would be enough to find a better calculation model… but until now, none could do it better than the Turing machine. Well almost.
The advent of the quantum
Physicists were very early interested in computers as “simulation” tools: by inserting physical laws into the computer program, one can mimic nature.
The Matrix, brought to the screen in 1999 by the Wachowski sisters, is an example of this type of program, which malevolent machines have carefully designed to emulate all possible interactions with the world. Is such a thing feasible in practice?
Wachowski sisters movie “Matrix”
If it is relatively isolated from simulating the envol des corbeaux devant les pas de l’agent Smith, les choses se corsent sevèrement si les inhabitants de la Matrice décident de constructe des accélérateurs de particules (une éventualité qui n’est malheureusement pas évoquée in the film). In fact, the equations that govern the behavior of particles (those of quantum mechanics) are much more complex to simulate for a computer than those that describe the flight of birds. Let’s try to find out what.
The interference of possibilities
Quantum physics is the relevant physical theory when it comes to describing phenomena on the scale of atoms. It has very special characteristics.
First, it only predicts probabilities that the particle will do this or that. Therefore, we can represent the evolution of a quantum object as a “tree of possibilities”.
But the most important aspect of quantum physics is that the different branches of this tree are not independent of each other. Some branches can be canceled or reinforced, we speak of “interferences”.
Here we see the difficulty: to simulate the real trajectory of a particle, it is also necessary to have simulated all other possible trajectories to take interference into account. This requires substantial computing resources, especially when considering concrete physical systems for which the number of possibilities is immense.
This is why it is difficult for a Turing machine to simulate systems described by quantum physics: it must perform a large number of operations. This is the observation that the physicist Richard Feynman made in 1981. He makes the following proposal:
“Wouldn’t it be easier to simulate quantum physics if the computers themselves were quantum?” »
How to simulate quantum systems?
To do this, the physicist David Deutsch imagined in 1985 a “quantum Turing machine”, which behaves like a particle. In each calculation step, the machine explores various branches and the final result depends on the interference between these different branches. A quantum Turing machine that uses only one branch is exactly a normal Turing machine.
Attention, the possible gain in computing power does not come directly from the possibility of performing several calculations in parallel in the branches. In fact, at the end of the calculation, we recover the result of a single branch with a certain probability depending on the interferences. Therefore, acceleration can only come fromclever algorithmic tricks increasing the probability of interesting branches, while decreasing the probability of others through interference. That is why it is very difficult to program a quantum computer.
Alfonso Saborido/Flickr, Tamiko Thiel/Wikipedia, CC BY-SA
To date, there are relatively few examples of such programs. The most famous is the“Shor’s Algorithm”which elegantly exploits interference to break certain types of security ciphers, for example the credit card encryption.
A still theoretical quantum advantage
A Turing machine can perfectly, in theory, emulate a quantum Turing machine by calculating all the trajectories and their interferences. Therefore, quantum computers cannot solve new problems that normal computers cannot solve.
However, a classical Turing machine takes a long time to simulate its quantum counterpart, suggesting that the The extended Church-Turing thesis could be shattered. Turing’s quantum machine would then become the new horizon of computing.
[Plus de 80 000 lecteurs font confiance à la newsletter de The Conversation pour mieux comprendre les grands enjeux du monde. Abonnez-vous aujourd’hui]
Of course, beware, because for the moment no one has been able to rigorously demonstrate that the quantum Turing machine is faster than the normal Turing machine, although the recent experiences tend to indicate that this is the case.
The challenge remains to demonstrate the quantum advantage in practice.
Finally, we have only talked about theory here, neglecting a very important aspect: the construction of computers.
Thus, if already in 1936 history was already theoretically folded, years and tremendous technological efforts were necessary for the Turing machine to be completely reflected in the processors. The same goes for quantum computing.
Even if the quantum Turing machine turns out to be faster, a real quantum computer has yet to be built. From then on, the theoretical duel between normal and quantum Turing machines will be transferred to the competition between concrete machines. The outcome of this duel is currently uncertain, and the challenge for quantum computing will be to demonstrate a practical advantage by making smart use of the billions invested in recent years.
And after that ? Who knows, maybe physics still has a few surprises in store for computer scientists of the future.
Read more:
“Back to…”: Are Quantum Technologies Ready to Enter Our Lives?