Der Grover-Algorithmus erklärt
Der Grover-Algorithmus ist ein Quantenprogramm für die Suche. Lov Grover hat ihn 1996 bei den Bell Labs veröffentlicht. Bei N Möglichkeiten braucht ein normaler Computer im Schnitt N/2 Versuche, ein Quantencomputer mit Grover nur ungefähr die Wurzel aus N Schritte. Bei einer Million Möglichkeiten sind das rund tausend statt einer halben Million.
Die Aufgabe: eine Nadel im Heuhaufen
Stell dir ein Zahlenschloss mit sieben Rädern vor. Es gibt 10.000.000 mögliche Codes, und nur einer passt. Ohne weitere Hinweise bleibt einem normalen Computer nichts anderes übrig, als die Codes der Reihe nach auszuprobieren: im Schnitt 5.000.000 Versuche.
Ein Quantencomputer kann das mit dem Grover-Algorithmus in deutlich weniger Schritten schaffen. Voraussetzung ist eine Prüfregel, die für jeden Kandidaten sagen kann: passt oder passt nicht.
Probier es aus: Findet die Quantensuche deinen Code? So funktioniert die Quantensuche in drei Schritten
Erstens: Alle Qubits kommen mit H in eine gleichmäßige Überlagerung. Jetzt steckt jede Möglichkeit mit demselben kleinen Gewicht im Zustand.
Zweitens: Die Prüfregel markiert die richtige Möglichkeit, indem sie ihr Vorzeichen umdreht. Messen würde man davon noch nichts, die Wahrscheinlichkeiten bleiben gleich.
Drittens: Ein Verstärkungsschritt spiegelt alle Gewichte am Durchschnitt. Dadurch wächst das Gewicht der markierten Möglichkeit, alle anderen schrumpfen ein wenig. Markieren und Verstärken zusammen sind eine Runde. Nach ungefähr π/4 mal der Wurzel aus N Runden misst man mit sehr hoher Wahrscheinlichkeit die richtige Antwort.
Wie viel schneller ist das?
Der Vorteil ist quadratisch: Aus N Versuchen werden etwa Wurzel aus N Schritte. Bei unserem siebenstelligen Zahlenschloss rechnet unser Simulator mit 24 Qubits, also 16.777.216 Möglichkeiten, und braucht dafür 3.216 Runden statt im Schnitt 5.000.000 Versuchen.
Grover selbst hat gezeigt, dass seine Methode bis auf einen festen Faktor so schnell ist, wie eine Quantensuche ohne weitere Hinweise überhaupt sein kann. Das ist ein großer, aber kein grenzenloser Vorteil.
Wichtig: Die eingesparten Schritte zählen bei einem echten Quantencomputer. Unser Simulator rechnet diese Schritte auf normaler Hardware nach, damit du sie erleben kannst.
Was der Grover-Algorithmus nicht kann
Mehr Runden sind nicht besser. Rechnet man über die richtige Zahl hinaus, schrumpft das Gewicht der richtigen Antwort wieder. Die Rundenzahl muss deshalb zur Größe der Suche passen.
Außerdem braucht Grover eine Prüfregel, die der Quantencomputer selbst ausführen kann. Für eine fremde, unbekannte PIN oder ein Passwort auf einem Server gibt es so eine Regel nicht einfach. Gegen gute Verschlüsselung mit langen Schlüsseln reicht der quadratische Vorteil allein nicht aus.
Häufige Fragen zum Grover-Algorithmus
Was ist der Grover-Algorithmus einfach erklärt?
Ein Quantenprogramm für die Suche. Es bringt alle Möglichkeiten in Überlagerung, markiert die richtige mit einer Prüfregel und verstärkt sie Runde für Runde, bis eine Messung sie mit hoher Wahrscheinlichkeit liefert.
Wer hat den Grover-Algorithmus erfunden?
Lov K. Grover, damals bei den Bell Labs. Er hat ihn 1996 veröffentlicht.
Wie viel schneller ist der Grover-Algorithmus?
Quadratisch schneller: Statt etwa N Versuchen braucht er ungefähr die Wurzel aus N Schritte. Bei einer Million Möglichkeiten sind das rund tausend Schritte.
Kann der Grover-Algorithmus Passwörter knacken?
Nicht einfach so. Er braucht eine Prüfregel, die der Quantencomputer selbst ausführen kann, und er beschleunigt die Suche nur quadratisch. Lange Schlüssel bleiben deshalb sicher.
Warum macht man nicht einfach mehr Runden?
Weil sich das Gewicht der richtigen Antwort nach der passenden Rundenzahl wieder verringert. Zu viele Runden verschlechtern das Ergebnis.
- Was ist ein Quantencomputer? Einfach erklärt
- Was ist ein Qubit?
- Überlagerung (Superposition) einfach erklärt
- Verschränkung einfach erklärt
- Kann ein Quantencomputer Verschlüsselung knacken?
- Quantencomputer-Simulator
Quellen
- Lov K. Grover: A fast quantum mechanical algorithm for database search (Bell Labs, 1996)
- Bundesregierung: Quantencomputing kurz erklärt
Stand: 31. Oktober 2026
Lass die Quantensuche deinen Code finden.
Leg am Zahlenschloss einen Testcode fest und sieh zu, wie unser Simulator ihn sucht. Ohne Anmeldung.