Visiter Bibliothèque de Classiq pour une implémentation de l'algorithme de Shor
‍

Toute personne intéressée par l'apprentissage de l'informatique quantique ne peut éviter d'entendre parler de l'algorithme de factorisation de Shor. Il s'agit de l'un des rares algorithmes quantiques classiques, ce qui signifie qu'il reste l'un des rares exemples d'avantage en matière de calcul quantique. En d'autres termes, l'algorithme peut calculer de manière quantique quelque chose qui est plus difficile et plus lent à calculer de manière classique. En fait, cet algorithme particulier peut calculer quelque chose qui est, pour autant que nous le sachions, impossible à réaliser de manière classique à toute échelle utile.

Parmi les algorithmes mentionnés dans les manuels, l'algorithme de factorisation de Shor sort du lot. Il y a deux excellentes raisons à cela. Premièrement, il peut factoriser les nombres exponentiellement plus rapidement que n'importe quel algorithme classique connu. Si tous les algorithmes quantiques classiques offrent des avantages en termes de calcul, l'algorithme de Shor fait partie de l'élite des quelques algorithmes offrant une vitesse exponentielle, ainsi que de l'élite des quelques algorithmes ayant une application pratique. Plus important encore, sa capacité à factoriser les nombres dans des délais raisonnables menace directement les cryptosystèmes les plus populaires au monde.  

On ne saurait trop insister sur l'importance de ce phénomène. Le cryptage RSA, qui protège les transactions financières dans le monde entier, fonctionne en multipliant deux énormes nombres premiers. Les nombres premiers ne peuvent pas être divisés en nombres entiers autres qu'eux-mêmes et le chiffre un. Leurs produits sont si grands qu'il n'existe aucun moyen connu de les factoriser efficacement de manière classique. La factorisation est une multiplication inversée qui détermine les nombres premiers utilisés, ce qui permet le décryptage non autorisé des communications internet.

Cet article de blog se réfère occasionnellement à l'algorithme en question comme Algorithme de factorisation de Shor, et non simplement Algorithme de Shor, parce qu'il existe également un code de correction d'erreur quantique portant le nom de Shor, avec le même homonyme, qui a été découvert à la suite de la publication de l'algorithme de factorisation. Pour cet article, afin d'éviter toute ambiguïté, sachez que l'algorithme de Shor et l'algorithme de factorisation de Shor font référence au même algorithme.

Qu'est-ce que l'algorithme de Shor en informatique quantique ?             

L'algorithme de factorisation de Shor a mis l'informatique quantique sur la carte proverbiale. En menaçant la version animée, les gouvernements nationaux, des industries entières et le grand public ont été forcés de prendre conscience de cette technologie relativement nouvelle. Des décennies plus tard, cet algorithme reste le porte-drapeau des algorithmes quantiques. Des efforts considérables sont déployés depuis longtemps pour protéger les systèmes financiers mondiaux, la sécurité nationale et toutes les autres utilisations de la cryptographie. Il existe un danger géopolitique clair et actuel que quiconque, en particulier un acteur étatique, développe une puissance de calcul quantique suffisante pour utiliser l'algorithme de Shor avant que des cryptosystèmes à sécurité quantique puissent être universellement déployés.

Presque aussi important, l'algorithme de Shor a conduit à l'investissement actuel de milliards de dollars dans les technologies quantiques, y compris l'informatique quantique. Trois décennies après la découverte de l'algorithme, la recherche se poursuit pour trouver d'autres applications pratiques pour lesquelles des accélérations exponentielles peuvent être réalisées. Si au moins un algorithme peut y parvenir, on pense qu'il doit y en avoir d'autres. Après toutes ces années, les candidats les plus probables empruntent à l'algorithme de Shor.

Pour écouter l'histoire complète de la découverte de l'algorithme de factorisation de Shor, racontée par le professeur Peter Shor lui-même, regardez ici sur Qiskit's YouTube, ou pour écouter une version animée plus courte de cette histoire, regardez ici.

