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.
Verwandte Begriffe
Quantenschaltkreis
FundamentalsEine Abfolge von Quantengattern, die auf ein Register von Qubits angewendet werden, gefolgt von Messungen.
Hadamard-Gatter
GatesDas Hadamard-Gatter (H) erzeugt aus |0⟩ oder |1⟩ eine gleichmäßige Superposition. Es ist zentral für Quanteninterferenz und Algorithmen wie Grovers Suche.
QFT
AlgorithmsQuanten-Fourier-Transformation — das Quantenanalogon zur diskreten Fourier-Transformation, exponentiell schneller.
Deutsch-Jozsa-Algorithmus
AlgorithmsEin früher Quantenalgorithmus, der mit einer einzigen Abfrage bestimmt, ob eine verborgene Funktion konstant oder ausgeglichen ist — gegenüber bis zu der Hälfte aller möglichen Eingaben klassisch —, historisch bedeutsam als erster Beweis, dass Quantencomputer eine exponentielle Beschleunigung bieten können.
Amplitudenschätzung
AlgorithmsEin Quantenalgorithmus, der die Wahrscheinlichkeitsamplitude eines markierten Ergebnisses quadratisch schneller schätzt als klassisches Monte-Carlo-Sampling — die Grundlage vorgeschlagener Quantenbeschleunigungen bei Derivatbewertung und Risikoanalyse.