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

Technische Samenvatting: Van Periodevinden naar Roosterbemonstering

Probleemstelling
Hoewel het algoritme van Shor theoretisch integer factorisatie in polynomiale tijd oplost, wordt de praktische implementatie op huidige Noisy Intermediate-Scale Quantum (NISQ) hardware ernstig beperkt door de diepte van de circuits, gate-fouten en decoherentie. Deze beperkingen hebben geleid tot interesse in alternatieve factorisatiealgoritmen, zoals het algoritme van Regev, dat het probleem herformuleert als een hoogdimensionale roosterbemonsteringsopgave in plaats van een eendimensionaal periodevindingsprobleem. De huidige experimentele analyses missen echter vaak systematische, multi-backend vergelijkingen onder strikt gecontroleerde omstandigheden om te begrijpen hoe deze afzonderlijke algoritmische structuren interageren met realistische hardware-ruis. Deze studie adresseert dit gat door het algoritme van Shor en het algoritme van Regev experimenteel te vergelijken op echte quantumhardware om hun relatieve robuustheid en faalmodi te karakteriseren.

Methodologie
De auteurs voerden een gecontroleerde experimentele studie uit met de benchmark-instantie $N = 15$. Beide algoritmen werden geïmplementeerd met Qiskit en uitgevoerd op twee verschillende quantum-backends: de QMIO quantumcomputer bij het Centro de Supercomputación de Galicia (CESGA) en een IBM open-access quantumprocessor (ibm_torino). Ideale (ruisvrije) simulaties dienden als referentie-baseline.

• Algoritmeconfiguratie:
  • Algoritme van Shor: Gebruikte basis $a=2$ met een controle-register van $k=3$ qubits om de orde $r=4$ te vinden. Het circuit maakte gebruik van gespecialiseerde, ondiepe modulaire exponentiatie-constructies gebaseerd op permutaties in plaats van generieke aritmetica om de diepte te minimaliseren.
  • Algoritme van Regev: Geconfigureerd als een tweedimensionale instantie ($d=2$) met bases $a_1=4, a_2=49$. Het maakte gebruik van een Gaussische superpositie over $\mathbb{Z}^d$ gevolgd door Fourier-bemonstering om vectoren in het duale rooster te benaderen.
• Compilatie en Executie: Circuits werden getranspileerd met Qiskit, waarbij parameters werden aangepast aan de native gate-sets en connectiviteit van elke backend. Alle hardware-runs maakten gebruik van 4.096 shots.
• Evaluatiemetrieken: Om de impact van ruis te kwantificeren zonder voor elke run een volledige klassieke reconstructie te vereisen, introduceerden de auteurs distributiegebaseerde metrieken:
  • Shannon Entropie ($H(p)$): Meet de dispersie van de waarschijnlijkheidsverdeling.
  • Effectieve Ondersteuningsgrootte ($N_{eff}$): Schat het aantal uitkomsten dat significant bijdraagt aan de distributie.
  • Top-K Massa ($M_4$): Het fractie van de totale waarschijnlijkheid die wordt bevat door de vier meest frequente uitkomsten.

Belangrijkste Bijdragen

1. Gecontroleerde Experimentele Benchmark: Het artikel biedt een directe, laag-niveau vergelijking van het algoritme van Shor en het algoritme van Regev op dezelfde probleeminstantie ($N=15$) over meerdere hardwareplatforms en ideale simulaties.
2. Multi-Backend Evaluatie: Resultaten worden gerapporteerd voor zowel IBM- als QMIO-apparaten, wat inzichten biedt in hoe verschillende hardware-architecturen de algoritmische prestaties beïnvloeden.
3. Interpretatie van Informatie-encodering: De studie interpreteert experimentele resultaten door de lens van "informatieconcentratie" (Shor) versus "informatieverdeling" (Regev). Het demonstreert hoe deze structurele verschillen leiden tot kwalitatief verschillende door ruis veroorzaakte degradaties in meet-histogrammen.
4. Reproduceerbaarheid: De auteurs rapporteren specifieke algoritmische parameters en compilatie-pipelines die zijn gebruikt om de experimentele distributies te genereren.

