L’algorithme quantique de Shor

L’ordinateur quantique

La physique quantique est considérée comme l’une des théories physiques les plus mystérieuses des temps modernes. Pour comprendre le fonctionnement d’un ordinateur quantique, il faut se placer à l’échelle atomique et subatomique, dans le monde physique des électrons, des photons et autres particules élémentaires. La physique quantique, développée au début du XX^e siècle, décrit certains phénomènes fortement contre-intuitifs se déroulant à cette échelle. Par exemple, la physique quantique prévoit que certaines particules puissent être dans une superposition d’états. Concrètement, un électron peut donc être excité ou au repos en même temps, un photon peut être à la fois présent et absent. C’est difficile d’imaginer ce qu’être et ne pas être en même temps veut dire. Schrödinger, l’un des pères de la physique quantique, imagine un chat mort et vivant à la fois pour expliquer ce phénomène. Ce qui n’est certainement pas possible pour les chats l’est par contre pour des particules élémentaires obéissant aux lois de la physique quantique. Par exemple, 30 particules subissant ces effets quantiques peuvent exister dans des milliards d’états différents. Il est alors tentant d’utiliser ce phénomène pour faire de nombreux calculs en même temps grâce à la superposition quantique. Par contre, ces effets quantiques sont extrêmement fragiles. N’importe quelle interaction avec l’environnement extérieur les détériore.

L’idée de faire du calcul quantique apparaît dans les années 1970. On a développé des modèles théoriques qui décrivent très bien ce que pourrait faire un tel ordinateur quantique, quel temps de calcul est nécessaire pour réaliser ces opérations et avec quelles ressources. Dès 1984, les cryptologues Charles H. Bennett et Gilles Brassard proposent le premier protocole d’échange de clés sécurisé grâce à la communication quantique. Ce protocole ne nécessite pas de calcul quantique à proprement parler mais utilise des états quantiques uniquement pour détecter quiconque voudrait espionner des communications. Le point culminant de ces recherches est la découverte en 1994 d’un algorithme quantique de factorisation par Peter Shor, chercheur au MIT. Cet algorithme montre qu’en contrôlant quelques milliers de particules, on serait capable de résoudre le problème de factorisation sur un ordinateur quantique et ainsi de casser une grande partie des systèmes de sécurité informatique utilisés aujourd’hui.

L’algorithme quantique de Shor

L’algorithme de Shor vise à résoudre le problème de factorisation, utilisé dans la majorité de nos systèmes de sécurité informatique. Concrètement, étant donné deux nombres p et q premiers — c’est-à-dire divisibles uniquement par eux-mêmes et par 1 — il est facile de calculer le produit N = p x q avec des algorithmes rapides de multiplication. Le problème de factorisation est le problème inverse : étant donné N, retrouver p et q. Ce problème est, aujourd’hui, difficile à résoudre. On est capable avec les algorithmes et les supercalculateurs d’aujourd’hui, de factoriser des nombres ayant environ 250 chiffres. Par contre, dès qu’il y a un trop grand nombre de chiffres, disons au-delà de 500 chiffres, cette factorisation devient impossible…

En 1994, Peter Shor a montré qu’avec un ordinateur quantique, on pourra factoriser des nombres qui auront des milliers voire des millions de chiffres. Shor utilise le lien entre le problème de factorisation et la recherche d’une période dans une fonction. En utilisant la superposition quantique, il montre comment faire résonner des états quantiques autour de la période de la fonction pour la retrouver, et ensuite utiliser ce résultat pour factoriser rapidement. À titre de comparaison, les meilleurs algorithmes actuels pour factoriser un nombre de 600 chiffres ont besoin de millions de millions d’années pour factoriser un tel nombre, temps évidemment inatteignable alors qu’un ordinateur quantique entièrement fonctionnel pourrait effectuer cette opération en quelques minutes.

La découverte de Shor est l’une des motivations principales pour construire un ordinateur quantique. Quelle conséquence cet algorithme a-t-il sur les systèmes de sécurité informatique ?

Faut-il modifier les systèmes de sécurité informatique ? Ou pourquoi être en avance sur son temps n’est plus suffisant.

De nombreux systèmes de sécurité informatique reposent sur des hypothèses calculatoires, c’est-à-dire sur l’incapacité des ordinateurs actuels à résoudre certains problèmes mathématiques. On entend souvent parler d’attaques cryptographiques et de failles de sécurité mais très rarement d’attaques sur ces hypothèses calculatoires proprement dites. En clair, les fondements mathématiques de nos systèmes de sécurité informatique sont relativement solides. Par exemple, l’algorithme cryptographique RSA, utilisé dans de nombreux protocoles sur Internet, repose sur la difficulté de factoriser de grands nombres.

