⚛️ quantum physics

Can PCE solve the factorisation problem via optimisation?

Cet article explore la faisabilité de l'adaptation de l'algorithme de codage de corrélation de Pauli (PCE) au problème de la factorisation d'entiers en tant que méthode pour réduire drastiquement les besoins en qubits, offrant une analyse préliminaire de son potentiel et de ses limites pour le matériel quantique à court terme sans revendiquer d'avantage computationnel.

Auteurs originaux : Fernando Alonso, Colomán Samprón, Jacobo Veiga, Andrés Gómez

Publié 2026-07-28

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Fernando Alonso, Colomán Samprón, Jacobo Veiga, Andrés Gómez

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayiez de percer un code secret qui protège votre compte bancaire, vos e-mails et presque tout ce que vous faites en ligne. Ce code repose sur un jeu mathématique simple mais complexe : prendre deux très grands nombres premiers (des nombres qui ne peuvent être divisés que par 1 et par eux-mêmes), les multiplier ensemble, et donner le résultat au monde entier. Il est facile de les multiplier, mais si vous n'avez que le géant nombre final, découvrir quels deux nombres premiers l'ont créé revient à essayer de défaire un gâteau pour retrouver le nombre exact d'œufs et de tasses de farine utilisés. Pour nos ordinateurs actuels, cela est presque impossible pour des nombres très grands. C'est le problème de la « factorisation d'entiers », et c'est le pilien de la sécurité numérique moderne.

Maintenant, imaginez un nouveau type d'ordinateur qui ne se contente pas de calculer ; il explore de nombreuses possibilités à la fois en utilisant les règles étranges de la physique quantique. Les scientifiques essaient d'apprendre à ces machines quantiques à résoudre ce problème de « défaire le gâteau », et une méthode célèbre, inventée par Peter Shor, est théoriquement parfaite mais nécessite un ordinateur quantique si puissant et si stable que nous n'avons pas encore la technologie pour le construire. Les chercheurs cherchent donc des raccourcis « inspirés du quantique » — des méthodes qui utilisent un peu de magie quantique mais qui peuvent fonctionner sur les machines bruyantes et imparfaites que nous possédons aujourd'hui. La grande question est la suivante : pouvons-nous faire tenir ce problème mathématique massif dans un puzzle minuscule et gérable que ces premiers ordinateurs quantiques puissent réellement résoudre ?

Ce document explore précisément cette question en utilisant un tour astucieux appelé Codage de Corrélation de Pauli (PCE). Considérez le PCE comme un algorithme de compression super efficace. Habituellement, pour représenter un problème complexe avec de nombreuses variables (comme les bits d'un grand nombre), vous avez besoin d'un grand nombre de bits quantiques (qubits). Le PCE agit comme une fermeture éclair magique, permettant aux chercheurs de compacter des milliers de variables dans un nombre beaucoup plus restreint de qubits. Les auteurs, Fernando Alonso et son équipe du Centre de Supercalcul de Galice, se sont demandé : « Si nous utilisons cette fermeture éclair pour compresser le problème de factorisation, pouvons-nous ensuite utiliser des techniques d'optimisation pour trouver la réponse ? »

Ils n'ont pas fait que deviner ; ils ont construit deux « cartes » différentes pour guider la recherche. La première carte, appelée approche de base, consistait à essayer de trouver les facteurs en devinant directement le code binaire des deux nombres premiers. Ils ont testé cela sur des nombres allant jusqu'à 25 bits de long. Les résultats étaient un peu mitigés : cela fonctionnait assez bien pour les petits nombres, mais à mesure que les nombres devenaient plus grands, le taux de réussite chutait et l'ordinateur restait souvent bloqué sur des solutions « triviales » (comme dire qu'un nombre est simplement lui-même multiplié par un).

La seconde carte, appelée DoTS (Différence de Deux Carrés), était une stratégie plus intelligente. Au lieu de chercher directement les facteurs, elle cherchait deux nombres dont les carrés diffèrent d'un multiple du nombre cible. C'est comme chercher deux personnes qui, lorsqu'elles se tiennent sur une balance, ont une différence de poids qui correspond parfaitement à un motif spécifique. Cette approche a été bien plus fructueuse. Dans leurs simulations, la méthode DoTS a réussi à factoriser des nombres allant jusqu'à 36 bits.

