Pour mieux comprendre l’ordinateur quantique et la course technologique qu’il génère, nous vous proposons ici le quatrième opus de notre série. Celui-ci examine comment les ordinateurs quantiques pourraient changer la donne en cryptographie et en intelligence artificielle – deux domaines qui pourraient paraître spécifiques mais qui imprègnent déjà complètement nos vies numériques. Il fait suite à des articles sur la naissance du concept d’ordinateur quantique, sur les défis techniques à relever pour en construire « en vrai », et sur la consommation énergétique de tels futurs ordinateurs.
Après l’intelligence artificielle, l’étoile naissante de l’informatique est l’ordinateur quantique.
Il pourrait changer la donne – une fois qu’on saura le fabriquer – notamment en cryptographie, la science des codes secrets. Discrètement, celle-ci imprègne déjà tous les domaines de notre vie numérique et permet d’assurer notre cybersécurité, par exemple avec le chiffrement des cartes bancaires, des signatures électroniques et des communications sécurisées sur Internet – vitales pour toute personne qui habite dans un régime totalitaire et qui ne plaît pas au régime.
Améliorer la sécurité des échanges chiffrés est au cœur des recherches en cryptographie. Et notamment, les problèmes cryptographiques sont de ceux qui pourraient démontrer une potentielle « suprématie » des ordinateurs quantiques sur les ordinateurs classiques.
En effet, il n’est pas facile de démontrer que les ordinateurs quantiques sont avantageux par rapport aux ordinateurs que nous utilisons actuellement. On envisage deux voies : gagner plusieurs ordres de grandeur en efficacité sur l’ordinateur classique au prix de grands centres de calcul quantique, ou simplement calculer plus vite avec des ordinateurs petits qui verront le jour plus tôt.
Par exemple, quand Google a affirmé avoir atteint la suprématie quantique avec son ordinateur Sycamore en 2019, les critiques ont démontré que l’on pouvait trouver un meilleur algorithme classique. De nouveau, pour prouver la suprématie quantique d’un ordinateur à photons en 2020, ses auteurs ont implanté et testé le meilleur algorithme classique sur un superordinateur afin d’offrir une comparaison juste… mais un des auteurs a précisé que la facture des calculs classiques a été de l’ordre d’un million d’euros, et que la décision de pousser les calculs si loin a été prise suite à des demandes de chercheurs d’autres universités.
Cette question est celle de l’« optimalité des algorithmes ». Pour l’instant, on ne connaît aucun problème pour lequel on a à la fois un algorithme quantique plus rapide que le meilleur algorithme classique connu, et une preuve que ledit algorithme classique est effectivement optimal dans le monde classique.
[Près de 80 000 lecteurs font confiance à la newsletter de The Conversation pour mieux comprendre les grands enjeux du monde. Abonnez-vous aujourd’hui]
Certains problèmes informatiques sont dits « difficiles mais sans preuve d’optimalité » : alors qu’ils sont utilisés par de nombreux programmes informatiques et que des centaines de chercheurs et ingénieurs travaillent dessus depuis des décennies, on ne trouve pas de meilleur algorithme.
Ces problèmes sont pertinents pour l’industrie comme ceux de la planification de la flotte d’une compagnie aérienne. Si l’ordinateur quantique accélère un de ses problèmes, on aura une preuve « industrielle » de son efficacité plutôt qu’une preuve théorique.
Des problèmes cryptographiques pour démontrer la suprématie quantique
La cryptographie est une bonne source de tels problèmes « difficiles ».
Par exemple, la factorisation est le problème qui, étant donné le résultat de la multiplication de deux nombres premiers (par exemple 17 fois 11 égal 187), demande de trouver ces nombres. C’est un procédé très important car il sous-tend le codage informatique de nombreux échanges cryptés actuels, à commencer par le protocole « RSA » qui est actuellement utilisé pour la quasi-totalité des cartes bancaires et par le protocole Internet « https ».
La factorisation a été présentée comme un problème difficile par Friedrich Gauss dès 1801 dans son livre Disquisitiones arithmeticae et a fait l’objet de publications scientifiques tout au long du XXe siècle. Au XXIe siècle, on continue d’écrire des centaines d’articles pour présenter des améliorations des meilleurs algorithmes de factorisation. La compagnie RSA Security a offert des prix entre 1 000 et 200 000 dollars pour factoriser une liste d’entiers et l’agence française de cybersécurité ANSSI évalue le niveau de sécurité offert par les logiciels informatiques sur la base des records de calcul de factorisation obtenus par les chercheur·e·s.
Si l’avantage quantique est atteint sur le problème de la factorisation, ce sera un résultat percutant pour la recherche… avec de nombreuses implications pour la cybersécurité.
C’est dans ce contexte que Shor a présenté en 1994 son algorithme quantique de factorisation, extrêmement rapide. Plus précisément, le temps de calcul de l’algorithme de Shor augmente peu quand on augmente le nombre de chiffres du nombre à factoriser alors que le temps nécessaire pour le meilleur algorithme classique augmente très vite et c’est difficile de faire des factorisations plus grandes : le record de factorisation est passé seulement de 232 à 250 chiffres entre 2009 et 2020.
Deux poids, deux mesures
Le bémol d’utiliser la factorisation pour prouver la suprématie quantique est la taille requise pour les ordinateurs quantiques. Lors d’une compétition de factorisation entre un ordinateur quantique et un superordinateur classique, on peut toujours augmenter la taille de l’ordinateur classique en ajoutant plus de cœurs.
Par exemple, un temps affiché de 1 000 ans CPU (le CPU est l’unité de calcul d’un ordinateur) traduit en réalité cinq semaines sur un superordinateur de dix mille cœurs. Dans un certain sens, du point de vue de la factorisation, la taille d’un ordinateur classique se mesure en heures. Quant à l’ordinateur quantique, dans l’état actuel de la technologie quantique, seul le nombre de qubits compte.
Par exemple, il faut un minimum d’un million de qubits pour factoriser un entier de 2048 bits – utilisé actuellement sur Internet et sur les cartes bancaires – et un tel ordinateur quantique prendra un seul jour de calcul. Un ordinateur quantique plus petit ne peut pas faire le calcul, peu importe le temps disponible. Sachant qu’une carte bancaire est valable deux ans, on voit que le temps de calcul n’est pas un point de blocage.
En d’autres termes, actuellement, la difficulté d’un calcul se mesure en qubits pour le quantique et en temps pour le classique.
Ce tableau montre le temps nécessaire à un ordinateur classique avec un des meilleurs logiciels de factorisation pour factoriser un nombre à N chiffres, ainsi que le nombre de qubits nécessaires à un ordinateur quantique (qui a besoin d’environ 8×N « qubits sans erreurs ») :
Au-delà de la factorisation
Un autre problème cryptographique moins connu mais plus prometteur pour prouver l’avantage quantique, car la différence entre temps de calcul (classique) et nombre de qubits (quantique) est plus marquée, est l’« équation de Pell » ou « le calcul du nombre de classes et des unités », pour lequel un algorithme quantique a été proposé mais pas encore testé expérimentalement. Voici une comparaison entre le temps nécessaire à un ordinateur classique et la taille d’un ordinateur quantique dans ce cas :
On peut conclure que l’avantage quantique sera ici à peu près atteint avec un ordinateur ayant 1600 qubits. Si l’avantage est contesté, on augmentera sensiblement le nombre de qubits, l’essentiel est d’obtenir des résultats « comparables ». Cela permettra de résoudre l’équation de Pell pour un entier d de 100 chiffres décimaux, ce qui est très difficile sur le classique et près des records.
Des ordinateurs quantiques sans erreurs
Les ordinateurs quantiques sont sensibles aux moindres perturbations des champs électromagnétiques.
Pour éviter les erreurs de calcul, des qubits « sans erreur », appelés aussi « qubits logiques » sont réalisés à l’aide de « codes correcteurs quantiques ». Le nom est inspiré des codes correcteurs classiques dont l’exemple le plus connu est le bit de parité : tous les 8 bits enregistrés sur le disque d’un ordinateur, on retrouve un neuvième bit qui fait que la somme des 9 bits soit paire. Ainsi, 8 bits logiques sont réalisés par 9 bits physiques.
Dans le cas de l’ordinateur quantique, on estime qu’il faut entre 5 et 48 qubits physiques pour un qubit logique – c’est-à-dire que les 1600 qubits logiques qui seraient nécessaires pour démontrer une suprématie quantique avec les problèmes de classe seront réalisés par un ordinateur de 78 000 qubits physiques.
Or, le record actuel est de 127 qubits pour l’ordinateur Eagle construit par IBM. Le nombre est tellement faible que l’on préfère parler de « preuve de concept » : un ordinateur quantique fonctionnel devrait avoir plus de 10 000 qubits.
Dans le scénario le plus optimiste, celui d’un doublement du nombre de qubits tous les ans, les premiers calculs quantiques du problème de classe qui se comparent aux calculs classiques seront possibles au plus tôt dans dix ans.
Contourner la question de la suprématie quantique
Mais l’ordinateur quantique offre d’autres perspectives. Notamment, si un ordinateur quantique de petite taille voit le jour et qu’il offre déjà un gain de temps de calcul à cette taille limitée, on pourra s’affranchir de la question de la suprématie quantique.
On peut alors chercher des applications industrielles de ce gain limité. Voici l’idée de Seth Lloyd et ses collègues qui ont proposé en 2017 des algorithmes quantiques pour l’intelligence artificielle. L’idée serait dans ce cas qu’un logiciel d’apprentissage machine installé sur un ordinateur classique utilise un ordinateur quantique en guise de co-processeur.
Un facteur deux par exemple pour l’intelligence artificielle peut sembler modeste comparé aux avantages quantiques annoncés par Sycamore et ses successeurs, mais il a été suffisant pour justifier un investissement important – une usine de circuits intégrés coûte plusieurs milliards d’euros – de la part du constructeur de voitures électriques Tesla.
L’intelligence artificielle a changé déjà le monde et continue de nous surprendre. À travers elle, l’ordinateur quantique pourrait bien avoir un impact qui n’a pas été imaginé par les pionniers de la physique quantique.