Es kann einige Versuche dauern, bis der Algorithmus Erfolg hat. 10 Versuche um 15 zu faktorisieren ist normal. Zahlen kleiner als 15 haben teilweise sehr niedrige Erfolgsraten.
Schritt 0: Wahl eines geeigneten \(a\)
Zunächst wählen wir eine Zufallszahl \(a\) in \([2, \dots, N-1]\),
wobei \(\gcd(a,N) = 1\) gelten muss. Dieser Wert \(a\)
ist die Basis der Modulo-Funktion \(f(x) = a^x \bmod N\),
deren Periode wir gleich im Quanten-Teil bestimmen möchten.
1. Initialisierung
Wir verwenden insgesamt 2n Qubits: Das Top-Register (n Qubits)
und das Bottom-Register (n Qubits). Wir starten beispielsweise
im Zustand
\( |\psi_0\rangle = |0 \ldots 0\rangle_{\text{top}} \otimes |1\rangle_{\text{bottom}} \).
2. Hadamard-Transformation auf dem Top-Register
Auf jeden der n Top-Qubits wird das Hadamard-Gatter angewendet:
\( H |0\rangle = \tfrac{1}{\sqrt{2}} (|0\rangle + |1\rangle), \quad
H |1\rangle = \tfrac{1}{\sqrt{2}} (|0\rangle - |1\rangle) \).
So entsteht (vereinfacht) eine Superposition aller x-Werte
\( |0\rangle, |1\rangle, \dots, |2^n - 1\rangle \) im Top-Register.
3. Kontrollierte Multiplikation \(\bmod\ N\)
Anschließend wird in kontrollierten Schritten
die Operation
\( |x\rangle_{\text{top}} \,|y\rangle_{\text{bottom}}
\mapsto |x\rangle_{\text{top}} \,\bigl(y \cdot a^x \bmod N\bigr)_{\text{bottom}} \)
realisiert. So entsteht eine Verschränkung zwischen
x (im Top-Register) und dem modifizierten y (im Bottom-Register).
4. Quantum Fourier Transform (QFT) auf dem Top-Register
Nun wird die QFT auf den n Top-Qubits angewendet. Für
\( |x\rangle \) mit \( x \in \{0,\dots,2^n-1\} \) gilt
\[
\text{QFT} :\; |x\rangle \;\mapsto\; \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n - 1}
\exp\!\bigl(2\pi i \cdot kx / 2^n\bigr)\, |k\rangle.
\]
Dadurch kann die Periode der Funktion \( f(x) = a^x \bmod N \)
erkannt werden.
5. Messung des Top-Registers und Faktorfindung
Abschließend messen wir die n Qubits im Top-Register.
Mit etwas Glück entspricht der Messwert \(r\) (oder ein ganzzahliges Vielfaches)
der Periode. Dann prüfen wir über
\(\gcd(a^{r/2} - 1, N)\) und \(\gcd(a^{r/2} + 1, N)\),
ob sich nichttriviale Faktoren von \(N\) ergeben.
Erhalten wir nur \(\{1,N\}\), war der Messwert unpassend und wir
müssen den Algorithmus wiederholen (ggf. mit neuem \(a\)).
Diese Schritte bilden das Grundgerüst von Shors Algorithmus. In dieser vereinfachten Simulation werden sie in kleiner Dimension (und teils naiv implementiert) gezeigt, um das Prinzip des "quantum-unterstützten" Periodenfindens nachvollziehbar zu machen.