Comment fonctionne l'algorithme de Shor ?

La factorisation des nombres avec l'algorithme de Shor commence par la sélection d'un nombre entier aléatoire plus petit que le nombre à factoriser. Le plus grand diviseur commun (PGCD) de ces deux nombres, le nombre aléatoire et le nombre cible, est alors utilisé pour déterminer si le nombre cible a déjà été factorisé accidentellement. Pour les petits nombres, c'est une possibilité. Pour les nombres plus importants, un superordinateur pourrait être nécessaire. Et pour les nombres dont on pense qu'ils sont cryptographiquement sûrs, un ordinateur quantique sera nécessaire.

Le rôle de l'ordinateur quantique est de déterminer la période du nombre à factoriser. Les résultats du calcul déterminent si un nouvel entier aléatoire doit être testé ou si les facteurs recherchés ont été découverts. Une fois l'entier cible factorisé, le rôle de l'algorithme de Shor est conclu

À un niveau élevé, tout ce processus peut sembler assez simple. Et, à un niveau élevé, il l'est. Cependant, l'explication détaillée de chaque étape peut être décomposée en une série de cours. La mise en œuvre de l'algorithme peut être réalisée après avoir suivi un court tutoriel, mais la compréhension complète de l'algorithme peut nécessiter de nombreuses heures d'étude. 

Pour une explication mathématique de l'algorithme de factorisation de Shor, voir ici. Sinon, c'est l'algorithme de Shor expliqué en quelques mots.

Comment l'algorithme de Shor est-il mis en œuvre ?                                   

L'algorithme de factorisation de Shor n'est pas simple à mettre en œuvre. Tout d'abord, l'algorithme se compose de trois éléments principaux : un qui utilise le calcul classique, un qui utilise le calcul quantique et un autre qui utilise le calcul classique. Dans l'ensemble, l'algorithme comporte six étapes importantes, résumées ci-dessus.

Pour ajouter à cette complexité, la composante quantique de l'algorithme de factorisation de Shor comporte quatre sous-composantes, dont chacune pourrait faire l'objet d'un article d'explication à part entière. Et si deux de ces sous-composants quantiques sont relativement simples à expliquer, les deux autres sont des sous-programmes quantiques incroyablement importants. En fait, on peut dire qu'il s'agit des deux sous-programmes quantiques les plus importants.

L'un des sous-composants quantiques critiques est appelé estimation quantique de la phase (QPE). Ce qu'il faut retenir ici, c'est qu'elle effectue l'arithmétique modulaire nécessaire pour trouver la période du nombre à factoriser. En d'autres termes, c'est de là que vient la puissance de factorisation de l'algorithme de Shor. 

L'autre sous-composant quantique clé s'appelle la transformée de Fourier quantique inverse (iQFT). En termes simples, l'iQFT prend le résultat quantique de l'arithmétique modulaire qui le précède immédiatement et le transforme en informations classiques qui peuvent être extraites du circuit quantique par le biais d'un processus connu sous le nom de mesure.

Au total, l'algorithme de factorisation de Shor commence par quelques étapes classiques. La composante quantique trouve ensuite la période du nombre à factoriser. Cela se fait par le biais de l'arithmétique modulaire quantique, dont le résultat est converti d'information quantique en information classique afin d'être utilisable. Enfin, il y a encore quelques étapes classiques. Si la réponse n'est pas trouvée et que le nombre ne peut donc pas être factorisé, l'algorithme dans son intégralité est ajusté et répété.

‍

Combien de qubits sont nécessaires pour l'algorithme de Shor ? 