L’arrivée d’un ordinateur quantique diminuerait donc fortement les hypothèses calculatoires sur lesquelles on peut se baser pour garantir la sécurité de nos systèmes informatiques. En particulier, RSA, ainsi que d’autres systèmes basés sur le logarithme discret par exemple, sont inutilisables. En quoi ces attaques nous concernent-elles ? Ne peut-on pas attendre l’arrivée éventuelle d’un ordinateur quantique et modifier nos systèmes de sécurité le cas échéant ?

Pendant longtemps, on considérait qu’être en avance sur les attaques potentielles était suffisant. Par exemple, il est aujourd’hui possible de casser les schémas utilisés en cryptographie il y a 20 ou 30 ans, sans que cela ne pose un grave problème de sécurité. En effet, tous les systèmes obsolètes ont été depuis longtemps remplacés.

Par contre, actuellement, une grande quantité de données sensibles et chiffrées sont accessibles facilement. Quelqu’un pourrait stocker ces données et attendre 20-30 ans des avancées potentielles — comme l’ordinateur quantique — pour déchiffrer ces données. Ceci peut devenir très problématique si ces données sensibles sont par exemple des données médicales, politiques ou d’autres données sensibles qui doivent rester secrètes pendant longtemps.

Heureusement, les ordinateurs quantiques ne sont pas tout-puissants. Il existe en effet des problèmes calculatoires qui restent difficiles même pour un ordinateur quantique. Un effort important est fait pour étudier précisément ces systèmes cryptographiques résistant à l’ordinateur quantique, et la normalisation de tels systèmes est en cours. Notamment, un système d’échange sûr contre les ordinateurs quantiques a été utilisé dans le navigateur Chrome, ce qui montre leur faisabilité pratique. Le NIST (National Institute of Standards and Technologies) vient de lancer une campagne internationale pour standardiser la cryptographie sûre contre les ordinateurs quantiques, ce qui montre le sérieux avec lequel cette menace est considérée.

Des perspectives pour l’ordinateur quantique

On entend beaucoup parler de l’ordinateur quantique. Néanmoins, sa concrétisation technologique semble encore lointaine. En effet, les particules quantiques en superposition sont extrêmement fragiles. N’importe quelle interaction avec l’environnement détériore cette superposition jusqu’à enlever les propriétés quantiques de ces particules. On sait manipuler quelques états quantiques en même temps mais la route est encore longue avant de pouvoir calculer efficacement avec un ordinateur quantique. La seule chose qu’on arrive assez bien à faire est la communication quantique, qui permet de faire de l’échange de clés sécurisé. Mais là encore, l’absence de répéteurs dans les réseaux quantiques limite fortement les distances, et donc l’applicabilité de ces schémas.

Jusqu’à récemment, la construction d’un calculateur quantique relevait principalement du domaine académique mais maintenant, tous les géants de l’informatique, Google, Microsoft, IBM et bien d’autres, se sont lancés dans la course à la construction d’un ordinateur quantique et y investissent des milliards de dollars. IBM a annoncé en novembre 2017 avoir construit un ordinateur quantique de 50 qubits et Google a présenté en mars 2018 l’ordinateur Bristlecone capable d’opérer sur 72 qubits. Ces ordinateurs n’ont pas encore pu être testés donc on ne connait pas encore le taux d’erreur ou la durée de vie de ces qubits. En tout cas, l’enjeu principal est de trouver une technologie qui passe bien à l’échelle, aussi bien en termes de nombre de bits quantiques que de durée de vie des états quantiques utilisés.

L’ordinateur quantique capable de faire fonctionner l’algorithme de Shor est donc largement hors de portée. Néanmoins, il y a aussi d’autres applications, notamment pour la simulation de molécules chimiques, pour la conception de nouveaux médicaments, ou pour les algorithmes d’apprentissage par exemple. Avec quelques centaines de bits quantiques stables, on pourrait obtenir des gains importants en terme de puissance calculatoire. En parallèle, D-WAVE, une entreprise canadienne, annonce faire tourner une machine avec plus de 1000 bits quantiques simultanément. Cette machine n’est néanmoins pas un calculateur quantique complet et s’attaque à un problème d’optimisation très particulier via du recuit simulé quantique.

Au final, l’ordinateur quantique sera t-il l’ordinateur de demain ou restera-t-il dans le domaine de la science-fiction ? Il est difficile de répondre à cette question tant les défis technologiques semblent immenses. Néanmoins, les différentes approches et l’investissement massif mis dans cet objectif sont très encourageants. Un enjeu à court terme est la simulation de certaines molécules soumises aux effets de la physique quantique, avec des applications en chimie pour la confection de médicaments ou de batteries par exemple. Si l’on arrive d’ici 5 à 10 ans à atteindre cet objectif en utilisant un ordinateur quantique rudimentaire, alors ce sera de très bonne augure pour l’arrivée future d’un ordinateur quantique plus puissant dont l’existence aura des conséquences encore largement inexplorées.