Ordinateur quantique : pour quoi faire ?

“« Si tout corps est divisible à l’infini, de deux choses l’une : ou il ne restera rien, ou il restera quelque chose. Dans le premier cas, la matière n’aurait qu’une existence virtuelle, dans le second cas on se pose la question : que reste-t-il ? La réponse la plus logique, c’est l’existence d’éléments réels, indivisibles et insécables appelés donc atomes » – Démocrite ”

Ces derniers mois ont été riches en informations plus ou moins sensationnelles relatives à l’arrivée prochaine d’un ordinateur quantique… Pourtant, depuis l’idée originale d’un ordinateur quantique proposée en 1981 par le physicien américain Richard Feynman, la réalité tangible d’un ordinateur quantique ne semble pas dater d’hier. Ainsi, le 19 décembre 2001, une équipe du centre de recherche Almaden d’IBM à San José annonçait la factorisation du nombre 15 par l’algorithme de Shor grâce à un ordinateur quantique de 7 qubits, exploitant le phénomène de résonnance magnétique nucléaire (RMN). Et ce n’était pas la première fois…

Ainsi, dès 1997, une équipe conjointe du MIT et l’Université de Californie, Berkeley, annonçait avoir construit un ordinateur RMN à deux qubits sur lequel ils avaient résolu le problème « un parmi quatre » en une seule étape en appliquant l’algorithme de Grover. Mais il est vrai que les choses semblent s’accélérer : IBM qui annonce en mai dernier avoir créé un ordinateur quantique de 17 qubits, Intel qui annonce en septembre dernier avoir produit un chip quantique de 17 qubits, Google qui parle d’atteindre la « suprématie quantique » en 2017 grâce à une grille quantique de 49 qubits. Sans oublier Microsoft qui annonce un nouveau langage de programmation quantique ainsi qu’une approche très originale appelée « ordinateur quantique topologique » permettant de simplifier considérablement la résolution de la problématique de la décohérence quantique.

Il semble donc finalement que, soit le marketing des sociétés d’informatique soit pris d’une brusque frénésie de communication, chacun des acteurs répondant à ses concurrents, soit que l’ordinateur quantique soit enfin proche de nous… Mais pour quoi faire ? Ne peut-on pas se contenter de la loi de Moore et de l’évolution qui semble inexorable de la puissance de calcul des ordinateurs que l’on a désormais la possibilité de regrouper dans des Datacenters géants, grands comme 20 fois la taille d’un terrain de football grâce au Cloud Computing ?

Le potentiel et les limites d’un ordinateur quantique

Nous venons de fêter il y a 2 ans le 50ème anniversaire de la loi de Moore et de nombreux observateurs suggèrent que nous nous rapprochons de sa fin. La réalité est que nous nous rapprochons des limites de la physique et bientôt nous ne pourrons continuer de récolter indéfiniment les avantages dont nous avons pu bénéficier pendant ces cinq décennies. Et le problème n’est pas que technique… En effet, aujourd’hui, pour la première fois, nous nous heurtons à un mur économique. Nous pouvons certes continuer de construire des transistors plus petits pendant encore quelque temps, mais ceci n’est plus économiquement viable car a) trop cher et b) l’on n’en retire pas la valeur additionnelle ou l’amélioration de performance escomptées.

Pourtant, certains problèmes nécessiteraient encore la durée de vie de l’univers pour les résoudre, même dans la perspective peu probable d’une continuation centenaire de la loi de Moore et l’utilisation de tous les processeurs les plus rapides du monde entier…

Prenons l’exemple du défi RSA-2048. C’est un défi (qui était doté d’un prix de 200 000 $ avant l’arrêt de ce prix en 2007) dans lequel, étant donné un nombre de 2048 bits, il faut identifier deux nombres premiers qui, multipliés entre eux, permettent d’obtenir ce nombre initial (problème de factorisation). Il faudrait littéralement un milliard d’années pour résoudre un tel problème sur un ordinateur classique… Si nous avions un ordinateur quantique, il nous faudrait seulement environ 100 secondes en utilisant l’algorithme de Shor dont nous avons parlé plus haut… Ce problème constitue le fondement du crypto-système RSA, un pilier du commerce en ligne sur Internet…

