Accueil / Regards sur la science / Confusions concernant le calcul quantique

Confusions concernant le calcul quantique

Publié en ligne le 2 octobre 2016 - Intelligence Artificielle -

Souvent on évoque les ordinateurs quantiques comme sur le point d’exister et de tout changer, ou même existant déjà et réalisant de formidables exploits qui mettent en danger la cryptographie mathématique moderne et donc nos cartes bancaires et le fonctionnement de l’Internet commercial. Des annonces tonitruantes sont faites assez régulièrement (par exemple par Google et D-wave en décembre 2015), qui créent une grande confusion.

Où en est-on réellement ? Et quels changements peuvent résulter des avancées de l’informatique quantique ?

A) Il existe une cryptographie quantique. Elle n’est presque pas utilisée car plus délicate à mettre en œuvre que la cryptographie mathématique qui, pour l’instant, n’est pas vraiment menacée par les ordinateurs quantiques réels (voir plus bas). Cette cryptographie quantique opérationnelle aujourd’hui – des entreprises vendent des dispositifs qui la mettent en œuvre 1 – ne doit pas être confondue avec le calcul quantique qui consiste, non pas à mettre au point des systèmes quantiques spécialisés de cryptographie, mais à mettre au point des ordinateurs les plus généraux possible fondés sur les principes de la mécanique quantique.

B) Il existe un modèle mathématique d’ordinateur quantique et on a démontré dès 1995 qu’il avait un pouvoir théorique de calcul supérieur à celui des ordinateurs classiques (tous les ordinateurs aujourd’hui). Un ordinateur quantique général pourrait par exemple factoriser rapidement (on dit en temps polynomial) des nombres entiers, alors qu’un ordinateur classique ne le peut très probablement pas. Cependant, même sur le plan théorique tout n’est pas faisable rapidement avec un ordinateur quantique général. Ils ont aussi des limites.

C) La cryptographie étudie et conçoit des méthodes mathématiques de cryptographie dites post-quantiques qui exploitent les faiblesses et limites des ordinateurs quantiques généraux. Ces méthodes de cryptographie mathématique post-quantiques, contrairement à la majorité de celles utilisées aujourd’hui en cryptographie, ne seraient pas mises en danger par l’existence d’ordinateurs quantiques généraux. Des solutions existent donc pour « sauver » la cryptographie mathématique lorsqu’on saura réaliser des ordinateurs quantiques généraux qui ne soient pas que des jouets. Ces solutions permettraient de ne pas avoir à s’appuyer sur la cryptographie quantique évoquée dans le paragraphe A.

D) Les recherches pratiques sur la réalisation d’ordinateurs quantiques progressent. Cependant, ce qu’on réussit à faire aujourd’hui avec des calculateurs quantiques ne permet de résoudre aucun problème plus rapidement qu’on ne le résout avec un ordinateur classique. Aucun danger immédiat pour la cryptographie mathématique usuelle ne semble donc résulter des dispositifs de calculs quantiques qu’on sait vraiment fabriquer aujourd’hui. La cryptographie n’a en conséquence pas besoin pour l’instant de mettre en œuvre les dispositifs quantiques de cryptographie qui existent (point A) ou les méthodes de cryptographie mathématiques post-quantiques (point C). Les progrès dans la mise au point des ordinateurs quantiques ont conduit aujourd’hui à des machines capables de factoriser le nombre 143 (143 = 11×13) en 2012, et les nombres de 6 chiffres décimaux inférieurs à 200 000 (avril 2016, record en attente de validation). C’est très bien, mais ridicule en regard de ce qu’on sait faire avec des algorithmes classiques sur des ordinateurs classiques. En effet, aujourd’hui, sur ces machines classiques, on factorise assez facilement des nombres de 100 chiffres décimaux ; le record est de 232 chiffres pour un nombre entier difficile (car produit de 2 nombres premiers). On peut penser que de nombreuses années seront nécessaires pour passer de la factorisation par des machines quantiques des nombres de 6 chiffres à ceux de 100 chiffres.

L’annonce 2, parfois présentée comme un triomphe des ordinateurs quantiques en décembre 2015, concernait un type de machines quantiques spécialisées (et non pas un ordinateur quantique général) et ne consistait qu’en la résolution d’un problème qu’on sait résoudre par les méthodes classiques beaucoup plus rapidement. L’astuce qui a trompé quelques journalistes était que la méthode « programmée » dans la machine quantique permet de calculer beaucoup plus rapidement la solution que la même méthode programmée dans un ordinateur classique. Ce qui rend l’exploit beaucoup moins spectaculaire qu’il n’y paraît est que la méthode utilisée n’est pas la meilleure possible et que lorsqu’on utilise la meilleure méthode connue, alors les ordinateurs classiques sont beaucoup plus rapides. En clair, c’est comme si l’ordinateur quantique était champion d’un calcul de multiplication à la condition d’utiliser la méthode suivante, la seule qu’il peut appliquer : « pour connaître A x B additionner A + A + A + … + A en écrivant B fois le A. » alors que cette méthode est mauvaise et que l’ordinateur classique en utilisant un meilleur algorithme de multiplication (par exemple celui qu’on a appris à l’école) était plus rapide.

Le calcul quantique avance, mais pas aussi vite que certains voudraient nous le faire croire, et aujourd’hui, il n’a pas résolu un seul problème réel de calcul mieux que l’ordinateur classique. Ne vendons pas la peau de l’ours avant de l’avoir numérisé !

1 Sans que l’on sache qui achète ces dispositifs, puisque ce n’est pas rendu public. On peut imaginer des gouvernements ou des entreprises, pour communiquer entre deux bâtiments au sein d’une capitale. Il y a une limitation de distance entre les deux points de communication : quelques dizaines de kilomètres au plus.

Publié dans le n° 317 de la revue


Partager cet article


L' auteur

Jean-Paul Delahaye

est professeur émérite à l’université de Lille et chercheur au Centre de recherche en informatique signal et (...)

Plus d'informations

Intelligence Artificielle

L’intelligence artificielle (IA) suscite curiosité, enthousiasme et inquiétude. Elle est présente dans d’innombrables applications, ses prouesses font régulièrement la une des journaux. Dans le même temps, des déclarations médiatisées mettent en garde contre des machines qui pourraient prendre le pouvoir et menacer la place de l’Homme ou, a minima, porter atteinte à certaines de nos libertés. Les performances impressionnantes observées aujourd’hui sont-elles annonciatrices de comportements qui vont vite nous échapper ?