Einführung

Grovers Algorithmus ist ein Quantenalgorithmus für sogenannte unstrukturierte Suchprobleme, der eine quadratische Verbesserung gegenüber klassischen Algorithmen bietet. Das bedeutet: Grovers Algorithmus benötigt eine Anzahl von Operationen in der Größenordnung der Quadratwurzel der Anzahl von Operationen, die zur Lösung einer unstrukturierten Suche klassisch erforderlich sind – was gleichbedeutend damit ist, dass klassische Algorithmen für unstrukturierte Suche mindestens Kosten in der Größenordnung des Quadrats der Kosten von Grovers Algorithmus aufweisen müssen.

Grovers Algorithmus und seine Erweiterungen sowie die zugrunde liegende Methodik erweisen sich als breit anwendbar und bieten einen quadratischen Vorteil bei vielen interessanten Berechnungsaufgaben, die auf den ersten Blick gar nicht wie unstrukturierte Suchprobleme aussehen.

Auch wenn die breite Anwendbarkeit von Grovers Suchtechnik überzeugend ist, sollte zu Beginn dieser Lektion anerkannt werden, dass der quadratische Vorteil gegenüber klassischen Computern in absehbarer Zeit voraussichtlich keinen praktischen Nutzen bringen wird. Die klassische Computerhardware ist der Quantencomputerhardware weit überlegen – und der quadratische Quantenvorteil, den Grovers Algorithmus bietet, wird für jedes unstrukturierte Suchproblem, das in absehbarer Zeit ausführbar sein könnte, durch die enormen Taktfrequenzen moderner klassischer Computer wettgemacht.

Mit dem Fortschritt der Quantencomputertechnologie könnte Grovers Algorithmus jedoch Potenzial entfalten. Tatsächlich bieten einige der wichtigsten und wirkungsvollsten klassischen Algorithmen aller Zeiten – darunter die schnelle Fourier-Transformation und schnelle Sortierverfahren (zum Beispiel Quicksort und Mergesort) – einen etwas weniger als quadratischen Vorteil gegenüber naiven Ansätzen für die Probleme, die sie lösen. Der entscheidende Unterschied besteht natürlich darin, dass für Grovers Algorithmus eine völlig neue Technologie (nämlich Quantencomputing) erforderlich ist. Obwohl diese Technologie im Vergleich zur klassischen Datenverarbeitung noch in den Kinderschuhen steckt, sollten wir das Potenzial technologischer Fortschritte nicht unterschätzen – Fortschritte, die eines Tages erlauben könnten, dass ein quadratischer Quantenvorteil greifbare praktische Vorteile bietet.

Lektionsvideo

Im folgenden Video führt John Watrous durch den Inhalt dieser Lektion zu Grovers Algorithmus. Alternativ kannst du das YouTube-Video für diese Lektion in einem separaten Fenster öffnen. Folien herunterladen für diese Lektion.