Il y a donc des problèmes que l’ordinateur quantique permet de résoudre qu’il serait absolument impossible à des ordinateurs classiques de traiter. Essayons de comprendre un peu pourquoi.

« Le zoo de la complexité »

En informatique, la théorie de la complexité vise à étudier formellement les besoins en ressources (temps, espace mémoire, etc.) d’un algorithme pour résoudre un problème algorithmique. Et donc si la réponse à un problème peut être donnée très efficacement, efficacement ou au contraire être inatteignable en pratique, avec des niveaux intermédiaires de difficulté entre les deux extrêmes. De façon plus formelle, la complexité en temps d’un calcul d’une machine de Turing est le nombre d’itérations nécessaires à la machine avant qu’elle ne s’arrête. Et la complexité en espace d’un calcul d’une machine de Turing est le nombre de cases mémoires sur lesquelles la machine a écrit avant qu’elle ne s’arrête.

Dans le but de mieux comprendre comment les problèmes se situent les uns par rapport aux autres, la théorie de la complexité établit des hiérarchies de difficulté entre les problèmes algorithmiques, dont les niveaux sont appelés des « classes de complexité ». Comme nous allons le voir, il existe tout un « zoo de la complexité ».

En effet, une des questions fondamentales que se pose tout informaticien est celle du temps nécessaire pour résoudre un problème et plus précisément à quelle vitesse augmente le temps de résolution d’un problème en fonction de la taille des données. Ici, on mesure le temps en nombre d’étapes élémentaires de calcul que doit franchir l’algorithme pour obtenir la solution. Pour prendre un exemple simple, si vous utilisez la méthode que vous avez apprise à l’école primaire pour multiplier deux nombres de n chiffres, puisqu’il faut multiplier chaque chiffre du multiplicateur par chaque chiffre du multiplicande, cela exige donc n² produits de deux chiffres et le temps de calcul évolue donc comme le carré du nombre de chiffres. On parle ici d’un temps de calcul polynomial car le rythme de l’augmentation est mesuré avec des puissances de n.

Mais imaginons maintenant que, comme on vient de l’évoquer, on cherche à réaliser l’opération inverse, à savoir la factorisation d’un nombre entier en deux nombres premiers. Dans ce cas, les méthodes les plus efficaces connues demandent un temps qui augmente exponentiellement avec le nombre de chiffres du nombre à factoriser. La factorisation est donc un problème beaucoup plus difficile que la multiplication. C’est ce que l’on vient de voir avec le problème RSA-2048.

D’une manière générale, les problèmes que l’on peut résoudre en un temps « raisonnable » même pour n grand sont ceux pour lequel il existe un algorithme dont le temps de calcul augmente de façon polynomiale, c’est‑à-dire comme une puissance fixée de n. Pour ces problèmes, on dit qu’ils appartiennent à la classe des problèmes de complexité « P » (P signifiant ici « temps polynomial »).

Il existe aussi des problèmes comme ceux de la factorisation dont on vient de parler, celui du voyageur de commerce (trouver le circuit de longueur minimale permettant de visiter une seule fois toutes les villes d’une région ou d’un pays) ou encore celui du sac à dos (problème d’optimisation combinatoire qui modélise une situation analogue au remplissage d’un sac à dos, ne pouvant supporter plus d’un certain poids, avec tout ou partie d’un ensemble donné d’objets ayant chacun un poids et une valeur ; les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum) qui, certes, admettent des algorithmes de résolution un peu plus performants que d’essayer une à une toutes les solutions, mais ont quand même un temps de résolution qui augmente exponentiellement avec la taille des données du problème.

