Le gouvernement français a récemment annoncé un important « Plan quantique » de 1,8 milliard d’euros, dont la majorité sera consacrée aux ordinateurs quantiques. La recherche française compte ainsi se réserver une place de choix dans cette formidable aventure scientifique et technologique que beaucoup comparent aux débuts de la microélectronique du siècle dernier. Il faut dire que les forces en présence sont nombreuses et diverses, comme on peut le voir sur ce graphique.
La raison fondamentale de cette ruée vers le calcul quantique est le phénomène de superposition quantique, qui fait qu’une particule peut être dans plusieurs états quantiques en même temps.
Appliqué à l’informatique, il permet d’obtenir une puissance de calcul naturellement exponentielle. Un registre classique de N bits ne peut stocker qu’une seule série de N valeurs binaires à la fois. Mais un registre de N qubits peut, grâce au phénomène de superposition, stocker toutes les combinaisons à la fois, soit 2N séries de valeurs binaires. Chaque série est associée à une certaine probabilité. « L’art de l’algorithmique consiste à modifier la distribution de ces probabilités pour converger vers la bonne réponse en s’appuyant sur une cascade de portes logiques et le phénomène d’intrication quantique », nous explique François Perruchot, expert en ingénierie quantique CEA-Leti. Le but, c’est qu’au moment de réaliser la lecture du registre — une action qui fait évanouir la superposition quantique — seuls les bons résultats apparaissent.
Un premier cas d’application concret apparaît avec la découverte de l’algorithme de Shor en 1994. Il permet de factoriser beaucoup plus rapidement les grands nombres. Sur un ordinateur classique, la complexité d’une telle opération augmente de façon exponentielle avec le nombre de bits. Si N est le nombre de bits, le nombre d’opérations élémentaires nécessaires sera de l’ordre de 2N. Mais avec l’algorithme de Shor, le nombre d’opérations ne sera plus que de l’ordre de N3. L’accélération est alors exponentielle ou « superpolynomiale ».
Le « killer app », c’est la chimie
Cette découverte intéresse beaucoup les agences de renseignement, car elle permettrait de casser assez facilement le chiffrement à clé publique, comme l’algorithme RSA, qui protège toutes nos communications. Le mieux que les informaticiens ont réussi à faire à l’heure actuelle est de factoriser une clé RSA de 829 bits, ce qui a mobilisé 2700 cœurs de calculs Intel Xeon pendant un an. Aujourd’hui, il est recommandé d’utiliser des clés d’au moins 2048 bits, qui sont impossibles à casser par les supercalculateurs d’aujourd’hui. Mais en 2003, le chercheur Stéphane Beauregard a montré que pour factoriser un entier de N bits, il suffit d’avoir 2N + 3 qubits logiques, soit environ le double. Pour casser une clé de 2048 bits, il faudrait donc 4099 qubits logiques.
Mais l’espionnage, soyons honnêtes, ne fait pas rêver les gens et n’explique pas l’engouement industriel auquel nous assistons dans le domaine de l’informatique quantique. Le domaine qui devrait le plus profiter du calcul quantique est la chimie et la science des matériaux. C’est d’ailleurs à cela que pensait le physicien Richard Feynman quand il avait imaginé pour la première fois, en 1982, l’existence d’un ordinateur quantique. Il estimait alors que seul un système informatique quantique serait capable de simuler des systèmes quantiques physiques.
En effet, pour simuler des molécules et des réactions chimiques, il faut par exemple tenir compte des spins des électrons. Ces derniers ne peuvent que prendre deux valeurs (+1/2 et -1/2). La complexité augmente donc là aussi de façon exponentielle avec le nombre d’électrons (2N). D’après les scientifiques, pour simuler une molécule relativement simple comme la pénicilline (41 atomes, 242 orbites d’électrons), il faudrait un ordinateur avec 1086 transistors. Ce qui est plus que le nombre d’atomes dans l’univers visible. Avec un ordinateur quantique, en revanche, 286 qubits logiques suffiraient en théorie.
Plus intéressant que la pénicilline est la molécule FeMoco. Celle-ci intervient dans la fixation biologique de l’azote atmosphérique par les bactéries sous la forme d’ammoniac. C’est une réaction fondamentale de la nature, mais encore très largement incomprise. L’industrie chimique dispose de techniques de fixation de l’azote, mais elles sont beaucoup moins efficaces que ce procédé biologique. En 2016, un groupe de chercheurs a montré que la simulation de cette molécule pourrait se faire en une vingtaine d’heures avec 2024 qubits logiques, en utilisateur l’algorithme de Trotter-Suzuki. Mais ce n’est pas le seul. Dans ce domaine de la simulation quantique « nous disposons d’algorithmes quantiques très efficaces et nous sommes quasiment certains qu’il n’existe pas d’algorithme classique aussi efficace », souligne Andrew Childs, professeur à l’université de Maryland, à l’occasion de la conférence Q2C 2020.
Des algorithmes à la pelle
Une accélération quantique exponentielle a également été prouvée dès 2009 pour la résolution d’équations linéaires et, par extension, aux équations différentielles, au travers de l’algorithme HHL (Harrow, Hassidim, Lloyd). Le champ d’application de ce type d’algorithmes est évidemment très large : industrie, commerce, apprentissage automatique, etc. Et en réalité, il existe beaucoup d’autres algorithmes quantiques dont on sait qu’ils seront plus efficaces que les algorithmes classiques. Une liste non exhaustive, mais plutôt impressionnante, est disponible sur le site Quantum Algorithm Zoo.
Parmi eux, citons notamment l’algorithme de Grover. Découvert en 1996, il permet de chercher un élément dans un ensemble (l’aiguille dans une botte de foin en quelque sorte). Dans l’informatique classique, la complexité de cette tâche est de l’ordre de N, le nombre d’éléments. Un ordinateur quantique permet de réduire cette complexité à √N. On parle alors d’une accélération polynomiale. « C’est beaucoup moins impressionnant que l’algorithme de Shor, mais c’est déjà très étonnant que l’on puisse arriver à un tel résultat dans ce domaine. Par ailleurs, c’est un problème qui existe dans de nombreuses applications », explique Andrew Childs.
Un idéal hors de portée
Le problème, c’est que tous ces algorithmes ne sont pas utilisables à l’heure actuelle, car les ordinateurs quantiques ne sont pas encore assez efficaces. Le taux d’erreur est encore bien trop élevé et la phase de superposition bien trop instable. Résultat : pour obtenir l’équivalent d’un qubit logique, il faudrait agglomérer des centaines voire des milliers de qubits physiques pour gommer toutes ces imperfections. En 2019, des chercheurs ont montré qu’un ordinateur quantique pourrait casser un code RSA de 2048 bits en l’espace de huit heures… à condition d’avoir 20 millions de qubits physiques. La même année, d’autres chercheurs ont estimé que l’on pouvait simuler la molécule FeMoco en l’espace d’une semaine avec l’aide… d’un million de qubits physiques. Quant à la résolution d’équations linéaires, elle demande de charger beaucoup de données au départ, ce que les ingénieurs pour l’instant ne savent pas faire.
A l’heure actuelle, personne ne sait réellement quand on aura de telles machines. On ne sait même pas si ce sera vraiment possible. Pour autant, les chercheurs ne veulent pas rester les bras ballants et tentent d’implémenter des versions dégradées de ces algorithmes sur les architectures disponibles et en cours de développement, même si elles sont imparfaites. Bref, tant que l’on n’a pas une technologie quantique correcte, on essaye de faire avec ce que l’on a. C’est ce que les spécialistes appellent le NISQ (Noisy Intermediate-Scale Quantum). Pour la simulation de molécules, il existe par exemple l’algorithme VQE (Variational Quantum Eigensolver). Pour les problèmes d’optimisation, il y a l’algorithme QAOA (Quantum Approximate Optimization Algorithm).
L’idée est excellente, mais son résultat est très incertain. « Il est très difficile de prouver [mathématiquement] une accélération dans ces cas-là. Donc en fait, on ne sait pas vraiment », explique Phillip Gerbert, directeur général chez Boston Consulting Group, à l’occasion de la conférence Q2B 2019. Les scientifiques et les ingénieurs avancent donc de manière heuristique, c’est-à-dire par l’expérience. C’est pourquoi Google et d’autres fabricants nouent des partenariats avec les entreprises potentiellement utilisatrices d’ordinateurs quantiques. Ils peuvent ainsi tester leurs algorithmes sur des données réelles et les adapter en conséquence. « Si l’on trouve des algorithmes NISQ efficaces, ce sera probablement pour des problèmes très spécifiques », estime Ryan Babbush, chercheur chez Google Research, à l’occasion de la conférence Q2B 2019.
Pour certains, cette situation fait un peu penser au domaine de l’intelligence artificielle. Là aussi, il a toujours été très difficile de prouver quoi que ce soit à l’avance de façon mathématique. Les formidables progrès des années passées ont été réalisés progressivement, par l’expérience et les essais sur des données réelles. Evidemment, les protagonistes de l’informatique quantique espèrent ne pas subir une traversée du désert comme pour l’intelligence artificielle pendant les années 1980 et 1990, où les développement à totalement stagné. Mais rien n’est moins sûr.
🔴 Pour ne manquer aucune actualité de 01net, suivez-nous sur Google Actualités et WhatsApp.
