Abschließende Bemerkungen

Im Rahmen des Abfragemodells ist Grovers Algorithmus asymptotisch optimal. Das bedeutet, dass es keinen Abfragealgorithmus geben kann, der das Such-Problem – oder speziell das Eindeutige-Such-Problem – mit asymptotisch weniger als $O(\sqrt{N})$ Abfragen im schlechtesten Fall löst. Dies wurde auf mehrere Arten rigoros bewiesen.

Interessanterweise war dies bereits bekannt, bevor Grovers Algorithmus entdeckt wurde – der Algorithmus entsprach einer bereits bekannten unteren Schranke.

Grovers Algorithmus ist zudem breit anwendbar, da die quadratische Beschleunigung, die er bietet, in verschiedensten Kontexten erzielt werden kann. Manchmal lässt sich Grovers Algorithmus beispielsweise in Kombination mit einem anderen Algorithmus einsetzen, um eine Verbesserung zu erzielen. Außerdem wird Grovers Algorithmus häufig als Unterroutine in anderen Quantenalgorithmen verwendet, um Beschleunigungen zu erzielen.

Schließlich lässt sich die in Grovers Algorithmus verwendete Technik – bei der zwei Spiegelungen komponiert und iteriert werden, um einen Quantenzustandsvektor zu rotieren – verallgemeinern. Ein Beispiel ist die Technik der Amplitudenverstärkung (Amplitude Amplification), bei der ein ähnlicher Prozess wie bei Grovers Algorithmus auf einen anderen Quantenalgorithmus angewendet werden kann, um dessen Erfolgswahrscheinlichkeit quadratisch schneller zu steigern, als es klassisch möglich wäre. Die Amplitudenverstärkung findet breite Anwendung in Quantenalgorithmen.

Obwohl Grovers Algorithmus möglicherweise in absehbarer Zeit keinen praktischen Quantenvorteil bei der Suche bieten wird, ist er ein grundlegend wichtiger Quantenalgorithmus – und repräsentativ für eine allgemeinere Technik mit vielen Anwendungen in der Quantenalgorithmik.