Il existe également une classe de problème dite « NP ». NP signifie « temps polynomial non déterministe ». Les problèmes de la classe NP sont ceux pour lesquels une solution proposée peut être vérifiée en un temps polynomial, même si la solution peut être très longue à déterminer. Par exemple, trouver l’itinéraire qui visite chaque ville d’un pays une seule fois peut être très long à trouver mais, si l’on propose un tel itinéraire, il est facile de vérifier que l’itinéraire proposé constitue bien une solution. En résumé, P est la classe des problèmes dont on peut rapidement trouver une solution (rapidement = en temps polynomial) ; NP est la classe des problèmes dont on peut rapidement vérifier qu’une solution est bien une solution.

Cette classe NP regroupe de très nombreux problèmes pratiques. Tous les problèmes P sont a fortiori des problèmes NP, ce qui veut dire que la classe P est contenue dans la classe NP (P⊆NP). En effet, si on peut résoudre un problème rapidement, on peut aussi vérifier sa solution rapidement.

Le défi des problèmes dits « NP-complets »

Stephen Cook, Richard Karp et Leonid Levin ont aussi mis en évidence une classe particulière de problèmes NP : les problèmes dits « NP-complets ». On les appelle ainsi car si l’on trouvait un algorithme efficace pour l’un d’entre eux, on pourrait l’adapter pour résoudre tous les autres problèmes NP (d’où son nom). Le problème du voyageur de commerce que l’on vient de mentionner est un exemple typique de problème NP-complet. Ces problèmes sont, par essence, très difficiles. Mais, il ne faudrait pas penser que, si un problème est NP-complet, il est totalement illusoire de s’y attaquer. Ainsi, lorsque les méthodes de résolution exactes ne sont pas applicables, des algorithmes d’approximations (ou à défaut des heuristiques) permettent de trouver des solutions approchées de l’optimum en un temps raisonnable pour un certain nombre de problèmes NP-complets. Ainsi, il est possible de monter que le problème la « 3‑coloriabilité » (un graphe est-il coloriable avec trois couleurs sans que deux nœuds reliés portent la même couleur ?) qui est un problème NP-complet admet 197 étapes pour le résoudre en moyenne, quel que soit le nombre n de nœuds du graphe. Certains problèmes sont cependant impossibles à approximer, comme le problème du voyageur de commerce.

Savoir résoudre un seul problème NP-complet en temps polynomial déterministe, permettrait de résoudre tous les problèmes NP en temps polynomial déterministe. Inversement d’ailleurs, si on réussissait à démontrer qu’un problème NP-complet ne peut pas être résolu en temps polynomial déterministe, cela signifierait qu’aucun problème NP-complet ne peut l’être. L’existence d’un algorithme « efficace » pour un problème NP-complet signifierait que tous les problèmes NP, y compris NP-complets, sont en fait des problèmes P. Tous ces problèmes se ramèneraient ainsi à des problèmes solubles en un temps polynomial. La question qui se pose est donc la suivante : existe-t-il un tel algorithme ?

Pour le dire autrement, est-ce que P = NP ? En fait, cette question est une question à un million de dollars puisque l’institut Clay de mathématiques à Cambridge aux Etats-Unis l’a sélectionné en l’an 2000 comme constituant l’un des 7 « problèmes du millénaire » dont la résolution est mise à prix pour un million de dollars…

Pourtant, depuis bientôt un demi-siècle que cette question est posée, personne n’a encore trouvé d’algorithme efficace pour un problème NP-complet. La plupart des mathématiciens sont donc convaincus aujourd’hui que P≠NP, même si personne n’est en mesure de comprendre le pourquoi d’une telle inégalité ni de la prouver. Le lecteur expert et très intéressé par cette question pourra lire avec profit le papier très intéressant publié cette année par Scott Aaronson qui est un grand spécialiste du sujet (et des ordinateurs quantiques).