Resultaten
De experimentele gegevens onthullen verschillende faalmodi voor de twee algoritmen onder NISQ-beperkingen:

• Algoritme van Shor (Informatieconcentratie):

  • In ideale simulaties is de waarschijnlijkheidsmassa sterk geconcentreerd op een klein aantal spectrale pieken (lage entropie, $N_{eff} \approx 4$, $M_4 = 1.0$).
  • Op IBM-hardware wordt de distributie breder maar behoudt zij dominante pieken ($M_4 = 0.921$), wat gedeeltelijk succes in orde-herstel mogelijk maakt.
  • Op het luidruchtigere QMIO-apparaat zijn de spectrale pieken aanzienlijk afgeplat en vertroebeld ($M_4 = 0.564$, $N_{eff} \approx 7.8$), wat leidt tot een verlies van de periodieke structuur die nodig is voor klassieke reconstructie.
  • Observatie: Het algoritme van Shor is zeer gevoelig voor fasefouten; zodra de scherpe pieken door ruis worden verbreed, faalt het algoritme om nuttige informatie te leveren.

• Algoritme van Regev (Informatieverdeling):

  • In ideale simulaties is de distributie inherent meer verspreid dan die van Shor, maar vertoont het nog steeds een subset van dominante vectoren die consistent zijn met het duale rooster ($N_{eff} \approx 2.34$, $M_4 = 0.944$).
  • Op IBM-hardware wordt de distributie meer verspreid ($M_4 = 0.645$), maar een subset van uitkomsten blijft dominant genoeg om potentieel roosterreductie te ondersteunen.
  • Op QMIO wordt het geometrische signaal sterk verdund ($M_4 = 0.29$, $N_{eff} \approx 15.8$), waarbij de waarschijnlijkheidsmassa uniform over vele vectoren wordt verspreid, waardoor de roosterstructuur effectief wordt vertroebeld.
  • Observatie: Het algoritme van Regev vertrouwt op statistische bias over meerdere gecorreleerde monsters. Hoewel het ondiepere gecompileerde circuits gebruikt (Tabel 2 laat zien dat de gecompileerde diepte van Regev lager is dan die van Shor op beide platforms), introduceert de multidimensionale bemonsteringsfase een ruisgevoeligheid die zorgt voor een snelle dispersie van het geometrische signaal.

• Circuitdiepte vs. Robuustheid: Ondanks het feit dat het algoritme van Regev een ondiepere gecompileerde circuitdiepte heeft (bijv. 147 vs. 210 op IBM), vertaalde deze reductie zich niet in superieure robuustheid op de huidige hardware. De meetdistributies van Regev verspreidden zich sneller onder ruis vergeleken met Shor.

Betekenis en Claims
Het artikel claimt bescheiden dat geen van beide algoritmen een praktisch voordeel vertoont ten opzichte van de ander in het kleine $N$-regime ($N=15$) op huidige NISQ-apparaten. In plaats daarvan benadrukt de studie een fundamentele afweging:

• Het algoritme van Shor profiteert van zeer gestructureerde, geconcentreerde outputs wanneer de ruis laag is, maar faalt catastrofaal wanneer de fasecoherentie verloren gaat.
• Het algoritme van Regev verdeelt informatie over een hogere-dimensie ruimte, wat grotere problemen mogelijk andere schalingseigenschappen biedt, maar momenteel lijdt onder een verhoogde gevoeligheid voor ruis in multidimensionale bemonstering.

De auteurs concluderen dat deze resultaten de waarde onderstrepen van experimentele benchmarking om de praktische implicaties van algoritmische ontwerpkeuzes te begrijpen. Ze benadrukken dat asymptotische relaties in de fouttolerante setting geen vergelijkbaar gedrag garanderen op NISQ-hardware, waar de specifieke encodering van aritmetische informatie (concentratie versus distributie) bepaalt hoe ruis zich manifesteert en hoe algoritmen falen. Toekomstig werk wordt voorgesteld om deze benchmarks uit te breiden naar grotere $N$ en om foutmitigatiestrategieën te verkennen die gericht zijn op deze specifieke afwegingen.