🔍 Grovers Suchalgorithmus

Die optimale Anzahl beträgt etwa π/4·√N. Für N = 16 rundet sich das auf 3 Iterationen, bei denen die Zielwahrscheinlichkeit nahe ihrem Maximum liegt. Die Infoleiste zeigt dies als "π/4·√16 ≈ 3" an.

Klassisch benötigt die Suche in einer unsortierten Liste von N Elementen im Durchschnitt etwa N/2 Vergleiche (8 für N = 16). Grover findet das Ziel in nur O(√N) Iterationen, eine quadratische Beschleunigung. Für eine Million Elemente sind das etwa 1.000 Abfragen statt 500.000.

Grover-Iterationen sind eine Rotation, daher schießen sie über das Ziel hinaus. Nach dem optimalen Punkt sinkt die Zielwahrscheinlichkeit wieder, während sich der Zustand über die Lösung hinausdreht. Die Simulation bezeichnet dies als "Über-Rotation" und zeigt, dass mehr Iterationen nicht immer besser sind.

Es ist der unitäre Operator D = 2|s⟩⟨s| − I, wobei |s⟩ die gleichmäßige Überlagerung ist. In der Praxis spiegelt er jede Amplitude um den Durchschnitt aller Amplituden, was jeden Wert verstärkt, den das Orakel unter den Mittelwert gedrückt hat, nämlich das markierte Ziel.

Die Amplitudenarithmetik ist für einen idealisierten, rauschfreien Quantencomputer mit reellen Amplituden exakt, was alles ist, was Grovers Algorithmus benötigt. Sie lässt reale Effekte wie Dekohärenz, Gatterfehler und Messkollaps aus, ist also ein getreues mathematisches Modell und keine Hardware-Emulation.

Der Algorithmus beginnt damit, das Register in eine gleichmäßige Überlagerung zu versetzen, typischerweise über Hadamard-Gatter, sodass jedes Element die Amplitude 1/√N = 1/4 und die Wahrscheinlichkeit 1/16 (6,25%) hat. Dieser gleiche Startpunkt spiegelt wider, dass kein Vorwissen darüber besteht, wo das Ziel liegt.

Nein. Für unstrukturierte Suche ist die O(√N)-Skalierung nachweislich optimal; kein Quantenalgorithmus kann ein markiertes Element mit weniger Orakelabfragen finden. Diese Optimalität, bewiesen von Bennett, Bernstein, Brassard und Vazirani, macht Grover zu einem Maßstab für Quantensuche.

Grover-artige Amplitudenverstärkung beschleunigt Brute-Force-Aufgaben: das Durchsuchen unstrukturierter Datenbanken, das Invertieren von Funktionen, das Lösen von Constraint- und SAT-Problemen und das Angreifen symmetrischer Kryptografie (Halbierung der effektiven Schlüsselstärke), weshalb Post-Quanten-Empfehlungen größere Schlüsselgrößen empfehlen.