Le rôle de l’ordinateur quantique

Si l’on admet que P≠NP, il ne reste qu’un espoir pour résoudre les problèmes NP-complets en un temps raisonnable (polynomial donc) qui consiste, ce qui n’est pas une mince affaire, à élargir à la fois le concept d’ordinateur et de d’algorithme. Et ce qui est intéressant ici, c’est que les possibilités offertes par un ordinateur quantique semblent répondre exactement à cet objectif. Ainsi, grâce à la mécanique quantique et au principe de superposition, un même état quantique peut posséder plusieurs valeurs pour une certaine quantité observable (spin, position, quantité de mouvement, etc.).

Considérons l’exemple de 250 particules dont le spin est, quand on le mesure, orienté soit vers le « haut » soit vers le « bas ». En mécanique quantique, l’état de cet ensemble de particules est caractérisé par des « amplitudes » qui sont des nombres complexes liés à la probabilité que les particules soient dans un état ou un autre. Pour prendre un exemple, on a une amplitude associée à la possibilité que toutes les particules soient mesurées avec un spin « haut », une autre à la possibilité que toutes les particules soient mesurées avec un spin « bas », ou encore que les 125 premières aient un spin vers le « haut » et les 125 dernières vers le « bas » et toutes les combinaisons du même genre possibles. Au total, on a donc 2²⁵⁰ configurations possibles, ce qui représente environ 10⁸⁰ (c’est plus que le nombre d’atomes contenus dans l’univers visible) et, à chacune de ces configurations, est attribuée une amplitude. L’état quantique des 250 particules correspond donc généralement à une superposition de ces 10⁸⁰ états collectifs de base ; il est spécifié par les 10⁸⁰ amplitudes correspondantes.

Ceci revient à dire qu’il est possible de stocker simultanément 10⁸⁰ nombres sur ces 250 particules qui représentent autant de solutions potentielles à un problème. Ensuite, en effectuant diverses opérations sur ces particules (c’est ce que l’on fait au sein d’un ordinateur quantique en utilisant différentes méthodes que nous n’évoquerons pas ici), on peut faire évoluer l’état du système. Ces modifications affectent simultanément les 10⁸⁰ amplitudes. En d’autres termes, cet « algorithme quantique » traite les 10⁸⁰ solutions potentielles en même temps. Il suffit ensuite de lire l’état quantique des particules à la fin des opérations pour repérer la bonne solution. Le traitement des données étant massivement parallèle, la puissance de calcul est prodigieuse. C’est de ce parallélisme massif que provient tout l’intérêt d’un ordinateur quantique ; mais cela ne se fait pas sans devoir faire face à certaines difficultés…

Ainsi, il y a quelques menus problèmes à résoudre… Selon les lois quantiques, quand on mesure l’état final des particules, on sélectionne l’un des 10⁸⁰ états possibles au hasard (avec une probabilité égale au carré de son amplitude) et l’information sur tous les autres états disparait. On appelle « réduction du paquet d’onde » cette destruction de l’état superposé par la mesure quantique. Utiliser un ordinateur quantique ne semble finalement pas plus efficace qu’un ordinateur classique pour tester une des solutions potentielles au hasard. Dans les deux cas, on obtient un résultat concernant une seule des solutions potentielles… Tout cela pour rien ou si peu me direz-vous, paraphrasant ainsi Shakespeare… Heureusement, on peut quand même tirer parti de la superposition des états quantiques d’une manière un peu plus subtile.

Petit détour par la physique quantique

Un système quantique est décrit par ce que l’on appelle une « fonction d’onde » qui est une fonction du temps et de l’espace dont le carré donne la probabilité de présence du système et qui détermine les probabilités d’obtenir un résultat quand on mesure une grandeur de ce système (énergie, position,…). La fonction d’onde qui décrit une paire d’électrons dispose d’une propriété remarquable : en vertu du principe d’exclusion de Pauli, elle change de signe si l’on permute les deux électrons. Ceci a pour conséquence que les bosses de la fonction d’onde seront transformées en creux et réciproquement lors de cette permutation. Bien entendu, ceci reste sans effet sur le carré de la fonction d’onde et donc sur les probabilités de présence de la paire ou les valeurs d’une quelconque quantité mesurable de ce système quantique.

