Einführung

Der Grover-Algorithmus ist ein Quantenalgorithmus für sogenannte unstrukturierte Suchprobleme, der eine quadratische Verbesserung gegenüber klassischen Algorithmen bietet. Das bedeutet, dass Grovers Algorithmus eine Anzahl von Operationen in der Größenordnung der Quadratwurzel der Anzahl von Operationen erfordert, die erforderlich sind, um die unstrukturierte Suche klassisch zu lösen - was gleichbedeutend damit ist, dass klassische Algorithmen für die unstrukturierte Suche Kosten mindestens in der Größenordnung des Quadrats der Kosten von Grovers Algorithmus haben müssen.

Grovers Algorithmus, seine Erweiterungen und die zugrundeliegende Methodik erweisen sich als breit anwendbar, was zu einem quadratischen Vorteil für viele interessante Berechnungsaufgaben führt, die auf den ersten Blick nicht wie unstrukturierte Suchprobleme aussehen mögen.

Obwohl die breite Anwendbarkeit von Grovers Suchtechnik überzeugend ist, sollte hier zu Beginn der Lektion eingeräumt werden, dass der quadratische Vorteil, den sie bietet, wohl kaum in absehbarer Zeit zu einem praktischen Vorteil von Quantencomputern gegenüber klassischen Computern führen wird. Klassische Computerhardware ist viel fortschrittlicher als Quantencomputerhardware - und der quadratische Quantenvorteil, den Grovers Algorithmus gegenüber klassischen Computern bietet, wird mit Sicherheit durch die schwindelerregenden Taktraten moderner klassischer Computer für jedes unstrukturierte Suchproblem, das in absehbarer Zeit durchführbar wäre, zunichte gemacht werden.

Mit den Fortschritten in der Quantencomputertechnologie könnte Grovers Algorithmus jedoch Potenzial haben. Einige der wichtigsten und einflussreichsten klassischen Algorithmen, die je entdeckt wurden, wie die schnelle Fourier-Transformation und die schnelle Sortierung (z. B. Quicksort und Merge-Sort), bieten sogar etwas weniger als einen quadratischen Vorteil gegenüber naiven Ansätzen für die Probleme, die sie lösen. Der Hauptunterschied besteht natürlich darin, dass für die Ausführung von Grovers Algorithmus eine völlig neue Technologie (d. h. Quantencomputer) erforderlich ist. Auch wenn diese Technologie im Vergleich zum klassischen Rechnen noch in den Kinderschuhen steckt, sollten wir das Potenzial der technologischen Fortschritte, die es ermöglichen könnten, dass ein quadratischer Vorteil des Quantencomputers gegenüber dem klassischen Rechnen eines Tages greifbare praktische Vorteile bietet, nicht so schnell unterschätzen.

Lektionsvideo

Im folgenden Video führt John Watrous Sie durch den Inhalt dieser Lektion über den Grover-Algorithmus. Alternativ können Sie das YouTube Video zu dieser Lektion in einem separaten Fenster öffnen. Laden Sie die Folien zu dieser Lektion herunter.