Meine Merkliste

Home
Lexikon
Grover-Algorithmus

Grover-Algorithmus

Der Grover-Algorithmus ist ein Quantenalgorithmus zur Suche in einer unsortierten Datenbank mit N Einträgen in $O(\sqrt{N})$ Schritten und mit $O (log N)$ Speicherbedarf (siehe O-Notation). Er wurde von Lov Grover im Jahre 1996 veröffentlicht^[1] und ist der bislang einzige bekannte Beweis, dass Quantenrechner prinzipiell schneller als klassische Computer sind.^[2]

Auf einem klassischen Computer ist der prinzipiell schnellstmögliche Suchalgorithmus in einer unsortierten Datenbank die lineare Suche, die O(N) Rechenschritte erfordert. Der Grover-Algorithmus mit O(N^1/2) Schritten liefert damit eine quadratische Beschleunigung, was bei großen N beträchtlich ist.

Wie die meisten Quantenalgorithmen ist der Grover-Algorithmus ein probabilistischer Algorithmus, d.h. er gibt die korrekte Antwort mit hoher Wahrscheinlichkeit, wobei die Wahrscheinlichkeit einer fehlerhaften Antwort durch einfache Wiederholung des Algorithmus verkleinert wird.

Weiteres empfehlenswertes Fachwissen

Was ist der richtige Weg, um die Wiederholbarkeit bei Waagen zu überprüfen?

Leitfaden zu den grundlegenden Laborkenntnissen

Richtiges Wägen mit Laborwaagen: Die Wägefibel

Inhaltsverzeichnis

1 Anwendungen
2 Detaillierter Ablauf
- 2.1 Voraussetzungen
- 2.2 Schrittabfolge
3 Geometrische Sicht und Bestimmung der Schrittzahl r(N)
4 Erweiterungen
5 Optimalität des Grover-Algorithmus
6 Verwandte Themen
7 Quellen

Anwendungen

Der Grover-Algorithmus ermöglicht neben der Suche in unsortierten Datenbanken die Umkehrung einer endlichen Funktion y=f(x), denn zu einem gegebenen Wert y entspricht ein Wert $x = f - 1 (y)$ der Suche nach einem Wert x im Definitionsbereich von f.

Der Grover-Algorithmus kann ebenso zur Berechnung des Mittelwerts und des Medians einer Menge von Zahlen verwendet werden, sowie zur Lösung des Kollisionsproblems. Weiter kann er zur Lösung NP-vollständiger Probleme eingesetzt werden, indem er die Menge aller möglichen Probleme durchläuft. Obwohl damit "große" NP-vollständige Probleme beträchtlich schneller gelöst werden können, ermöglicht auch der Grover-Algorithmus keine Lösung in polynomialer Zeitkomplexität.

Detaillierter Ablauf

Der folgende Ablauf des Algorithmus bezieht sich auf die Suche nach einem einzelnen Sucheintrag. Der Algorithmus kann weiter optimiert werden, um einen von mehreren möglichen Einträgen zu finden, wobei deren Anzahl im Vorhinein bekannt ist.

Voraussetzungen

Gegeben sei eine unsortierte Datenbank mit N Einträgen, die in einem N-dimensionalen Zustandsraum $\mathcal{H}$ durch log₂N Qubits dargestellt wird. Die Einträge seien mit 0, 1, ..., (N-1) durchnumeriert. Dann wählen wir eine auf $\mathcal{H}$ wirkende Observable Ω mit N verschiedenen Eigenzuständen

$\{|0\rang, |1\rang, \cdots, |N-1\rang\}$

(in der Bra-Ket-Notation) und den zugehörigen Eigenwerten

$\{\lambda_0, \lambda_1, \cdots, \lambda_{N-1} \}.$

Ferner sei ein unitärer Operator U_ω gegeben, der eine Subroutine, das sogenannte "Orakel", darstellt, die die Datenbankeinträge effizient nach dem Suchkriterium vergleicht. Der Algorithmus legt nicht fest, wie das Orakel arbeitet, es muss allerdings die Superposition der Quantenzustände verarbeiten und den gesuchten Eigenzustand |ω> erkennen:

$U_\omega |\omega\rang = - |\omega\rang$

$U_\omega |x\rang = |x\rang \qquad \forall x \ne \omega$

Ziel des Algorithmus ist es, diesen Eigenzustand |ω>, bzw. äquivalent den Eigenwert ω zu identifizieren.

Schrittabfolge

Initialisiere das System in den Zustand
$|s\rang = \frac{1}{\sqrt{N}} \sum_x |x\rang$
Führe die folgende "Grover-Iteration" r(N)-mal durch. (Die Funktion r(N) wird weiter unten beschrieben.)
1. Wende den Operator $U ω$ an;
2. Wende den Operator $U_s = 2 \left|s\right\rangle \left\langle s\right| - I$ an.
Führe die Messung von Ω durch. Das Messergebnis beträgt λ_ω mit einer Wahrscheinlichkeit nahe 1, falls N>>1. Mit der Messung von λ_ω ist das System im Zustand ω.

