Grovers Algorithmus

Grovers Algorithmus, veröffentlicht von Lov Grover im Jahr 1996, bietet eine quadratische Beschleunigung für die unstrukturierte Suche. Für einen Suchraum von N Elementen benötigt die klassische Suche O(N) Abfragen, während Grover nur O(√N) Abfragen benötigt. Der Algorithmus funktioniert, indem er wiederholt den „Grover-Diffusionsoperator“ anwendet — der die Amplitude des Zielzustands verstärkt und andere unterdrückt — durch einen Prozess namens Amplitudenverstärkung. Nach ~π√N/4 Iterationen liefert die Messung des Zustands das Zielelement mit hoher Wahrscheinlichkeit. Grovers Algorithmus ist nachweislich optimal — kein Quantenalgorithmus kann bei unstrukturierter Suche besser abschneiden. Zu den Anwendungen zählen Datenbanksuche, das Lösen NP-schwerer Probleme und Quantenkryptanalyse. HLQuantum enthält eine eingebaute Grover-Implementierung.