Vers l’ordinateur quantique : un défi scientifique majeur pour les prochaines décennies  

4. Deux grands résultats et leurs conséquences

C'est dans la première moitié des années 1990 que deux résultats théoriques majeurs ont donné le véritable signal de départ aux recherches aujourd'hui foisonnantes sur l'information quantique et son traitement : l'algorithme quantique de Shor (1994) pour la factorisation des entiers, et l'algorithme quantique de Grover (1996) pour la recherche d'un élément dans une base de données non ordonnée.

Que changerait l'algorithme de Shor ?

Prenons un exemple de problème qui peut devenir insurmontable pour l'informatique classique : la factorisation des entiers. Considérons un nombre entier, très grand, dont on sait qu'il est le produit de deux nombres premiers, mais on ne sait pas lesquels. Le problème de la factorisation est de trouver ces deux nombres. C'est un problème simple à poser, mais il excite les mathématiciens depuis plus de deux millénaires. En effet, s'il faut n chiffres pour écrire notre nombre, on ne connaît encore aucune méthode, ni à la main ni avec les ordinateurs actuels, qui garantisse qu'on puisse trouver ces deux facteurs en effectuant un nombre d'opérations qui ne soit pas une fonction exponentielle de n : tous les algorithmes classiques connus pour la factorisation sont de complexité exponentielle. Pour chacun de ces algorithmes, on connaît une formule qui, étant donnée la valeur de n, permet de déterminer l'ordre de grandeur du nombre d'opérations qu'il devra effectuer. Par exemple, le meilleur de ces algorithmes devra effectuer de l'ordre de 10²⁶ opérations (1 suivi de 26 zéros) pour factoriser un nombre de 300 chiffres. Imaginons alors que nous ayons à notre disposition l'ordinateur le plus puissant qu'on sache construire aujourd'hui, dont les performances sont de l'ordre de 100 teraflops (10¹⁴ opérations par seconde). Pour trouver les deux facteurs de notre nombre de 300 chiffres, c'est-à-dire pour effectuer 10²⁶ opérations à raison de 10¹⁴ opérations par seconde, il lui faudra 10¹² secondes, c'est-à-dire 30 000 ans ! Paradoxalement, l'obstacle que constitue cette complexité présente un grand intérêt, car c'est précisément sur la difficulté à le franchir que repose la sécurité des systèmes de cryptage les plus répandus, comme ceux qui sont utilisés sur internet pour transmettre des informations confidentielles.

Ce que Peter Shor a montré est que, si on remplace nos vieux principes de calcul par ceux de l'informatique quantique, on pourra alors trouver les deux facteurs premiers de notre nombre de n chiffres en n³ opérations élémentaires, soit de l'ordre de 10⁷ opérations pour un nombre de 300 chiffres. Si l'ordinateur, maintenant quantique, effectue une opération par microseconde, ce qui est modeste, il lui suffira de 10 secondes pour trouver les deux facteurs. C'est ce résultat de Shor, en 1994, qui a mis le feu aux poudres pour les recherches sur le calcul quantique : à toute une classe de problèmes, dont fait partie la factorisation, le calcul quantique apportera des chutes exponentielles de complexité par rapport à ce qu'on sait faire de mieux pour ces problèmes avec le calcul classique. Les conséquences concrètes n'en sont peut-être pas très nombreuses, mais elles sont de taille : si, un jour encore lointain, un ordinateur quantique arrive sur le marché, il suffira de quelques minutes pour faire voler en éclats tous les systèmes de cryptage actuels.

L'information quantique détruira donc d'une main la cryptographie classique, qui est fondée sur des obstacles algorithmiques auxquels on accorde encore une certaine confiance, bien que leur robustesse ne soit pas prouvée. Mais elle reconstruit déjà de l'autre main une cryptographie quantique bien différente, évoquée plus loin (voir 6.), dont la sûreté est beaucoup plus définitive, car fondée sur des propriétés physiques de la matière à l'échelle quantique.

Qu'apporte l'algorithme de Grover ?

Le problème traité par Grover est bien différent. Un exemple simple suffit pour apprécier la portée de son résultat. Considérons un annuaire téléphonique qui contient les noms et numéros de 10⁶ abonnés, rangés dans l'ordre alphabétique de leurs noms, si bien qu'aucun ordre ne préside au rangement des numéros les uns par rapport aux autres. Si cet annuaire est la seule base de données dont on dispose sur le numéro affecté à chaque abonné, la recherche du nom de l'abonné ayant un numéro donné exigera, à la main ou avec un ordinateur actuel, de l'ordre de 10 ⁶ comparaisons entre ce numéro et ceux que contient l'annuaire (5.10⁵ en moyenne pour trouver la bonne réponse).

Ce que Grover a montré, c'est que les principes du calcul quantique permettront de trouver la réponse en faisant un nombre de comparaisons égal à la racine carrée de la taille de la base de données, c'est-à-dire, dans le cas de notre annuaire, mille comparaisons. Les principes mêmes de l'informatique classique lui interdisent l'accès à une telle chute quadratique de complexité pour ce problème simple. Cette chute est moins impressionnante que l'accélération exponentielle dont bénéficie la classe des problèmes traités par Shor, mais elle concerne la recherche d'information, c'est-à-dire une famille de problèmes omniprésents et d'importance cruciale en traitement de l'information.