Par contre, le changement de signe de la fonction d’onde a des conséquences sur l’interférence des électrons de la paire avec d’autres électrons. La combinaison de deux ondes est représentée par la somme de leurs amplitudes respectives : le résultat est donc une onde de plus grande amplitude, là où les bosses coïncident et une onde de plus faible amplitude là où les bosses coïncident avec un creux. Ainsi, au fil des opérations quantiques, les amplitudes associées à tel ou tel état peuvent se compenser, un phénomène nommé « interférence destructive », ou au contraire se renforcer : c’est l’ « interférence constructive ».

Si l’on conçoit bien un algorithme quantique, on peut faire en sorte que l’amplitude associée à une mauvaise réponse s’annule au cours du calcul, tandis que les chemins de calcul conduisant à une réponse correcte ont tous des amplitudes de même signe, ce qui permet de renforcer la probabilité qu’elle apparaisse lorsqu’on mesure l’état final des particules. Le but de l’algorithme quantique est d’augmenter la probabilité de sélectionner la bonne réponse lors de la mesure finale tout en effectuant un minimum de calculs. A ce stade se pose donc la question de savoir pour quels problèmes il est possible d’arriver à un tel résultat en utilisant moins de pas de calcul que dans un algorithme classique. Autrement dit, pour quels problèmes le calcul quantique est-il plus efficace que l’approche classique ?

En 1994, Peter Shor dont on a un peu parlé plus haut, a inventé le premier algorithme quantique permettant d’accélérer de façon spectaculaire la factorisation d’un nombre premier. Cet algorithme – on vient de le voir – permet à un ordinateur quantique de factoriser un nombre de n chiffres en un temps évoluant comme n² (donc en un temps polynomial), là, où le temps de calcul du meilleur ordinateur classique progresse exponentiellement.

Pour ce problème de la factorisation des entiers, l’ordinateur quantique apporte une augmentation exponentielle des performances. Cependant, contrairement à une idée répandue, on ignore à ce jour si le problème de factorisation est NP-complet et on n’a même aucune raison de penser qu’il le soit. En fait, Peter Shor, pour mettre au point son algorithme, a tiré parti de certaines propriétés mathématiques des nombres complexes qui se prêtent bien à la production des interférences destructives et constructives dont on a parlé plus haut, propriétés que les problèmes NP-complets ne semblent pas partager.

Des algorithmes quantiques pour résoudre les problèmes NP-complets ?

Certains algorithmes quantiques permettent donc de passer d’un temps de résolution exponentiel à un temps polynomial mais ce n’est pas le cas de tous, hélas. D’où la question fondamentale : existe-t-il un algorithme quantique efficace pour résoudre les problèmes NP-complets ? Malgré d’intenses efforts de recherche, la question reste toujours sans réponse. Aucun algorithme de ce type n’a été trouvé, même si personne n’a prouvé qu’il n’en existait pas. Ce dont on peut être certain toutefois, c’est qu’un algorithme quantique capable de résoudre de façon efficace un problème NP-complet devra, à l’instar de l’algorithme de Shor, exploiter la structure du problème d’une façon radicalement différente des approches actuelles et donc rentrer fondamentalement dans le monde quantique.

D’une manière générale, il a été démontré qu’il est impossible d’atteindre un gain de performance exponentiel en traitant les problèmes comme des « boîtes noires », c’est‑à-dire comme de simples ensembles de solutions potentielles à évaluer en parallèle, sans aucune structuration. Il est cependant possible d’améliorer, grâce au calcul quantique, les performances dans une approche de type boite noire. C’est le cas de l’algorithme développé en 1996 par Lov Grover et dont on a déjà parlé.

