Grover's Search

Man nutzt ihn, um AES anzugreifen. AES-128 hat $2^{128}$ Schlüssel. Mit Grover braucht man nur $\sqrt{2^{128}} = 2^{64}$ Operationen. Das ist machbar. Deshalb sagt man: "Nutzt AES-256!" Dann braucht Grover $2^{128}$, was sicher genug ist.

1. Amplitude Amplification

Der Trick:

1. Starte in Superposition (alles gleich wahrscheinlich).
2. Orakel-Phase: Markiere den gesuchten Eintrag (drehe Phase um).
3. Diffusions-Phase (Grover Operator): Invertiere alle Amplituden "am Mittelwert". Dadurch wächst die Amplitude des gesuchten Eintrags, die anderen schrumpfen. Nach ca. $\frac{\pi}{4}\sqrt{N}$ Wiederholungen ist die Wahrscheinlichkeit bei fast 100%.

2. Overshooting

Wenn man den Grover-Operator zu oft anwendet, schrumpft die Wahrscheinlichkeit wieder ("wie eine Uhr, die über 12 hinausdreht"). Man muss genau wissen, wann man aufhört (Messung).

1. Der Grover-Operator als Matrix

Mathematisch gesehen ist der Grover-Algorithmus eine Rotation in einem 2D-Vektorraum. Der Zustandsvektor $|\psi\rangle$ des Quantencomputers setzt sich zusammen aus dem "guten" Zustand $|w\rangle$ (das Ziel) und dem "schlechten" Rest $|s\rangle$. Der Grover-Operator $G$ wendet zwei Spiegelungen (Reflections) an. Jede Anwendung von $G$ rotiert den Vektor um einen festen Winkel $\theta$ in Richtung $|w\rangle$. Nach genau $k$ Schritten liegt der Vektor maximal nah an $|w\rangle$. Misst man zu diesem Zeitpunkt, bricht die Wellenfunktion mit fast 100%iger Wahrscheinlichkeit in $|w\rangle$ zusammen. Das ist kein "Raten", sondern präzise destruktive Interferenz der falschen Pfade.

2. Die $\Omega(\sqrt{N})$-Grenze (Optimality)

Warum geht es nicht schneller? In der Quanten-Komplexitätstheorie wurde bewiesen (Bennett et al.), dass für eine "Black-Box"-Suche (bei der wir nichts über die Struktur des Orakels wissen) $\sqrt{N}$ die absolute physikalische Untergrenze ist. Jedes Orakel-Query fügt dem Quantenzustand nur eine begrenzte Menge an Information hinzu. Man kann zeigen, dass der "Abstand" zum Zielzustand nach $T$ Abfragen proportional zu $T^2/N$ ist. Damit der Abstand 1 wird, muss $T \approx \sqrt{N}$ gelten. Grover ist also ein optimaler Algorithmus; das Universum erlaubt keine schnellere Suche ohne Zusatzwissen.

3. Grover auf Post-Quantum-Kryptographie

In der Praxis der IT-Sicherheit erzwingt Grover längere Schlüssel. Während der Shor-Algorithmus RSA und ECC (Elliptic Curve) komplett zerstört (exponentieller Speedup), "halbiert" Grover nur die effektive Schlüssellänge von symmetrischen Verfahren. Ein 128-Bit-Key hat gegen Grover nur noch eine Sicherheit von 64 Bit – was durch spezialisierte Hardware (ASICs für Grover) knackbar ist. Die Umstellung der Industrie auf 256-Bit-Verschlüsselung (für AES oder SHA-3) ist die direkte Antwort auf die theoretische Existenz von Grover-fähigen Quantenrechnern.