From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms

Cet article présente une comparaison expérimentale des algorithmes de factorisation quantique de Shor et de Regev sur du matériel NISQ réel pour N=15, analysant comment leurs approches structurelles distinctes de l'encodage arithmétique interagissent avec le bruit des dispositifs et les limitations d'échantillonnage pour éclairer l'étalonnage pratique de stratégies de factorisation alternatives.

L'essentiel

La vue d'ensemble : Deux façons différentes de casser un code

Imaginez que vous essayiez de casser un code secret (factoriser un nombre) en utilisant un nouveau type de super-ordinateur appelé ordinateur quantique. Depuis longtemps, tout le monde utilise une méthode spécifique pour faire cela, inventée par un mathématicien nommé Shor. C'est comme la recette « étalon » pour casser le code.

Cependant, les ordinateurs quantiques actuels sont comme des cuisines « bruyantes ». Ils sont petits, ils font des erreurs et ils se confondent facilement. Pour cette raison, les scientifiques cherchent des recettes alternatives qui pourraient mieux fonctionner dans ces conditions désordonnées. L'une de ces nouvelles recettes a été inventée par un mathématicien nommé Regev.

Cet article est une expérience où les auteurs ont préparé les deux recettes (celle de Shor et celle de Regev) sur de vrais ordinateurs quantiques bruyants pour voir laquelle gère le mieux le « bruit ». Ils n'ont pas essayé de casser un code massif et réel (ce qui prendrait des années) ; ils ont plutôt cassé un petit nombre facile (15) juste pour voir comment les deux méthodes se comportaient.

Les deux recettes : Une « lampe de poche » contre une « carte brumeuse »

Pour comprendre la différence, imaginez que vous essayez de trouver un trésor caché dans une pièce sombre.

1. L'algorithme de Shor : La lampe de poche

• Comment il fonctionne : La méthode de Shor essaie de projeter une lampe de poche très brillante et précise sur le trésor. Elle concentre toute son énergie sur un ou deux points spécifiques (pics). Si la lumière est assez brillante, vous voyez immédiatement le trésor.
• Le problème : Dans une cuisine bruyante, la lampe de poche vacille. Si la lumière devient trop faible ou instable, vous ne pouvez plus dire où se trouve le trésor. Le « pic aigu » devient flou, et le signal est perdu.
• La conclusion de l'article : Sur l'ordinateur IBM (qui était légèrement moins bruyant), la lampe de poche fonctionnait encore assez bien. Mais sur l'ordinateur QMIO (qui était plus bruyant), la lumière est devenue si floue qu'ils n'ont plus pu trouver le trésor.

2. L'algorithme de Regev : La carte brumeuse

• Comment il fonctionne : La méthode de Regev n'utilise pas une seule lampe de poche. À la place, elle trace un ensemble de lignes pointillées sur une carte. Aucun point unique n'indique directement le trésor, mais si vous regardez le motif de tous les points ensemble, ils forment une forme qui révèle l'emplacement. Elle répartit l'information sur de nombreux points.
• Le problème : Dans une cuisine bruyante, le brouillard s'épaissit. Les points sur la carte se dispersent et se mélangent. Comme l'information est répartie, il est plus difficile de voir le motif lorsque le bruit interfère.
• La conclusion de l'article : La méthode de Regev a créé une distribution de points plus « plate ». Sur l'ordinateur QMIO, très bruyant, les points se sont tellement dispersés que le motif a complètement disparu.

L'expérience : Que s'est-il passé ?

Les chercheurs ont testé les deux « recettes » sur deux ordinateurs quantiques différents (IBM et QMIO) et les ont comparées à une simulation parfaite sans bruit.

• Le monde « Idéal » : Dans une simulation parfaite, la méthode de Shor montrait quelques pics très hauts et acérés (la lampe de poche). La méthode de Regev montrait quelques points légèrement plus hauts dispersés selon un motif (la carte). Les deux fonctionnaient parfaitement.
• Le monde « Réel » (IBM) :
  • Shor : Les pics sont devenus un peu plus larges et plus courts, mais on pouvait encore les voir. La « lampe de poche » était instable mais visible.
  • Regev : Les points sont devenus plus dispersés, mais quelques-uns étaient encore légèrement plus hauts que les autres. La « carte » était brumeuse, mais le motif était encore faiblement présent.
• Le monde « Réel » (QMIO - La machine la plus bruyante) :
  • Shor : Les pics se sont totalement aplatis. La lampe de poche s'est éteinte. L'ordinateur ne pouvait plus faire la différence entre le signal et le bruit.
  • Regev : Les points sont devenus un nuage uniforme. Le motif a totalement disparu. La « carte » était si brumeuse qu'elle ressemblait à de la neige statique aléatoire.