L'équipe a utilisé trois différents « moteurs de recherche » (optimiseurs) pour naviguer sur ces cartes : l'Évolution Différentielle (DE), l'Optimisation par Essaim de Particules (PSO) et une version inspirée du quantique, la QDPSO. Les résultats ont montré que l'optimiseur DE était le grand vainqueur, trouvant systématiquement les bonnes réponses là où les autres échouaient.

Cependant, les auteurs sont très prudents et ne prétendent pas avoir « cassé » le code. Ils soulignent que, bien que leur méthode utilise beaucoup moins de qubits que d'autres approches quantiques (ce qui la rend réalisable sur le matériel actuel), il s'agit toujours d'une simulation exécutée sur des ordinateurs classiques. Ils ont constaté que pour des nombres supérieurs à 36 bits, leur méthode actuelle commence à échouer, suggérant que la « fonction de coût » (le règlement qu'ils ont écrit pour l'ordinateur) pourrait devoir être réécrite pour capturer la mathématique de manière plus efficace. Ils ont également noté que s'ils l'exécutaient sur du matériel quantique réel, le bruit pourrait soit aider l'ordinateur à échapper aux impasses, soit ruiner entièrement le calcul.

En résumé, ce document suggère que le PCE est un outil prometteur qui pourrait rendre les problèmes de factorisation beaucoup plus petits et plus maniables pour les ordinateurs quantiques. Il ne résout pas encore le problème des nombres massifs utilisés dans le cryptage du monde réel, mais il ouvre une nouvelle porte. Il montre qu'avec la bonne compression et la bonne stratégie de recherche, nous pourrions amener les ordinateurs quantiques à effectuer de sérieux calculs numériques plus tôt que nous ne le pensions, même s'il reste encore un long chemin à parcourir avant de pouvoir défaire les plus gros gâteaux du monde.

Résumé Technique : Le PCE peut-il résoudre le problème de la factorisation via l'optimisation ?

Énoncé du Problème
La factorisation d'entiers, particulièrement des nombres semi-premiers ( $N = p \cdot q$ ), est un problème fondamental de la théorie numérique computationnelle et constitue la base de la sécurité de la cryptographie RSA. Bien que l'algorithme de Shor offre une solution quantique en temps polynomial, le matériel quantique actuel de type NISQ (Noisy Intermediate-Scale Quantum) manque du nombre de qubits et de la cohérence nécessaires pour une mise en œuvre pratique. Des approches alternatives, telles que les algorithmes quantiques variationnels (VQA) qui convertissent la factorisation en problèmes d'optimisation binaire, sont confrontées à des problèmes d'évolutivité, nécessitant généralement un nombre de qubits qui croît linéairement avec le nombre de variables binaires. Cette croissance linéaire les rend irréalisables pour des instances à grande échelle sur le matériel actuel. L'article examine si l'encodage par corrélation de Pauli (PCE - Pauli Correlation Encoding), un cadre capable d'encoder $m$ variables binaires à l'aide d'un nombre polynomial de qubits ( $n \ll m$ ), peut être adapté pour résoudre le problème de la factorisation via l'optimisation avec des ressources limitées.

Méthodologie
L'étude reformule le problème de la factorisation en tant que tâche d'optimisation binaire et applique le PCE pour réduire les besoins en qubits. La méthodologie comprend :

Stratégies d'encodage : Deux approches distinctes ont été développées pour mapper les contraintes de factorisation dans une fonction de coût :
- Approche de base (Basic Approach) : Encode directement les représentations binaires des facteurs inconnus $p$ et $q$ . La fonction de coût minimise la distance de Hamming au carré entre l'entier cible $N$ et le produit candidat $x_p \cdot x_q$ , avec des pénalités pour éviter les solutions triviales (ex: $N \cdot 1$ ).
- Approche de la différence de deux carrés (DoTS Approach) : Reformule le problème comme la recherche d'entiers $a$ et $b$ tels que $a^2 \equiv b^2 \pmod N$ (avec $a \not\equiv \pm b$ ). Les facteurs sont récupérés via $\gcd(a-b, N)$ et $\gcd(a+b, N)$ . La fonction de coût combine un terme imposant la congruence modulaire avec un terme vérifiant la factorisation résultante.
Circuit Quantique : Un ansatz de type « brickwork » (maçonnerie) efficace pour le matériel a été employé, consistant en des couches alternées de rotations monoquantiques ( $R_X, R_Y, R_Z$ ) et de portes d'intrication ( $R_{XX}, R_{YY}, R_{ZZ}$ ). L'ordre de compression PCE $k$ détermine la profondeur du circuit et le nombre de qubits requis ( $n \approx m/k$ ).
Optimisation : Les circuits quantiques paramétrés ont été simulés classiquement via Qiskit Aer. L'optimisation a été réalisée à l'aide de trois algorithmes sans gradient : l'évolution différentielle (DE), l'optimisation par essaim de particules (PSO) et l'optimisation par essaim de particules delta quantique (QDPSO). La fonction signe a été utilisée pour approximer les variables binaires, évitant la relaxation par tangente hyperbolique afin de prévenir les solutions réelles infinies.

