Grovers Suchalgorithmus

Finde die Nadel im Heuhaufen in √N Schritten statt N — Amplitudenverstärkung

Rechenbeispiel — Grovers Suchalgorithmus

Aktuelle Iteration	0 (Superposition)
Zielwahrscheinlichkeit	12.50%
Klassisch (1/N)	12.50%
Iteration	0 / 2 · Superposition

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Warum √N und nicht schneller? 🖖

Grovers Algorithmus erreicht die optimale Abfragekomplexität O(√N) — das BBBV-Theorem beweist, dass kein Quantenalgorithmus eine unstrukturierte Datenbank ohne zusätzliche Problemstruktur schneller durchsuchen kann. Die geometrische Anschauung erklärt, warum: Jede Iteration dreht den Zustandsvektor um einen festen Winkel θ ≈ 2/√N in der zweidimensionalen Ebene, die vom Zielzustand und der gleichverteilten Überlagerung aller anderen Zustände aufgespannt wird. Ausgehend vom Äquator dieser Ebene sind etwa (π/4)√N Rotationen nötig, um den Vektor auf die Zielachse zu drehen — genau die O(√N)-Iterationszahl von oben. Da θ mit wachsendem N schrumpft, benötigen größere Suchräume proportional mehr — aber immer noch nur √N, nicht N — Iterationen zur Ausrichtung.

So wird die richtige Antwort verstärkt 🖖

In einer gleichmäßigen Superposition startet jeder Kandidat mit derselben winzigen Amplitude. Jede Runde tut zweierlei: ein Orakel kehrt das Vorzeichen der Zielamplitude um, danach spiegelt eine 'Inversion um den Mittelwert' alle Amplituden an ihrem Durchschnitt — die markierte steigt, die übrigen sinken. Nach mehreren Runden nähert sich die Trefferwahrscheinlichkeit 1. Bei einer Liste mit N = 1,000,000 prüft eine klassische Suche im Schnitt 500,000 Einträge; Grover braucht nur etwa 1,000.

Vier Elemente, ein Schritt, Gewissheit 🖖

Bei N = 4 — einer Suche mit zwei Qubits — ist Grover nicht nur schnell, sondern exakt: eine einzige Iteration trifft das Ziel mit 100% Wahrscheinlichkeit. Der Drehwinkel erfüllt sin(θ/2) = 1/√N = 1/2, also θ = 60°, und nach einem Schritt hat sich der Zustand um genau (2·1+1)·30° = 90° auf die Zielachse gedreht. Es ist der seltene Fall, in dem ein Quantenalgorithmus eine garantierte statt nur wahrscheinliche Antwort liefert.

Aufgabe vollständig gelöst

Zwei Iterationen, um ein markiertes Element unter 8 zu finden 5 Schritte
Der Grover-Algorithmus findet ein markiertes Element unter 8 in zwei Iterationen. Finden Sie heraus, woher die Zwei kommt — und was passiert, wenn Sie eine dritte ausführen.
1. Bevor irgendetwas läuft, ist der Zustand eine gleichmäßige Superposition: Jedes Element ist gleich wahrscheinlich, sodass das markierte Element 1/8 der Wahrscheinlichkeit trägt. Das ist dasselbe wie ein klassisches zufälliges Raten, und das Feld gibt beides aus, um dies zu verdeutlichen.
  
  $N = 8 : uniform superposition gives P = \frac{1}{8} = 12.50%$
2. Jede Grover-Iteration ist eine Drehung um einen festen Winkel in einer zweidimensionalen Ebene, die vom markierten Zustand und allem anderen aufgespannt wird. Der Winkel ergibt sich aus der Amplitude und beträgt für N = 8 etwa 20,7°.
  
  $sin θ = \frac{1}{N} ⟹ θ = 20.7 0^{\circ}; P_{k} = sin^{2} ((2 k + 1) θ)$
3. Die Wahrscheinlichkeit ist also keine Kurve, die ansteigt und sich abflacht — sie ist ein Sinusquadrat, und sie steigt steil an: 12,5%, dann 78,1%, dann 94,5%.
  
  $k = 1 : 78.12%; k = 2 : 94.53%; k = 3 : 33.01%$
4. Der optimale Stopppunkt ist die Drehung, die 90° am nächsten kommt, was π/4-mal die Quadratwurzel aus N ist. Für acht Elemente ist das 2,22, und da man keine fraktionale Iteration durchführen kann, sind es 2.
  
  $k_{opt} = ⌊ \frac{π}{4} N ⌋ = ⌊ 2.221 ⌋ = 2$
5. Führen Sie eine dritte aus, und die Drehung schießt über das Ziel hinaus. Die Wahrscheinlichkeit fällt auf 33,0% — schlechter als nach einer Iteration, und sie steuert wieder auf den Ausgangspunkt zu.
  
  $classical \sim \frac{N}{2} = 4 queries vs O (N) = 2$
Antwort

Das Tool zeigt sowohl für die Ausgangssuperposition als auch für die klassische 1-aus-N-Wahrscheinlichkeit 12,50 % an und beendet den automatischen Durchlauf bei 2. Mit den Steuerungen für den Einzelschritt und den Sprung ans Ende kommst du jedoch bis 5. Das Überschwingen überrascht viele: Mehr Iterationen verschlechtern das Ergebnis, denn die Amplitudenverstärkung ist eine Drehung, und bei Drehungen gelangst du irgendwann wieder zum Ausgangspunkt. Deshalb ist Grovers Beschleunigung auch nur quadratisch und nicht exponentiell. Um 90° zu erreichen, sind etwa √N Drehungen nötig; bei 8 Elementen also 2, bei einer Million 785. Das ist nützlich, aber weit entfernt von dem exponentiellen Vorteil, den das Wort „Quantensuche“ vermuten lässt.

$P_{k} = sin^{2} ((2 k + 1) θ) ROTATES : past k_{opt} it falls again$

Quellen (1)

The algorithm this tool steps through: L. K. Grover, "A fast quantum mechanical algorithm for database search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219, 1996.

Vom 42Math-Team · Aktualisiert 2026-07-29

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

N = 4 - N=4 Elemente — nur 1 Grover-Iteration nötig, um das Ziel zu finden
N = 8 - N=8 Elemente — ~2 Iterationen optimal, klassische Demogröße
N = 16 - N=16 Elemente — 3 Iterationen optimal, O(√N) wird sichtbar
N = 32 - N=32 Elemente — ~4 Iterationen, zeigt den quadratischen Vorteil