Imaginons que l’on cherche une solution à un problème difficile et que la seule opération que l’on sache effectuer est de tenter d’abord d’en deviner la solution puis de vérifier ensuite sa véracité. C’est ce que l’on fait, par exemple, si l’on cherche un élément dans une liste non triée, comme dans le cas d’un annuaire inversé afin de retrouver une personne d’après son numéro de téléphone. Admettons qu’il y ait n solutions possibles. Si l’on a beaucoup de chance, on va deviner la bonne solution du premier coup, mais dans le pire des cas, il faudra n essais, avec en moyenne n/2 essais.

Lov Grover a mis au moins un algorithme prenant en compte la possibilité de tester toutes les solutions dans une superposition quantique afin de résoudre le problème de la recherche dans une liste non triée. Avec cette méthode, trouver la bonne solution ne prend que √? étapes. L’algorithme de Grover incorpore deux éléments principaux :
1. Une « boîte noire », ou Oracle, qui détermine si un état quantique donné en entrée correspond à un certain critère. C’est cette boîte noire qui permet de particulariser l’algorithme à un problème donné.
2. Un algorithme d’amplification d’amplitude qui permet de rendre exploitable et mesurable l’information donnée par la boîte noire. Cet algorithme est indépendant de la boîte noire, et c’est cette procédure qui nécessite √? itérations.

Passer d’un temps de calcul augmentant comme n/2 à √? constitue une avancée certaine : pour un million de solutions possibles, on passe ainsi de 500 000 à 1000 pas de calcul, ce qui n’est pas si mal. Cependant, l’application de cette méthode à un problème dont le nombre de solutions n croit exponentiellement ne permettra malheureusement pas de passer à un temps de résolution polynomial ; on gardera un temps de résolution exponentiel dont l’exposant sera simplement deux fois plus petit.

L’algorithme de Grover est pourtant le meilleur possible pour ce genre de recherche ; Il a été prouvé en 1999, par Christof Zalka, que l’algorithme de Grover est l’algorithme quantique le plus efficace pour traiter le problème de la recherche non structurée. Il est donc impossible de faire mieux qu’une amélioration quadratique de la complexité, en utilisant le parallélisme du calcul quantique. Ainsi, depuis une vingtaine d’années, divers chercheurs ont démontré que certains algorithmes quantiques étaient bornés en efficacité et qu’il n’était pas toujours possible de bénéficier d’amélioration exponentielle de la vitesse de calcul.

Ce qui est certain, c’est que les possibilités du monde quantique ne suffiront pas à elles seules à résoudre tous les problèmes. Ainsi, de nombreux informaticiens estiment aujourd’hui que, non seulement P≠NP mais aussi que les ordinateurs quantiques ne pourront pas résoudre les problèmes NP-complets en un temps polynomial.

Il existe cependant une classe de problèmes que l’on appelle BQP (Bounded error Quantum Polynomial time) et qui correspond à la classe des problèmes de décision qui peuvent être résolus par un ordinateur quantique en un temps polynomial, avec une probabilité d’erreur d’au plus 1/3 dans tous les cas. Au sein de cette classe de problèmes, on trouve tous les problèmes P ainsi que quelques problèmes NP comme la factorisation des entiers, la simulation des systèmes quantiques et le problème dit du logarithme discret. On pense que la plupart des autres problèmes NP, en particulier les algorithmes NP-complets, ne sont pas inclus dans BQP, ce qui signifie que même un ordinateur quantique ne pourrait les résoudre en un temps polynomial. Par contre, la classe BQP pourrait déborder de NP (les classes NP et BQP sont à l’heure actuelle incomparables), ce qui signifie que les ordinateurs quantiques pourraient résoudre certains problèmes plus rapidement que les ordinateurs classiques ne pourraient en vérifier la réponse et donc, a fortiori, en trouver la solution. Cependant, on ne connait pas encore d’exemple convaincant d’un tel problème.

