Course à l’ordinateur quantique : aux origines d’une créature hybride

Titouan Carette, Université Paris-Saclay

Pour mieux comprendre l'ordinateur quantique et la course technologique qu'il génère, nous vous proposons ici le premier article d'une série à suivre avec d'autres éclairages dans les prochaines semaines.

---

Le 21 janvier 2021 était annoncé le « Plan Quantique », une stratégie nationale au budget de 1,8 milliard d’euros, faisant suite au rapport parlementaire « Forteza » du 9 janvier 2020 intitulé « Quantique : un virage que la France ne doit pas rater ».

À terme, les technologies quantiques pourraient permettre de réaliser des ordinateurs extrêmement rapides et puissants. Ceux-ci pourraient révolutionner tout ce qui dépend actuellement de l'informatique, des échanges financiers à la recherche de pointe, justifiant les investissements massifs et la course à la technologie des états et des GAFAMs.

Mais à l'heure actuelle, ces promesses restent en grande partie théoriques. Alors, pourquoi tant d’engouement pour l’ordinateur quantique ? Comment en est-on venu à accoler ces deux termes provenant de disciplines qui n’ont a priori rien à voir ?

Pour saisir les origines de cette créature hybride, entre physique et informatique, nous allons remonter loin, presque au tout début.

L’âme de tous les ordinateurs : la machine de Turing

En 1936, le mathématicien britannique Alan Turing, l’un des fondateurs de l’informatique, décrit la machine « de Turing » qui sera le « moule » de tous nos ordinateurs. Cette machine peut être programmée pour résoudre des problèmes de la façon suivante : on donne une entrée, puis la machine calcule en plusieurs étapes jusqu’à s’arrêter pour renvoyer sa sortie en réponse.

L’idée première de cette machine est de modéliser un humain muni d’un papier et d’un stylo, à qui l’on a fourni des instructions très précises, le fameux « computer », dans la langue de Turing. Fait surprenant, les nombreuses autres propositions qui ont été faites dans le même but se sont toutes révélées égales en puissance aux machines de Turing. On résume cela par la thèse de Church-Turing étendue, qui s’énonce ainsi :

« Tout calculateur raisonnable peut au mieux résoudre les mêmes problèmes et avec la même efficacité que la machine de Turing. »

Cette thèse n’est pas un énoncé mathématique rigoureux que l’on peut espérer prouver, mais elle peut être réfutée. Il suffirait pour cela de trouver un meilleur modèle de calcul… mais jusqu’à présent, aucun n’a pu faire mieux que la machine de Turing. Enfin presque.

L’avènement du quantique

Les physiciennes et physiciens se sont très tôt intéressés aux ordinateurs comme des outils de « simulation » : en insérant des lois physiques dans le programme de l’ordinateur, on peut imiter la nature.

La Matrice, portée à l’écran en 1999 par les sœurs Wachowski, est un exemple d’un tel programme, que des machines malveillantes ont soigneusement conçu pour émuler l’intégralité des interactions possibles avec le monde. Une telle chose est-elle réalisable en pratique ?

S’il est relativement aisé de simuler l’envol des corbeaux devant les pas de l’agent Smith, les choses se corsent sévèrement si les habitants de la Matrice décident de construire des accélérateurs de particules (une éventualité qui n’est malheureusement pas évoquée dans le film). En effet, les équations qui régissent le comportement des particules (celles de la mécanique quantique) sont bien plus complexes à simuler pour un ordinateur que celles décrivant le vol des oiseaux. Tâchons de comprendre en quoi.

L’interférence des possibles

La physique quantique est la théorie physique pertinente lorsqu’il s’agit de décrire les phénomènes à l’échelle des atomes. Elle possède des caractéristiques très particulières.

Premièrement, elle ne prédit que des probabilités que la particule fasse telle ou telle chose. On peut donc représenter l’évolution d’un objet quantique comme un « arbre de possibilités ».

Mais l’aspect le plus important de la physique quantique est que les différentes branches de cet arbre ne sont pas indépendantes les unes des autres. Certaines branches peuvent s’annuler ou se renforcer, on parle d’« interférences ».