La conclusion clé

L'article conclut qu'aucune des deux méthodes n'est clairement « meilleure » pour l'instant pour ces petites machines bruyantes.

• La méthode de Shor est comme un outil de haute précision : elle fonctionne très bien si l'environnement est propre, mais elle se brise facilement s'il y a ne serait-ce qu'un peu de saleté (bruit).
• La méthode de Regev est comme un réseau distribué : elle utilise des circuits moins profonds (des étapes moins complexes), ce qui semble être un avantage, mais parce qu'elle répartit son information, le bruit brouille le motif aussi efficacement qu'il brouille la lampe de poche.

L'essentiel à retenir :
Les auteurs ont découvert que la manière dont ces algorithmes stockent l'information est fondamentalement différente. Shor « concentre » l'information (comme un laser), tandis que Regev la « distribue » (comme un spray). Sur les ordinateurs bruyants d'aujourd'hui, les deux stratégies sont en difficulté, mais elles échouent de manières différentes. Shor perd sa focalisation précise, tandis que Regev perd son motif géométrique.

Cette étude ne dit pas que nous pouvons casser les codes bancaires réels dès maintenant. Au contraire, elle nous indique qu'à mesure que nous construisons de meilleurs ordinateurs quantiques, nous devons comprendre comment ces différents algorithmes réagissent au bruit, afin de pouvoir choisir le bon pour la bonne machine.

Résumé technique

Résumé Technique : De la recherche de période à l'échantillonnage de réseaux

Énoncé du problème
Bien que l'algorithme de Shor résolve théoriquement la factorisation d'entiers en temps polynomial, sa mise en œuvre pratique sur le matériel actuel de type NISQ (Noisy Intermediate-Scale Quantum) est sévèrement contrainte par la profondeur des circuits, les erreurs de porte et la décohérence. Ces limitations ont suscité l'intérêt pour des algorithmes de factorisation alternatifs, tels que l'algorithme de Regev, qui reformule le problème comme une tâche d'échantillonnage de réseaux multidimensionnels plutôt que comme un problème de recherche de période unidimensionnel. Cependant, les analyses expérimentales existantes manquent souvent de comparaisons systématiques multi-backends sous des conditions étroitement contrôlées pour comprendre comment ces structures algorithmiques distinctes interagissent avec le bruit matériel réaliste. Cette étude comble cette lacune en comparant expérimentalement les algorithmes de Shor et de Regev sur du matériel quantique réel afin de caractériser leur robustesse relative et leurs modes de défaillance.

Méthodologie
Les auteurs ont mené une étude expérimentale contrôlée utilisant l'instance de référence $N = 15$. Les deux algorithmes ont été implémentés via Qiskit et exécutés sur deux backends quantiques distincts : l'ordinateur quantique QMIO au Centro de Supercomputación de Galicia (CESSA) et un processeur quantique ouvert d'IBM (ibm_torino). Des simulations idéales (sans bruit) ont servi de référence de base.

• Configuration des algorithmes :
  • Algorithme de Shor : Utilisation de la base $a=2$ avec un registre de contrôle de $k=3$ qubits pour trouver l'ordre $r=4$. Le circuit utilise des constructions d'exponentiation modulaire spécialisées et peu profondes basées sur des permutations plutôt que sur l'arithmétique générique afin de minimiser la profondeur.
  • Algorithme de Regev : Configuré comme une instance bidimensionnelle ($d=2$) avec les bases $a_1=4, a_2=49$. Il emploie une superposition gaussienne sur $\mathbb{Z}^d$ suivie d'un échantillonnage de Fourier pour approximer les vecteurs du réseau dual.
• Compilation et exécution : Les circuits ont été transpilés avec Qiskit, avec des paramètres ajustés pour les ensembles de portes natifs et la connectivité de chaque backend. Tous les passages sur le matériel ont utilisé 4 096 tirages (shots).
• Métriques d'évaluation : Pour quantifier l'impact du bruit sans dépendre d'une reconstruction classique complète pour chaque passage, les auteurs ont introduit des métriques basées sur la distribution :
  • Entropie de Shannon ($H(p)$) : Mesure la dispersion de la distribution de probabilité.
  • Taille de support effectif ($N_{eff}$) : Estime le nombre de résultats contribuant de manière significative à la distribution.
  • Masse Top-K ($M_4$) : La fraction de la probabilité totale contenue dans les quatre résultats les plus fréquents.

Contributions clés