Pour répondre à cette question, il faut d'abord faire la distinction entre les qubits physiques et les qubits logiques. Tous les qubits actuels sont des qubits physiques. Ils sont extrêmement "bruyants", ce qui signifie qu'ils sont sujets à des erreurs. Les résultats d'un calcul quantique de quelque importance ne permettent pas de distinguer les réponses correctes des réponses incorrectes. Toutes les solutions possibles ont la même probabilité d'être correctes, ce qui revient à ne pas avoir de réponse du tout.

C'est là que les qubits logiques entrent en jeu. Les qubits physiques doivent être connectés et structurés de manière à ce qu'ils fournissent collectivement une correction d'erreur suffisante pour être considérés comme collectivement "tolérants aux pannes". À ce stade, ces qubits collectifs sont appelés "qubits logiques", ou parfois "qubits parfaits".

Ces qubits logiques sont des abstractions. Un circuit quantique actuel avec cinq qubits représente cinq qubits physiques très bruyants et sujets aux erreurs. Les concepteurs d'algorithmes quantiques du futur proche voudront que ces cinq qubits représentent des qubits logiques, tolérants aux pannes et exempts d'erreurs. Les estimations varient quant au nombre de qubits physiques nécessaires pour représenter un qubit logique, mais un nombre raisonnable est de 1 000. La plupart estiment qu'un ordinateur quantique aura besoin d'environ 1 000 qubits physiques pour représenter un seul qubit logique.

Pour se rendre compte de l'ampleur du défi, il suffit de rappeler que le plus grand ordinateur quantique actuel ne possède que 127 qubits physiques. Et bien qu'IBM ait pour objectif de dévoiler un appareil de 1 000 qubits d'ici l'année prochaine, il ne s'agit encore que de 1 000 qubits physiques. Il reste encore beaucoup à faire pour concevoir le premier qubit logique.

Les estimations du nombre de qubits nécessaires à l'algorithme de factorisation de Shor varient considérablement. Tout d'abord, il faut veiller, comme indiqué, à distinguer les estimations pour les qubits logiques des estimations pour les qubits physiques. Selon les objectifs des chercheurs, le nombre de qubits requis peut être réduit, en sacrifiant le temps d'exécution et la profondeur du circuit. D'autre part, le nombre de qubits peut être considérablement augmenté, ce qui réduit le temps d'exécution et la profondeur du circuit. Les différences sont que les nombres de qubits inférieurs seront disponibles plus tôt, tandis que les durées d'exécution les plus rapides seront les plus avantageuses. Voici une sélection d'estimations.

Dans un article du 1er août 1996 intitulé "Efficient networks for quantum factoring", rédigé par David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni et John Preskill, les auteurs ont estimé que la factorisation d'un nombre de K bits prendrait ^K3 de temps et nécessiterait 5K+1 qubits logiques. Factoriser un nombre de 2 048 bits, c'est-à-dire casser le cryptage RSA, prendrait donc 8,6 milliards de temps et nécessiterait 10 241 qubits logiques, soit environ 10 millions de qubits physiques. Malheureusement, on ne sait pas exactement quelle serait la durée de 8,6 milliards de temps, car les différentes technologies de qubits fonctionnent à des vitesses différentes.

Puis, dans un article du 21 février 2003 intitulé "Circuit for Shor's algorithm using 2n+3 qubits" par St'ephane Beauregard, les auteurs ont estimé que la factorisation d'un nombre de K bits nécessiterait 2n+3 qubits logiques. La factorisation d'un nombre de 2 048 bits ne nécessiterait donc que 4 099 qubits logiques, soit environ 4 millions de qubits physiques. Là encore, aucun qubit logique n'existe aujourd'hui. Cet article a néanmoins permis de rapprocher l'algorithme de factorisation de Shor de sa mise en œuvre. 