Il existe quand même de nombreux cas très concrets où l’irruption d’un ordinateur quantique dans notre monde pourrait le changer à jamais… Voici quelques exemples d’applications concrètes d’un ordinateur quantique.

Applications d’un ordinateur quantique

Nous allons présenter dans la suite 4 applications concrètes d’un ordinateur quantique pour lesquelles nous disposons déjà des approches algorithmiques permettant de les mettre en œuvre.

Fixation de l’azote

La fixation de l’azote est un processus au sein duquel l’azote de l’atmosphère est convertie en ammonium. La méthode actuelle fait toujours appel au procédé de Haber qui a été inventé en 1909 et qui nécessite 400°C et 200 atmosphères de pression. Les engrais azotés sont fabriqués en utilisant du gaz naturel pour l’hydrogène et de l’azote extrait de l’air pour former de l’ammoniac comme produit final. L’enjeu est de taille car disposer d’un engrais peu cher signifierait une production plus facile de nourriture et donc de pouvoir lutter contre la faim dans le monde.

Malheureusement, comme on vient de le voir, ce procédé requiert de hautes pressions de hautes températures. On estime que l’utilisation de ce procédé représente aujourd’hui la consommation d’environ 3–5% de la production de gaz naturel du monde entier et entre 1 et 2% de l’énergie mondiale annuelle. De nombreuses recherches ont déjà été effectuées afin de découvrir des catalyseurs permettant la fixation de l’azote, souvent avec le but de la réduction de la quantité d’énergie nécessaire pour cette conversion. Malheureusement, cette recherche a jusqu’à présent échoué pour ne serait-ce qu’approcher l’efficacité et la facilité d’utilisation du procédé de Haber.

Le problème est donc de trouver un catalyseur pour convertir l’azote en ammoniac à température ambiante afin de réduire l’énergie nécessaire pour convertir l’air en engrais. La fixation chimique catalytique de l’azote à des températures beaucoup plus basses que le processus de Haber constitue un effort scientifique en cours mais concevoir un tel catalyseur et simuler les chemins réactionnels entre le catalyseur et l’azote nécessite de tracer des chemins réactionnels précis. Ceci requiert une précision de l’ordre du micro-Hartree alors que la précision actuellement disponible est de l’ordre du milli-Hartree (cela représente une simulation 1000 plus longue que la solution chimique actuelle). C’est cependant faisable en utilisant un ordinateur quantique disposant de 100 à 200 qubits ainsi que l’on démontré les chercheurs de Microsoft Research.

Capture du CO2

Les émissions de dioxyde de carbone ont augmenté de manière continue dans les 200 dernières années d’environ 1 million de tonnes dans les années 1800 à plus de 40 milliards de tonnes aujourd’hui. Pour réduire le réchauffement climatique, nous souhaiterions être en mesure de capturer le carbone directement depuis l’air, depuis n’importe quel emplacement. Ceci est actuellement limité à une capture réalisée depuis des sources ponctuelles, par exemple directement depuis des usines de combustibles fossiles. Réaliser cela n’importe où permettrait de réduire de 80–90 % la quantité de dioxyde de carbone émise dans l’atmosphère mais augmenterait le coût énergétique de 21 à 90%, ce qui n’est guère envisageable. Il faut donc également trouver un catalyseur pour extraire le dioxyde de carbone de l’atmosphère.

Pour cela, il faudrait pouvoir concevoir un catalyseur afin de permettre l’extraction du dioxyde de carbone de l’air. Avec un ordinateur quantique, c’est envisageable en utilisant un ordinateur quantique de 100 à 200 qubits.

Fabrication d’un supraconducteur à température ambiante