1. Benchmark expérimental contrôlé : L'article fournit une comparaison directe et de bas niveau des algorithmes de Shor et de Regev sur la même instance de problème ($N=15$) à travers plusieurs plateformes matérielles et simulations idéales.
2. Évaluation multi-backends : Les résultats sont rapportés pour les dispositifs IBM et QMIO, offrant un aperçu de la manière dont les différentes architectures matérielles affectent les performances algorithmiques.
3. Interprétation du codage de l'information : L'étude interprète les résultats expérimentaux à travers le prisme de la « concentration de l'information » (Shor) versus la « distribution de l'information » (Regev). Elle démontre comment ces différences structurelles conduisent à des dégradations induites par le bruit qualitativement distinctes dans les histogrammes de mesure.
4. Reproductibilité : Les auteurs rapportent les paramètres algorithmiques spécifiques et les pipelines de compilation utilisés pour générer les distributions expérimentales.

Résultats
Les données expérimentales révèlent des modes de défaillance distincts pour les deux algorithmes sous les contraintes NISQ :

• Algorithme de Shor (Concentration de l'information) :

  • Dans les simulations idéales, la masse de probabilité est fortement concentrée sur un petit nombre de pics spectraux (faible entropie, $N_{eff} \approx 4$, $M_4 = 1,0$).
  • Sur le matériel IBM, la distribution s'élargit mais conserve des pics dominants ($M_4 = 0,921$), permettant une récupération partielle de l'ordre.
  • Sur le dispositif plus bruyant QMIO, les pics spectraux sont significativement aplatis et obscurcis ($M_4 = 0,564$, $N_{eff} \approx 7,8$), entraînant une perte de la structure périodique nécessaire à la reconstruction classique.
  • Observation : L'algorithme de Shor est très sensible aux erreurs de phase ; une fois que les pics nets sont élargis par le bruit, l'algorithme ne fournit plus d'informations utiles.

• Algorithme de Regev (Distribution de l'information) :

  • Dans les simulations idéales, la distribution est intrinsèquement plus dispersée que celle de Shor, mais présente tout de même un sous-ensemble de vecteurs dominants cohérents avec le réseau dual ($N_{eff} \approx 2,34$, $M_4 = 0,944$).
  • Sur le matériel IBM, la distribution devient plus étalée ($M_4 = 0,645$), mais un sous-ensemble de résultats reste suffisamment dominant pour potentiellement supporter la réduction de réseau.
  • Sur QMIO, le signal géométrique est fortement dilué ($M_4 = 0,29$, $N_{eff} \approx 15,8$), la masse de probabilité se répartissant uniformément sur de nombreux vecteurs, ce qui occulte efficacement la structure du réseau.
  • Observation : L'algorithme de Regev repose sur un biais statistique à travers de multiples échantillons corrélés. Bien qu'il utilise des circuits plus peu profonds (le Tableau 2 montre que la profondeur compilée de Regev est inférieure à celle de Shor sur les deux plateformes), l'étape d'échantillonnage multidimensionnel introduit une sensibilité au bruit qui provoque une dispersion rapide du signal géométrique.

• Profondeur de circuit vs Robustesse : Malgré le fait que l'algorithme de Regev possède une profondeur de circuit compilé plus faible (ex: 147 contre 210 sur IBM), cette réduction ne s'est pas traduite par une robustesse supérieure sur le matériel actuel. Les distributions de mesure de Regev se sont dispersées plus rapidement sous l'effet du bruit par rapport à celles de Shor.

Signification et affirmations
L'article affirme modestement qu'aucun des deux algorithmes ne démontre d'avantage pratique sur l'autre dans le régime de petit $N$ ($N=15$) sur les dispositifs NISQ actuels. Au lieu de cela, l'étude met en évidence un compromis fondamental :

• L'algorithme de Shor bénéficie de sorties hautement structurées et concentrées lorsque le bruit est faible, mais échoue de manière catastrophique lorsque la cohérence de phase est perdue.
• L'algorithme de Regev distribue l'information dans un espace de dimension supérieure, ce qui peut offrir des propriétés de mise à l'échelle différentes pour des problèmes plus larges, mais souffre actuellement d'une sensibilité accrue au bruit lors de l'échantillonnage multidimensionnel.

Les auteurs concluent que ces résultats soulignent la valeur de l'évaluation expérimentale pour comprendre les implications pratiques des choix de conception algorithmique. Ils insistent sur le fait que les relations asymptotiques dans le cadre tolérant aux fautes ne garantissent pas un comportement similaire sur le matériel NISQ, où le codage spécifique de l'information arithmétique (concentration vs distribution) dicte la manière dont le bruit se manifeste et comment les algorithmes échouent. Des travaux futurs sont proposés pour étendre ces benchmarks à des valeurs de $N$ plus grandes et explorer des stratégies d'atténuation d'erreurs ciblant ces compromis spécifiques.