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

Technisches Resümee: Von der Periodensuche zur Gitterabtastung

Problemstellung
Obwohl Shors Algorithmus die ganzzahlige Faktorisierung theoretisch in Polynomialzeit löst, ist seine praktische Implementierung auf aktueller NISQ-Hardware (Noisy Intermediate-Scale Quantum) durch Schaltungstiefe, Gatterfehler und Dekohärenz stark begrenzt. Diese Einschränkungen haben das Interesse an alternativen Faktorisierungsalgorithmen geweckt, wie etwa Regevs Algorithmus, der das Problem eher als eine hochdimensionale Gitterabtastungsaufgabe denn als ein eindimensionales Periodenfindungsproblem formuliert. Bestehende experimentelle Analysen lassen jedoch oft systematische, Multi-Backend-Vergleiche unter streng kontrollierten Bedingungen vermissen, um zu verstehen, wie diese unterschiedlichen algorithmischen Strukturen mit realistischem Hardware-Rauschen interagieren. Diese Studie adressiert diese Lücke, indem sie Shors und Regevs Algorithmen auf realer Quantenhardware experimentell vergleicht, um deren relative Robustheit und Fehlermodi zu charakterisieren.

Methodik
Die Autoren führten eine kontrollierte experimentelle Studie unter Verwendung der Benchmark-Instanz $N = 15$ durch. Beide Algorithmen wurden unter Verwendung von Qiskit implementiert und auf zwei verschiedenen Quanten-Backends ausgeführt: dem QMIO-Quantencomputer am Centro de Supercomputación de Galicia (CESGA) und einem IBM Open-Access-Quantenprozessor (ibm_torino). Ideale (rauschfreie) Simulationen dienten als Referenzbasislinie.

• Algorithmus-Konfiguration:
  • Shors Algorithmus: Verwendete die Basis $a=2$ mit einem Kontrollregister von $k=3$ Qubits, um die Ordnung $r=4$ zu finden. Die Schaltung nutzte spezialisierte, flache modulare Exponentiationen basierend auf Permutationen anstelle generischer Arithmetik, um die Tiefe zu minimieren.
  • Regevs Algorithmus: Konfiguriert als zweidimensionale Instanz ($d=2$) mit den Basen $a_1=4, a_2=49$. Er verwendete eine Gaußsche Superposition über $\mathbb{Z}^d$, gefolgt von einer Fourier-Abtastung, um Vektoren im dualen Gitter zu approximieren.
• Kompilierung und Ausführung: Die Schaltungen wurden mittels Qiskit unter Berücksichtigung der nativen Gatter-Sets und der Konnektivität der jeweiligen Backends transpilliert. Alle Hardware-Läufe verwendeten 4.096 Shots.
• Evaluationsmetriken: Um die Auswirkungen des Rauschens zu quantifizieren, ohne für jeden Lauf eine vollständige klassische Rekonstruktion durchzuführen, führten die Autoren distributionsbasierte Metriken ein:
  • Shannon-Entropie ($H(p)$): Misst die Dispersion der Wahrscheinlichkeitsverteilung.
  • Effektive Support-Größe ($N_{eff}$): Schätzt die Anzahl der Ergebnisse, die signifikant zur Verteilung beitragen.
  • Top-K-Masse ($M_4$): Der Anteil der Gesamtwahrscheinlichkeit, der auf den vier häufigsten Ergebnissen liegt.

Wesentliche Beiträge

1. Kontrollierter experimenteller Benchmark: Die Arbeit liefert einen direkten, Low-Level-Vergleich von Shors und Regevs Algorithmus für dieselbe Probleminstanz ($N=15$) über mehrere Hardware-Plattformen und ideale Simulationen hinweg.
2. Multi-Backend-Evaluierung: Die Ergebnisse werden sowohl für IBM- als auch für QMIO-Geräte berichtet, was Einblicke darüber gibt, wie unterschiedliche Hardware-Architekturen die algorithmische Leistung beeinflussen.
3. Interpretation der Informationskodierung: Die Studie interpretiert die experimentellen Ergebnisse durch die Linse der „Informationskonzentration“ (Shor) versus „Informationsverteilung“ (Regev). Sie zeigt auf, wie diese strukturellen Unterschiede zu qualitativ unterschiedlichen, durch Rauschen induzierten Degradationen in den Messhistogrammen führen.
4. Reproduzierbarkeit: Die Autoren berichten die spezifischen algorithmischen Parameter und die Kompilierungspipelines, die zur Erzeugung der experimentellen Verteilungen verwendet wurden.

