Grover-Suchalgorithmus

Es sei eine Menge von Indizes, und eine Funktion, die überprüft, ob ein gegebener Index eine gewisse Eigenschaft erfüllt oder nicht, also oder . Mit Hilfe des GROVER-Suchalgorithmus [23.5] ist es möglich, mit nur -maligem Aufrufen der Funktion einen Index zu finden, der die gewünschte Eigenschaft erfüllt.

Dieser Algorithmus ist für eine gewisse Klasse von Problemen nützlich, nämlich für solche, für die es zwar einfach ist zu überprüfen, ob eine gegebene Antwort das Problem löst, es aber umgekehrt schwierig ist, eine solche Antwort zu finden.

Beispiel A: Suche in einer unstrukturierten Datenbank

In einer Datenbank mit Einträgen, die keine Ordnung aufweisen, soll ein vorgegebener Eintrag gefunden werden. Zum Beispiel soll in einem Telefonbuch der Eintrag zu einer gegebenen Telefonnummer bestimmt werden. Klassische Algorithmen wie eine Suche der Reihe nach oder das zufällige Wählen von Elementen müssen im Mittel Einträge untersuchen. Mit Hilfe des GROVER-Suchalgorithmus genügt es nur Elemente zu untersuchen.

Beispiel B: Handlungsreisender

Der GROVER-Suchalgorithmus kann somit auch die brute-force-Suche, das Duchprobieren aller Möglichkeiten, bei Problemen wie dem des Handlungsreisenden beschleunigen (siehe auch Rundreiseproblem und Transportnetze). Für eine Menge von Städten finde man eine Route, die alle Städte verbindet, deren Länge aber eine gegebene Grenze nicht überschreitet. Ein möglicher klassischer Algorithmus ist offenbar, alle verschiedenen Routen der Reihe nach zu testen, bis man auf eine mit der gewünschten Länge stößt.

• Orakel
• Such-Algorithmus