Nous aimerions aussi trouver un matériau supraconducteur à température ambiante (qui affiche donc une résistance nulle à température ambiante). Cela permettrait des inventions telles que des réseaux intelligents haute performance, la transmission de courant sans perte et les trains à sustentation magnétique. Quand on sait que 6,5% de l’énergie électrique produite dans le monde est malheureusement perdue dans les lignes de courant, on perçoit tout de suite l’enjeu pour notre société et notre environnement.

Réaliser une telle prouesse nécessiterait d’être capable de résoudre l’équation de Schrödinger pour un système donné afin de prédire son comportement, avec des applications importantes allant des sciences des matériaux aux systèmes biologiques complexes. Mais résoudre l’équation de Schrödinger requiert la connaissance de la fonction d’onde à N corps de l’espace de Hilbert correspondant qui a typiquement une dimension dépendant exponentiellement du nombre de particules. Sa solution pour un nombre raisonnablement grand de particules est donc typiquement impossible, même pour un ordinateur parallèle moderne dans un temps de calcul raisonnable. Un ordinateur quantique permettrait de faire tomber cette limite. Imaginez, par exemple que vous ayez 100 électrons interagissant dans un supraconducteur : sur un supercalculateur traditionnel, la simulation correspondante requiert environ 10³⁴ opérations, alors que sur un ordinateur quantique, elle n’en requiert que 10¹⁰.

Au-delà de cet exemple, il est imaginable de recourir à un ordinateur quantique pour l’appliquer de manière assez large à la science des matériaux en faisant appel à quelques centaines ou milliers de qubits.

Machine Learning

Il est possible de bénéficier d’une accélération substantielle des temps de calcul pour des tâches existantes grâce à un ordinateur quantique. Par exemple d’une accélération quadratique pour des tâches d’échantillonnage ou d’améliorations exponentielles pour des tâches d’inversion bien conditionnées. Il est possible de concevoir de nouveaux modèles pour les données à travers des modèles quantiques que l’on ne peut pas simuler efficacement ou bien en obtenant de nouvelles informations sur la structure des problèmes d’apprentissage. On peut aussi bénéficier d’un entrainement plus efficace avec moins d’approximations, ce qui permet l’obtention de modèles plus précis pour les données mais aussi d’une meilleure compréhension mathématique des algorithmes d’apprentissage.

Ainsi, de nombreux algorithmes bien connus en Machine Learning peuvent tirer largement parti d’un ordinateur quantique. Comme, par exemple, la méthode des k‑plus proches voisins et plein d’autres encore. Cependant l’utilisation d’un ordinateur quantique pour mettre en œuvre des algorithmes de Deep Learning reste problématique dans la mesure où un ordinateur quantique repose essentiellement sur la mise en œuvre d’algorithmes linéaires alors que le Deep Learning repose sur la mise en œuvre d’algorithmes non linéaires. C’est la raison pour laquelle il semble très prometteur de recourir aux Machines de Boltzmann dans un tel cadre.

En guise de conclusion

Comme on vient de le voir, un ordinateur quantique ne permet certainement pas de résoudre tous les problèmes. Il permet cependant d’envisager de résoudre certains des problèmes les plus importants adressés à notre humanité. Car ces problèmes disposent déjà de solutions… si l’on dispose d’un ordinateur quantique assez puissant pour les résoudre.

C’est le physicien danois Niels Bohr qui, parlant de la mécanique quantique disait : « J’ai essayé d’expliquer à ces philosophes l’interprétation de la théorie quantique. Après mon exposé, il n’y a eu ni opposition ni questions difficiles ; mais je dois avouer que c’est précisément cela qui m’a le plus choqué. Car si, de prime abord, on n’est pas horrifié par la théorie quantique, on ne l’a certainement pas comprise. Probablement mon exposé était-il si mauvais que personne n’a compris de quoi il était question. » J’espère donc que certaines des notions que j’ai abordées ici – même de façon simplifiée – vous ont effectivement horrifié ☺…

 

Questions Fréquentes