Ergebnisse
Die experimentellen Daten zeigen deutliche Fehlermodi für die beiden Algorithmen unter NISQ-Beschränkungen auf:

• Shors Algorithmus (Informationskonzentration):

  • In idealen Simulationen ist die Wahrscheinlichkeitsmasse stark auf eine geringe Anzahl spektraler Peaks konzentriert (niedrige Entropie, $N_{eff} \approx 4$, $M_4 = 1.0$).
  • Auf IBM-Hardware verbreitert sich die Verteilung, behält aber dominante Peaks bei ($M_4 = 0.921$), was eine teilweise erfolgreiche Ordnungswiederherstellung ermöglicht.
  • Auf dem verrauschteren QMIO-Gerät werden die spektralen Peaks signifikant abgeflacht und verdeckt ($M_4 = 0.564$, $N_{eff} \approx 7.8$), was zum Verlust der für die klassische Rekonstruktion erforderlichen periodischen Struktur führt.
  • Beobachtung: Shors Algorithmus reagiert hochsensibel auf Phasenfehler; sobald die scharfen Peaks durch Rauschen verbreitert werden, liefert der Algorithmus keine nützlichen Informationen mehr.

• Regevs Algorithmus (Informationsverteilung):

  • In idealen Simulationen ist die Verteilung inhärent disperser als die von Shor, weist aber dennoch eine Teilmenge dominanter Vektoren auf, die mit dem dualen Gitter konsistent sind ($N_{eff} \approx 2.34$, $M_4 = 0.944$).
  • Auf IBM-Hardware wird die Verteilung breiter ($M_4 = 0.645$), doch bleibt eine Teilmenge der Ergebnisse dominant genug, um potenziell eine Gitterreduktion zu unterstützen.
  • Auf QMIO wird das geometrische Signal stark verdünnt ($M_4 = 0.29$, $N_{eff} \approx 15.8$), wobei sich die Wahrscheinlichkeitsmasse gleichmäßig über viele Vektoren verteilt, was die Gitterstruktur effektiv verschleiert.
  • Beobachtung: Regevs Algorithmus beruht auf statistischer Verzerrung über mehrere korrelierte Stichproben. Obwohl er flachere Schaltungen verwendet (Tabelle 2 zeigt, dass die kompilierte Tiefe von Regev auf beiden Plattformen geringer ist als die von Shor), führt die mehrdimensionale Abtastphase zu einer Raussempfindlichkeit, die eine schnelle Dispersion des geometrischen Signals verursacht.

• Schaltungstiefe vs. Robustheit: Trotz der Tatsache, dass Regevs Algorithmus eine geringere kompilierte Schaltungstiefe aufweist (z. B. 147 gegenüber 210 auf IBM), führte diese Reduktion nicht zu einer überlegenen Robustheit auf aktueller Hardware. Die Messverteilungen von Regev dispersierten unter Rauschen schneller als die von Shor.

Bedeutung und Behauptungen
Die Arbeit stellt bescheiden fest, dass im kleinen $N$-Regime ($N=15$) auf aktuellen NISQ-Geräten keiner der Algorithmen einen praktischen Vorteil gegenüber dem anderen zeigt. Stattdessen hebt die Studie einen fundamentalen Trade-off hervor:

• Shors Algorithmus profitiert von hochstrukturierten, konzentrierten Ausgaben bei geringem Rauschen, versagt jedoch katastrophal, wenn die Phasenkohärenz verloren geht.
• Regevs Algorithmus verteilt Informationen über einen höherdimensionalen Raum, was bei größeren Problemen andere Skalierungseigenschaften bieten kann, aber derzeit unter einer erhöhten Raussempfindlichkeit während der mehrdimensionalen Abtastung leidet.

Die Autoren kommen zu dem Schluss, dass diese Ergebnisse die Bedeutung des experimentellen Benchmarkings unterstreichen, um die praktischen Auswirkungen von Designentscheidungen bei Algorithmen zu verstehen. Sie betonen, dass asymptotische Beziehungen im fehlertoleranten Setting keine Garantie für ein ähnliches Verhalten auf NISQ-Hardware bieten, wo die spezifische Kodierung der arithmetischen Information (Konzentration vs. Verteilung) bestimmt, wie sich Rauschen manifestiert und wie Algorithmen scheitern. Zukünftige Arbeiten sollen diese Benchmarks auf größeres $N$ ausweiten und Fehlerminderungsstrategien untersuchen, die auf diese spezifischen Trade-offs abzielen.