Puis, dans un ouvrage de mai 2014 intitulé "Fast quantum modular exponentiation architecture for Shor's factoring algorithm" (pp0649-0682) d'Archimedes Pavlidis et Dimitris Gizopoulos, les auteurs ont proposé une implémentation 9n+2, en ajoutant un nombre important de qubits pour réduire la profondeur du circuit. Pour casser un cryptage RSA de 2 048 bits, il faudrait 18 434 qubits logiques, soit environ 18 millions de qubits physiques. L'une des raisons de minimiser la profondeur des circuits est que les qubits perdent leur "cohérence" avec le temps. Plus il faut de temps pour exécuter un circuit, comme le détermine, en partie, la profondeur du circuit, plus le bruit peut s'infiltrer dans le système et plus les erreurs peuvent apparaître dans les résultats. Aujourd'hui encore, l'un des moyens de réduire les erreurs consiste à minimiser la profondeur des circuits.

Plus récemment, dans un article du 13 avril 2021 intitulé "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" par Craig Gidney et Martin Eker, les auteurs estiment que casser le cryptage RSA, en particulier, nécessiterait environ 20 000 qubits logiques, ou approximativement 20 millions de qubits physiques. Les auteurs vont plus loin et quantifient la durée d'exécution de leur configuration à seulement huit heures. Si l'on compare ce chiffre à l'estimation des superordinateurs les plus puissants du monde pour casser le cryptage RSA, ce qui dépasse largement la durée de vie d'un être humain, la puissance de l'algorithme de factorisation de Shor devient évidente. Pour d'autres estimations du nombre de qubits pour l'algorithme de Shor, consultez les références de cet article.

Là encore, la durée d'exécution de l'algorithme de Shor est inversement proportionnelle au nombre de qubits logiques disponibles. Il dépend également de la technologie des qubits utilisée, car les ordinateurs quantiques exécutent les opérations à des vitesses très différentes. Moins il y a de qubits, plus le temps d'exécution de l'algorithme est long, mais plus vite les cryptosystèmes modernes passent de l'obsolescence à la désuétude. Inversement, plus il y a de qubits disponibles, plus vite les cryptosystèmes modernes seront déchiffrés. Mais heureusement, cette époque est encore plus lointaine.

Comment exécuter l'algorithme de Shor ?

Vous ne pouvez pas. 

Le plus grand nombre factorisé à ce jour avec l'algorithme de Shor est 21. Et le plus petit nombre possible à factoriser avec l'algorithme est 15. Il s'agit d'une fourchette très étroite pour deux raisons spécifiques. Premièrement, l'algorithme de factorisation de Shor nécessite un grand nombre de qubits, comme indiqué précédemment, et un grand nombre de qubits n'existe pas. Deuxièmement, les qubits actuels sont "bruyants", ce qui signifie qu'ils sont remarquablement sujets aux erreurs. La profondeur de circuit requise par l'algorithme produit des résultats contenant tellement d'erreurs qu'il est impossible de distinguer les solutions correctes des solutions incorrectes.

En d'autres termes, RSA et d'autres systèmes cryptographiques potentiellement vulnérables sont en sécurité. Pour l'instant. Le NIST continue de travailler à la sélection d'une norme post-quantique, également connue sous le nom de norme "à sécurité quantique", dont on espère qu'elle sera largement mise en œuvre bien avant que suffisamment de qubits tolérants aux fautes soient disponibles pour concrétiser cette menace imminente.

Malgré la longueur du délai et le travail effectué pour atténuer le risque, l'algorithme de factorisation de Shor reste un bon moyen de sensibiliser à l'informatique quantique, aussi bien aujourd'hui qu'à l'époque où il a été découvert. Les dirigeants de tous les secteurs d'activité doivent se préoccuper des risques potentiels pour les communications et les données sensibles, et celui-ci est bien réel. Il est à espérer qu'ils découvriront ainsi les dizaines d'autres cas d'utilisation potentiels de l'informatique quantique dont leurs entreprises respectives pourraient un jour bénéficier de manière substantielle.

Visiter Bibliothèque de Classiq pour une implémentation de l'algorithme de Shor‍