Ordinateur quantique et algorithmes : des logiciels à affûter

Africa-Press – Côte d’Ivoire. Disposer d’un ordinateur quantique sans logiciel pour l’exploiter reviendrait à s’asseoir devant un piano sans savoir en jouer: ses performances demeureraient théoriques. Ainsi, tandis que les machines se perfectionnent, toute une recherche s’active pour développer des programmes à la hauteur de leurs potentialités. Ce qui nécessite de revisiter de fond en comble l’algorithmique…

Un algorithme, quantique ou classique, est une série d’opérations destinées à effectuer une tâche bien précise: classer des nombres par ordre croissant ou décroissant, chercher un mot dans une liste, faire des additions… Elles reposent sur la manipulation de bits (pour « binary digit », ou « chiffre binaire »), unité de base de l’information. Un bit peut prendre deux valeurs, 0 ou 1. Cela peut correspondre à la présence (1) ou non (0) d’une tension électrique aux bornes d’un circuit, par exemple.

Utiliser les propriétés ondulatoires des qubits

Toute la révolution quantique vient du fait que ce bit est remplacé par un qubit, comme l’explique Sophie Laplante, chercheuse à l’Institut de recherche en informatique fondamentale (Irif-université Paris Cité). « Leur nature est complètement différente. Les qubits sont des objets quantiques [photon, ion, atome…]. Ils possèdent donc des propriétés quantiques, comme la possibilité d’être dans deux états à la fois. Ainsi, un bit ne peut être que dans l’état 0 ou 1. Tandis qu’un qubit peut valoir 50 % 0 et 50 % 1, ou bien 80 % 0 et 20 % 1.  » Autre différence de taille, les qubits se comportent comme des ondes, à l’instar de toutes les particules. On peut se les représenter comme des vagues, ou des vibrations de l’air. « Tout l’art consiste à utiliser ces propriétés ondulatoires pour réaliser des opérations, essentiellement via le phénomène d’interférence « , résume la chercheuse.

Or troquer des courants électriques pour des ondes rend d’un coup caduques les portes logiques, des mini-circuits électroniques qui réalisent des opérations élémentaires sur les bits. « Prenez une porte logique dite ET, illustre Sophie Laplante. Si deux bits 1 se présentent en entrée, elle renvoie 1 en sortie. Dans tous les autres cas, elle renvoie 0. Elle ne fonctionnera pas avec des qubits car ils ne vaudront pas forcément 0 ou 1, mais une combinaison des deux. L’informatique quantique nécessite donc de redéfinir les portes logiques pour les transformer en portes quantiques.  » Ces portes existent conceptuellement depuis les années 1980: Porte Hadamard, porte Pauli-X, Y et Z, porte Swap… Bien plus exotiques, elles n’ont rien à voir avec les portes logiques.

Ainsi, la porte Hadamard crée des superpositions d’états quantiques au sein d’un même qubit. Les informaticiens les manipulent sur le papier depuis bien avant la mise au point des premiers ordinateurs quantiques. Sans compter que rien n’empêche de simuler sur ordinateur classique le comportement de qubits, jusqu’à une trentaine environ. Cela a suffi pour défricher le domaine dès les années 1990.

Lov Grover, un chercheur indo-américain qui a longtemps œuvré aux laboratoires Bell (New Jersey, États-Unis), est à l’origine d’un célèbre programme capable de rechercher un nom dans une liste. Sa méthode est radicalement différente de celle d’un ordinateur classique qui va interroger la liste jusqu’à ce qu’il trouve le mot cherché. Cela peut nécessiter un million d’opérations s’il y a un million d’objets… Dans le même cas, l’algorithme de Grover n’a besoin que de 1000 opérations.

Un algorithme qui fait émerger la réponse peu à peu

Le principe consiste à coder les mots en langage binaire sur les qubits. Puis de jouer sur le caractère ondulatoire des qubits afin de les faire interférer entre eux. Pour cela, la phase de l’onde associée à l’élément que l’on cherche est inversée. En faisant interférer l’onde « marquée » avec tous les mots de la liste simultanément, l’algorithme fait peu à peu émerger celui recherché car l’onde marquée s’additionne à celle du mot présent dans la liste, et se soustrait aux autres. Forcément, il sort du lot. « Au bout de 1000 itérations, le mot est repéré avec une précision suffisante « , conclut Sophie Laplante.

Autre algorithme fondateur: celui de Peter Shor, un mathématicien américain du Massachusetts Institute of Technology (Cambridge, États-Unis). Il décompose des grands nombres en un produit de nombres premiers (qui ne sont divisibles que par 1 et par eux-mêmes, par exemple: 45 = 3 x 3 x 5). Sa réalisation par des ordinateurs quantiques suffisamment puissants mettrait en péril les protocoles de cryptographie actuels. Il date de 1994. « Il est frappant de constater que les algorithmes principaux ont été trouvés il y a trente ans, constate Simon Apers, chercheur à l’Irif. Beaucoup des travaux réalisés depuis ont pour origine ces algorithmes fondateurs. Ainsi, l’algorithme d’Ambainis, en 2004, est une généralisation de Grover. Il permet de déterminer si une liste comporte deux éléments identiques, sans savoir quels sont ces éléments au départ.  »

Aujourd’hui, une des pistes les plus prometteuses consiste à exploiter l’algorithme HHL, du nom de ses auteurs (Aram Harrow, Avinatan Hassidim et Seth Lloyd), découvert en 2008. Il résout à la manière quantique des équations linéaires du type ax = b. Cela débouche sur de très nombreuses applications, en économie pour l’optimisation de portefeuilles en fonction du risque, pour la simulation de molécules en chimie, l’apprentissage automatique (machine learning)…

Mais selon Simon Apers, les potentialités de HHL sont bien plus grandes. « Cet algorithme offre la possibilité de manipuler des matrices [des tableaux de données], de les multiplier entre elles ou de les inverser à une vitesse exponentielle par rapport aux méthodes classiques… La difficulté consiste à lire le résultat. Car il est présenté sous une forme quantique qui est détruite lorsque l’on cherche à la connaître.  » C’est en effet une autre particularité, fâcheuse, du monde quantique: lire le contenu d’un qubit fait disparaître ses propriétés quantiques, et les informations qu’il contenait.

Malgré cela, c’est l’une des perspectives les plus prometteuses dans ce domaine car elle constitue la base d’une « algèbre linéaire quantique », en termes mathématiques. « Elle pourrait nous mener vers une grande unification des algorithmes quantiques, dans le même esprit que l’unification des théories en physique, avec la possibilité de reformuler les algorithmes existants pour les rendre plus efficaces, mais aussi d’en mettre au point de nouveaux « , ajoute Simon Apers. Le calcul classique stimulé par le quantique.

En attendant, l’algorithmique quantique stimule déjà son homologue classique, avec des conséquences bien plus proches de nous qu’on ne l’imagine, comme les algorithmes de recommandation des plateformes TV… « À l’origine, on pensait que seule la voie quantique pouvait mener à des algorithmes de recommandation vraiment efficaces, explique Simon Apers. Mais lorsqu’une étudiante de l’Université du Texas, aux États-Unis, Ewin Tang, a voulu démontrer cela en 2018 – à 17 ans ! -, elle est au contraire parvenue à trouver une méthode classique aussi bonne que la version quantique.  » Résoudre des problèmes par l’ordinateur quantique mais sans l’ordinateur quantique, quoi de plus quantique après tout.

Pour plus d’informations et d’analyses sur la Côte d’Ivoire, suivez Africa-Press