Grovers Suchalgorithmus

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.

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.

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.