Factorisation quantique des nombres plus rapide que l’algorithme de Shor

L’algorithme quantique de Peter Shor permet de factoriser un nombre de n chiffres binaires en utilisant des qubits O(n) connectés par O(n).² log n) des portes logiques quantiques (opérations uniques), se terminant par des mesures quantiques O(1) (exécutions répétées) et un prosttraitement classique en temps polynomial. Oded Regev a publié l’année dernière un nouvel algorithme de factorisation qui nécessite O(n) sur arXiv.^3/2) portes logiques quantiques, bien qu’avec O(n^3/2) coudées, O(n^1/2) des mesures quantiques et un nouveau post-traitement classique en temps polynomial. Vinod Vaikuntanathan et Seyoon Ragavan ont publié quelques mois plus tard une amélioration de cet algorithme pour lequel O(n) suffit^3/2 log n) portes logiques quantiques, O(n log n) qubits, O(n^1/2) mesures quantiques et post-traitement Regev classique. Ce dernier algorithme est plus robuste car il réduit la constante de complexité qui multiplie le nombre O(n^1/2) des mesures, grâce au fait qu’il tolère mieux les erreurs des portes logiques. On pourrait penser que ces nouveaux algorithmes pourraient être utiles pour lutter contre la décohérence en réduisant le temps de calcul en réduisant le nombre de portes (opérations). Cependant, les nouveaux algorithmes n’y parviennent que pour n grand ; En fait, les constantes de complexité desdits algorithmes n’ont pas été calculées, donc pour de petits n, l’algorithme de Shor pourrait continuer à être plus efficace. Néanmoins, la prise en compte de nombres intéressants dans la cryptographie actuelle, tels que le RSA-2048 à 2 048 bits, dépasse ce qui est concevable dans les décennies à venir, à la fois avec l’algorithme de Shor et avec les deux nouveaux algorithmes.

Ces deux nouveaux algorithmes constituent la première avancée majeure dans la factorisation des nombres quantiques au cours des 30 dernières années (plusieurs articles optimisant les deux algorithmes ont déjà été publiés). Il faut se rappeler que le principal facteur qui limite la puissance des ordinateurs quantiques actuels est le volume quantique, une mesure du nombre maximum de portes logiques que peut avoir le circuit quantique qui représente un algorithme qui fonctionne correctement sur l’ordinateur. Le volume quantique d’un ordinateur dépend des taux d’erreur de ses qubits et de celui de ses portes logiques (les opérations pouvant être exécutées sur lesdits qubits). Avec la technologie actuelle (nous sommes dans l’ère NISQ, par exemple L’ère du quantique à échelle intermédiaire bruyante), le volume quantique est très petit ; Le record actuel (avril 2024) est détenu par l’ordinateur H1-1 de 20 qubits de la société Quantinuum, dont le volume quantique atteint un méga (2²⁰), grâce à l’utilisation de portes logiques binaires avec une fidélité de 99,914(3)% (la première fois que trois neuf sont atteints). Je ne sais pas si l’algorithme de Shor a été exécuté sur ledit ordinateur, mais il ne pourra prendre en compte qu’un très petit nombre.

Il convient peut-être de noter que le plus grand nombre qui a été factorisé avec l’algorithme de Shor sur un ordinateur quantique a été 21 = 7 × 3 en 2012. En 2019, une tentative a été faite pour factoriser le nombre 35 = 7 × 5 avec ledit algorithme sur un ordinateur quantique. Ordinateur quantique IBM Q System One (20 qubits), mais c’était impossible car il n’avait pas suffisamment de volume quantique ; Le prix de consolation était de factoriser le nombre 35 à l’aide d’un algorithme hybride basé sur celui de Shor. Grâce à un algorithme hybride, il a été possible en 2022 de factoriser un nombre de 48 bits en utilisant 10 qubits (LCMF, 27 décembre 2022). L’algorithme de Regev permettra-t-il de factoriser des nombres supérieurs à 21 sur les ordinateurs quantiques IBM ou Quantinuum ? Regev lui-même dit qu’il ne sait pas. Je suis optimiste et je le pense, donc j’espère que cette étape sera publiée à la fin de cette année. Malheureusement, je ne m’attends pas à ce que des nombres bien supérieurs à 35 puissent être factorisés. Un nombre comme RSA-2048 est toujours un nombre « infini » pour les ordinateurs NISQ actuels.