On voit ici la difficulté : pour simuler la trajectoire effective d’une particule, il faut aussi avoir simulé toutes les autres trajectoires possibles afin de prendre en compte les interférences. Cela nécessite des ressources informatiques conséquentes, surtout lorsque l’on considère des systèmes physiques concrets pour lesquels le nombre de possibilités est immense.

Voilà pourquoi il est difficile pour une machine de Turing de simuler des systèmes décrits par la physique quantique : elle doit faire un très grand nombre d’opérations. C’est le constat que fait le physicien Richard Feynman en 1981. Il fait la proposition suivante :

« Ne serait-il pas plus facile de simuler la physique quantique si les ordinateurs étaient eux-mêmes quantiques ? »

Comment simuler les systèmes quantiques ?

À cette fin, le physicien David Deutsch imagine en 1985 une « machine de Turing quantique », qui se comporte comme une particule. À chaque étape de calcul, la machine explore plusieurs branches et le résultat final dépend de l’interférence entre ces différentes branches. Une machine de Turing quantique n’utilisant qu’une seule branche est exactement une machine de Turing normale.

Attention, l’éventuel gain en puissance de calcul ne provient pas directement de la possibilité d’effectuer plusieurs calculs en parallèle dans les branches. En effet, à la fin du calcul, nous ne récupérons le résultat que d’une seule branche avec une certaine probabilité dépendant des interférences. Ainsi, l’accélération ne peut provenir que d’habiles stratagèmes algorithmiques permettant d’augmenter la probabilité des branches intéressantes, tout en diminuant la probabilité des autres par le biais des interférences. Voilà pourquoi il est très difficile de programmer un ordinateur quantique.

À ce jour, on compte relativement peu d’exemples de tels programmes. Le plus célèbre est l’« algorithme de Shor », qui exploite élégamment les interférences pour casser certains types de cryptages de sécurité, par exemple le cryptage des cartes bleues.

Un avantage quantique encore théorique

Une machine de Turing peut parfaitement, en théorie, émuler une machine de Turing quantique en calculant toutes les trajectoires et leurs interférences. Ainsi, les ordinateurs quantiques ne peuvent pas résoudre de nouveaux problèmes que les ordinateurs normaux ne pourraient pas déjà résoudre.

Cependant, une machine de Turing classique met beaucoup de temps pour simuler son homologue quantique, ce qui suggère que la thèse de Church-Turing étendue pourrait voler en éclat. La machine de Turing quantique deviendrait alors le nouvel horizon de l’informatique.

[Plus de 80 000 lecteurs font confiance à la newsletter de The Conversation pour mieux comprendre les grands enjeux du monde. Abonnez-vous aujourd’hui]

Prudence cependant, car pour l’instant personne n’a pu prouver rigoureusement que la machine de Turing quantique est plus rapide que la machine de Turing normale, même si les expériences récentes tendent à indiquer que c’est le cas.

L’enjeu reste de démontrer l’avantage quantique en pratique

Enfin, nous n’avons parlé ici que de théorie, en négligeant un aspect très important : la construction des ordinateurs.

Ainsi, si dès 1936 l’histoire était déjà théoriquement pliée, il a fallu des années et de formidables efforts technologiques pour que la machine de Turing s’incarne pleinement dans des processeurs. Il en va de même pour l’informatique quantique.

Même si la machine de Turing quantique s’avérait plus rapide, il reste encore à construire un véritable ordinateur quantique. Dès lors, le duel théorique entre machines de Turing normales et quantiques se transposera en compétition entre machines concrètes. L’issue de ce duel est pour l’instant incertaine, et l’enjeu pour l’informatique quantique sera de démontrer un avantage pratique en utilisant à bon escient les milliards investis ces dernières années.

Et après ça ? Qui sait, peut-être la physique garde-t-elle encore quelques surprises en stock pour les informaticiennes et informaticiens du futur.

Titouan Carette, Chercheur post-doctoral en informatique quantique, Université Paris-Saclay

Cet article est republié à partir de The Conversation sous licence Creative Commons. Lire l’article original.