Grover-Algorithmus

1996 entwickelte Lov Grover bei Bell Labs einen Suchalgorithmus für Quantencomputer. Das Problem: In einer unsortierten Datenbank mit N Einträgen muss ein klassischer Computer im Durchschnitt N/2 Einträge prüfen, um einen bestimmten zu finden. Grovers Algorithmus schafft das in etwa √N Schritten.

Konkret: Eine Datenbank mit einer Million Einträgen erfordert klassisch im Schnitt 500.000 Prüfungen. Grovers Algorithmus braucht nur etwa 1.000. Bei einer Milliarde Einträgen: klassisch 500 Millionen, Grover etwa 31.600. Die Beschleunigung ist quadratisch, also weniger dramatisch als die exponentielle Beschleunigung durch Shors Algorithmus, aber auf deutlich mehr Probleme anwendbar.

Der Algorithmus nutzt sogenannte Amplitudenverstärkung: Durch wiederholte Anwendung einer bestimmten Quantenoperation wird die Wahrscheinlichkeit, den gesuchten Eintrag zu messen, schrittweise erhöht, während die Wahrscheinlichkeit aller anderen Einträge sinkt.

Für die Kryptografie bedeutet Grovers Algorithmus, dass symmetrische Verschlüsselungen wie AES halbiert werden: AES-256 bietet gegen einen Quantencomputer nur noch 128 Bit Sicherheit. Das ist immer noch ausreichend, weshalb symmetrische Verfahren als quantensicher gelten, solange die Schlüssellänge verdoppelt wird.

Gerade weil der Grover-Algorithmus auf nahezu jede Suchaufgabe anwendbar ist, hat er trotz seiner bescheideneren Beschleunigung große praktische Bedeutung. Wo Shors Algorithmus nur ganz bestimmte Probleme angreift, verspricht Grover einen breiten, wenn auch quadratischen Vorteil bei der Suche im Ungeordneten. Für die Verschlüsselung bedeutet das eine kalkulierbare, keine katastrophale Bedrohung, denn symmetrische Verfahren bleiben mit verdoppelter Schlüssellänge sicher. Grovers Verfahren zeigt damit, dass nicht jeder Quantenfortschritt das digitale Fundament sprengt, sondern manche es nur ein Stück weit verschieben.