Contributions Clés et Résultats

Réduction des Ressources : L'étude démontre que le PCE peut réduire drastiquement le nombre de qubits requis pour la factorisation. Pour les longueurs de clés RSA typiques, le nombre de qubits requis reste dans une plage « abordable » pour le matériel actuel ou à court terme, et pour des ordres de compression $k > 2$ , le problème peut être résolu entièrement sur des ordinateurs classiques via l'émulation de circuits quantiques.
Comparaison de Performance :
- DoTS vs Basic : L'approche DoTS a systématiquement surpassé l'approche Basic. La fonction de coût DoTS, qui capture la structure arithmétique de la relation de différence de deux carrés, a produit des taux de succès plus élevés et un paysage d'optimisation plus favorable.
- Sensibilité de l'Optimiseur : L'évolution différentielle (DE) s'est révélée être l'optimiseur le plus robuste, atteignant des factorisations réussies à travers diverses longueurs de bits. Les méthodes basées sur les essaims (PSO, QDPSO) ont présenté des taux de succès nettement inférieurs, suggérant que le paysage d'optimisation est difficile pour ces algorithmes spécifiques.
- Limites d'Évolutivité : La méthode a réussi à factoriser des semi-premiers allant jusqu'à 36 bits en utilisant l'approche DoTS avec $k=4$ et DE. Les taux de succès ont diminué pour des entiers supérieurs à 25–36 bits, indiquant des limitations intrinsèques dans les formulations actuelles des fonctions de coût pour des instances plus grandes.
Efficacité de Recherche : L'analyse du nombre d'évaluations de la fonction objectif montre que l'algorithme ne repose pas sur une exploration par force brute. Le nombre d'évaluations est resté plusieurs ordres de grandeur en dessous de la taille de l'espace de recherche combinatoire ( $2^n$ ), indiquant un processus de recherche guidé.

Signification et Revendications
L'article positionne ce travail comme une contribution préliminaire et exploratoire plutôt que comme une solution définitive ou une revendication d'avantage computationnel sur les algorithmes existants.

Faisabilité : La principale conclusion est que les algorithmes basés sur le PCE constituent un cadre plausible pour étudier la factorisation en tant que problème d'optimisation avec des ressources quantiques limitées. Il offre une perspective alternative aux méthodes établies comme le VQF et le QAOA en découplant le nombre de variables du nombre de qubits.
Limitations : Les auteurs déclarent explicitement que les formulations actuelles ne passent pas à l'échelle avec succès vers des tailles d'entiers cryptographiquement pertinentes (ex: RSA 2048 bits). Le succès de la méthode dépend fortement de la conception de la fonction de coût classique et du choix de l'optimiseur.
Directions Futures : L'étude suggère que les recherches futures devraient se concentrer sur :
- La conception de fonctions de coût plus informatives qui capturent mieux la structure arithmétique de la factorisation (en incorporant potentiellement des variables de retenue/carry).
- L'exploration des hypothèses de facteurs équilibrés (communes en RSA) pour réduire le nombre de variables.
- L'investigation de stratégies de démarrage à chaud (warm-start) et d'architectures d'ansatz alternatives.
- L'évaluation des performances sous des modèles de bruit réalistes.

En conclusion, bien que la méthode ne menace pas actuellement la sécurité de RSA, elle établit un cadre viable et efficace en ressources pour étudier la factorisation via l'optimisation inspirée du quantique, justifiant des recherches approfondies sur la conception des fonctions de coût et les raffinements algorithmiques.

Résumé Technique : Le PCE peut-il résoudre le problème de la factorisation via l'optimisation ?

Articles similaires