Les nouveaux algorithmes ont été publiés dans Oded Regev, « An Efficient Quantum Factoring Algorithm », arXiv :2308.06572. [quant-ph] (12 août 2023), est ce que je: https://doi.org/10.48550/arXiv.2308.06572; Seyoon Ragavan, Vinod Vaikuntanathan, « Factorisation quantique peu encombrante et résistante au bruit », arXiv:2310.00899 [quant-ph] (02 octobre 2023), doi: https://doi.org/10.48550/arXiv.2310.00899. Informations plus informatives dans Ben Brubaker, “Trente ans plus tard, un accélérateur de vitesse pour l’affacturage quantique”, Quanta Magazine, 17 octobre 2023. Citez également Craig Gidney, Martin Ekerå, « Comment factoriser des entiers RSA de 2048 bits en 8 heures en utilisant 20 millions de qubits bruyants », Quantum 5 : 433 (2021), doi : https://doi.org/10.22331/q-2021-04-15-433, arXiv:1905.09749 [quant-ph] (23 mai 2019) ; Cédric Pilatte, « Correction inconditionnelle des algorithmes quantiques récents pour la factorisation et le calcul des logarithmes discrets », arXiv:2404.16450 [math.NT] (25 avril 2024), deux : https://doi.org/10.48550/arXiv.2404.16450; Martin Ekerå, Joel Gärtner, « Extension de l’algorithme de factorisation de Regev pour calculer des logarithmes discrets », PQCrypto 2024, Lecture Notes in Computer Science 14772 : 211-242 (2024), doi : https://doi.org/10.1007/978-3-031-62746-0_10, arXiv:2311.05545 [cs.CR] (09 novembre 2023) ; ; .

Essentiellement, l’algorithme de Shor pour factoriser le nombre N partie d’un nombre un N qui est co-cousin de N et cherche la période l > 0 tel que un^l = 1 module N en utilisant la transformée de Fourier quantique discrète (QFT) ; une fois le délai obtenu l Un post-traitement classique est utilisé en temps polynomial qui permet de déterminer un facteur premier de N. La clé de l’algorithme est le calcul des produits modulo N (calculer un^l mod N) en utilisant des transformations unitaires. Dans un sens, l’algorithme de Shor est unidimensionnel (comme cette figure tente de l’illustrer). Magazine Quanta). L’idée de Regev est d’utiliser une version multidimensionnelle dudit algorithme (comme tente d’illustrer la figure qui ouvre cet article, que je vous recommande de revoir). Au lieu de prendre un numéro un sont pris d > 0 numéros b₁…, b_d et est défini un_je = b_je²; dans des grilles séparées d dimension 𝓛 = {j | ∏ un_je^j_je = 1 module N} y 𝓛₀ = {j | ∏ b_je^j_je ∈ {−1,1} mod N} les multipériodes sont recherchées j = (j₁…, j_d) en utilisant QFT. Enfin, un post-traitement classique est appliqué en temps polynomial, basé sur un j^∗ ∈ 𝓛−𝓛₀ on obtient un facteur premier de N. À propos, Shor a également présenté un algorithme pour calculer le logarithme discret ; En 2024, Martin Ekerå et Joel Gärtner ont étendu l’algorithme de Regev pour calculer le logarithme discret.

Regev n’a pas réussi à prouver mathématiquement que son algorithme fonctionne en temps polynomial. Le post-traitement classique final, la détermination en temps polynomial d’un j^∗ ∈ 𝓛−𝓛₀, n’est assuré par aucun théorème mathématique. Au lieu de cela, Regev l’a proposé comme une conjecture ; donc votre algorithme fonctionne modulo ladite hypothèse. Cédric Pilatte a montré en 2024 que cette hypothèse peut être éliminée, même s’il faut augmenter le nombre de qubits et de portes logiques quantiques avec des facteurs polylogarithmiques.

Je n’ai pas l’intention d’entrer dans le détail de ces algorithmes quantiques (qui, bien que peu compliqués, nécessitent la connaissance de l’algorithme de Shor) ; Mon intention se limite à donner une idée de ce qui a été réalisé. En fait, Vaikuntanathan et Ragavan modifient la méthode de multiplication de réseau utilisée par Regev, basée sur l’utilisation de puissances de deux, en utilisant une technique de multiplication répétée basée sur des puissances avec des nombres de Fibonacci. Un gros problème avec l’algorithme de Shor est qu’il échoue en présence de bruit (non corrigé), comme Jin-Yi Cai l’a démontré en 2023. Le nouvel algorithme de Vaikuntanathan et Ragavan utilise une amélioration dans la prise de mesures quantiques qui permet une certaine tolérance aux erreurs dans le calcul quantique de QFT. Mais au final il faut appliquer le même post-traitement Regev (nécessitant la même hypothèse). Quoi qu’il en soit, l’amélioration de la tolérance aux erreurs est faible et les algorithmes de correction d’erreurs sont essentiels dans les deux nouveaux algorithmes, tout comme dans l’algorithme de Shor. Par exemple, Craig Gidney et Martin Ekerå ont estimé en 2021 qu’avec l’algorithme de Shor, la factorisation du nombre RSA-2048 nécessite environ 20 millions de qubits physiques qui simulent les qubits logiques nécessaires.

En résumé, des progrès ont été réalisés sur une question qui stagne depuis trois décennies. La nouvelle impulsion activera ce champ. Nous espérons tous que de nouvelles optimisations algorithmiques apparaîtront qui nous permettront de factoriser des nombres supérieurs à 21 dans les ordinateurs quantiques NISQ actuels. Mais ne vous y trompez pas, la prise en compte de l’intérêt pour la cryptographie et la sécurité informatique ne sera possible que dans la seconde moitié de ce siècle.