Geometrische Sicht und Bestimmung der Schrittzahl r(N)

Der Anfangszustand lautet

$|s\rang = \frac{1}{\sqrt{N}} \sum_x |x\rang.$

$\lang\omega|s\rang = \frac{1}{\sqrt{N}}$

Geometrisch bedeutet das, dass |ω> and |s> in einem Winkel von (π/2 - θ) zueinander stehen, wobei θ = θ(N) gegeben ist durch:

$\cos \left(\frac{\pi}{2} - \theta \right) = \frac{1}{\sqrt{N}}$

d.h.,

$\sin \theta = \frac{1}{\sqrt{N}}$

Der Operator U_ω ist eine Spiegelung an der zu |ω> orthogonalen Hyperebene; für Vektoren in der von |s> und |ω> aufgespannten Ebene wirkt er als Spiegelung an der Geraden durch |ω^×>. Der Operator U_s ist eine Spiegelung an der Geraden durch |s>. Der Zustandsvektor bleibt also nach der Anwendung von U_s und U_ω in der durch |s> und |ω> aufgespannten Ebene. Damit rotiert der Operator U_sU_ω bei jedem Schritt der Grover-Iteration den Zustandsvektor um einen Winkel von 2θ nach |ω>.

Der Algorithmus muss also anhalten, sobald der Zustandsvektor |ω> am nächsten gekommen ist. Weitere Iterationen würden ihn wieder von |ω> weg drehen und damit die Wahrscheinlichkeit der korrekten Antwort wieder verkleinern. Für die optimale Anzahl r an Iterationen zur exakten Übereinstimmung mit |ω> gilt:

$\frac{\pi}{2} - \theta = 2 \theta r,$

also

$r(N) = \frac{\pi}{4 \theta(N)} - \frac{1}{2}$

Da r aber eine ganze Zahl sein muss, setzen wir r gleich der gerundeten Zahl π/4θ - 1/2. Damit beträgt die Wahrscheinlichkeit, eine falsche Antwort zu messen, O(1 - cos²θ) = O(sin²θ). Die Irrtumswahrscheinlichkeit bei N Datenbankeinträgen lautet also asymptotisch O(1/N), d.h. sie ist vernachlässigbar klein für große N.

Für N>>1 gilt θ ≈ N^-1/2, also

$r(N) \to \frac{\pi \sqrt{N}}{4}$

Erweiterungen

Enthält die Datenbank nicht nur einen, sondern k gesuchte Einträge, so funktioniert der Algorithmus ebenfalls, allerdings gilt für die Anzahl r durchzuführender Iterationen nun π(N/k)^1/2/4 statt πN^1/2/4. Ist k unbekannt, so führt man den Grover-Algorithmus in

$\pi \frac{N^{1/2}}{4}, \pi \frac{(N/2)^{1/2}}{4}, \pi \frac{(N/4)^{1/2}}{4}, \ldots$

Iterationen durch. Für beliebiges k wird ein gesuchter Eintrag mit genügend hoher Wahrscheinlichkeit gefunden. Die Gesamtzahl von Iterationen beträgt höchstens

$\pi \frac{N^{1/2}}{4} \left( 1+ \frac{1}{\sqrt{2}}+\frac{1}{2}+\cdots\right) = O(\sqrt{N})$

Optimalität des Grover-Algorithmus

Der Grover-Algorithmus ist optimal in dem Sinne, dass es keinen Quantenalgorithmus mit weniger als $O(\sqrt{N})$ Rechenschritten geben kann.^[3] Dieses Resultat ist wichtig, um die Grenzen des Quantenrechnens zu verstehen. Wäre das Suchproblem beispielsweise im ungünstigste Fall mit $O (log c N)$ Schritten lösbar, so wäre NP in BQP enthalten.

Ebenso ist die Anzahl i.A. notwendiger Iterationen für k gesuchte Einträge, also π(N/k)^1/2/4, optimal.

Quellen

↑ Grover, L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
↑ Zwar ist mit dem Shor-Algorithmus ein polynomial schneller Faktorisierungsalgorithmus bekannt, während alle bekannten klassischen Faktorisierungen exponentielle Komplexität besitzen; allerdings gibt es keinen mathematischen Beweis, dass nicht doch auch ein polynomial schneller klassischer Algorithmus existiert.
↑ Bennett C.H., Bernstein E., Brassard G., Vazirani U.: The strengths and weaknesses of quantum computation. SIAM Journal on Computing 26(5): 1510-1523 (1997)

Kategorie: Quanteninformatik

Dieser Artikel basiert auf dem Artikel Grover-Algorithmus aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation. In der Wikipedia ist eine Liste der Autoren verfügbar.