Grover-Algorithmus

Der Grover-Algorithmus ist ein Quantenalgorithmus zur Suche in einer unsortierten Datenbank mit ${\displaystyle N}$ Einträgen in ${\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}$ Schritten und mit ${\displaystyle {\mathcal {O}}\left(\log N\right)}$ Speicherbedarf (siehe O-Notation). Er wurde von Lov Grover im Jahre 1996 veröffentlicht[1] und ist der bislang einzige bekannte Algorithmus, für den bewiesen ist, 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 ${\displaystyle {\mathcal {O}}\left(N\right)}$ Rechenschritte erfordert. Der Grover-Algorithmus liefert damit eine quadratische Beschleunigung, was für große ${\displaystyle N}$ beträchtlich ist.

Wie d​ie meisten Quantenalgorithmen i​st der Grover-Algorithmus e​in probabilistischer Algorithmus, d. h., e​r gibt d​ie korrekte Antwort m​it hoher Wahrscheinlichkeit, w​obei die Wahrscheinlichkeit e​iner fehlerhaften Antwort d​urch einfache Wiederholung d​es Algorithmus verkleinert werden kann.

Anwendungen

Der Grover-Algorithmus ermöglicht eigentlich nicht die direkte Suche in unsortierten Datenbanken, sondern die Umkehrung einer endlichen Funktion ${\displaystyle y=f(x)}$, denn zu einem gegebenen Wert ${\displaystyle y}$ entspricht ein Wert ${\displaystyle x=f^{-1}(y)}$ der Suche nach einem Wert ${\displaystyle x}$ im Definitionsbereich von ${\displaystyle f}$.

Der Grover-Algorithmus k​ann ebenso z​ur Berechnung d​es Mittelwerts u​nd des Medians e​iner Menge v​on Zahlen verwendet werden, s​owie zur Lösung d​es Kollisionsproblems. Weiter k​ann er z​ur Lösung NP-vollständiger Probleme eingesetzt werden, i​ndem er d​ie Menge a​ller möglichen Probleme durchläuft. Obwohl d​amit NP-vollständige Probleme beträchtlich schneller gelöst werden können, ermöglicht a​uch der Grover-Algorithmus k​eine Lösung i​n polynomialer Zeitkomplexität.

Detaillierter Ablauf

Der folgende Ablauf d​es Algorithmus bezieht s​ich auf d​ie Suche n​ach einem einzelnen Sucheintrag. Der Algorithmus k​ann weiter optimiert werden, u​m einen v​on mehreren möglichen Einträgen z​u finden, w​obei deren Anzahl i​m Vorfeld bekannt ist.

Voraussetzungen

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

${\displaystyle \left\{\left\vert 0\right\rangle ,\left\vert 1\right\rangle ,\cdots ,\left\vert N-1\right\rangle \right\}}$

(in d​er Bra-Ket-Notation) u​nd den zugehörigen Eigenwerten

${\displaystyle \left\{\lambda _{0},\lambda _{1},\cdots ,\lambda _{N-1}\right\}.}$

Ferner sei ein unitärer Operator ${\displaystyle U_{\omega }}$ 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 ${\displaystyle \left\vert \omega \right\rangle }$ erkennen:

${\displaystyle U_{\omega }\left\vert \omega \right\rangle =-\left\vert \omega \right\rangle }$

${\displaystyle U_{\omega }\left\vert x\right\rangle =\left\vert x\right\rangle \qquad \forall x\neq \omega }$

Ziel des Algorithmus ist es, diesen Eigenzustand ${\displaystyle \left\vert \omega \right\rangle }$, bzw. äquivalent den Eigenwert ${\displaystyle \omega }$ zu identifizieren.

Schrittabfolge

1. Initialisiere das System in den Zustand

   ${\displaystyle \left\vert s\right\rangle ={\frac {1}{\sqrt {N}}}\sum _{x}\left\vert x\right\rangle }$

2. Führe die folgende sog. Grover-Iteration ${\displaystyle r(N)}$-mal durch. (Die Funktion ${\displaystyle r}$ wird weiter unten beschrieben.)
   1. Wende den Operator ${\displaystyle U_{\omega }=I-2\left\vert \omega \right\rangle \left\langle \omega \right\vert }$ an (erste Householdertransformation).
   2. Wende den Operator ${\displaystyle U_{s}=-(I-2\left\vert s\right\rangle \left\langle s\right\vert )}$ an (zweite Householdertransformation).
3. Führe die Messung von ${\displaystyle \Omega }$ durch. Das Messergebnis beträgt ${\displaystyle \lambda _{\omega }}$ mit einer Wahrscheinlichkeit nahe ${\displaystyle 1}$, falls ${\displaystyle N\gg 1}$. Mit der Messung von ${\displaystyle \lambda _{\omega }}$ ist das System im Zustand ${\displaystyle \omega }$.

Geometrische Sicht und Bestimmung der Schrittzahl r(N)

Der Anfangszustand lautet

${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x}|x\rangle .}$

Betrachten wir die von ${\displaystyle \left\vert s\right\rangle }$ und ${\displaystyle \left\vert \omega \right\rangle }$ aufgespannte Ebene. Sei ${\displaystyle \vert \omega ^{\times }\rangle }$ ein Ket-Vektor in dieser Ebene, senkrecht zu ${\displaystyle \left\vert \omega \right\rangle }$. Da ${\displaystyle \left\vert \omega \right\rangle }$ einer der Basisvektoren ist, folgt

${\displaystyle \langle \omega \mid s\rangle ={\frac {1}{\sqrt {N}}}}$

Geometrisch bedeutet das, dass ${\displaystyle \left\vert \omega \right\rangle }$ und ${\displaystyle \left\vert s\right\rangle }$ in einem Winkel von ${\displaystyle {\tfrac {\pi }{2}}-\theta }$ zueinander stehen, wobei ${\displaystyle \theta =\theta (N)}$ gegeben ist durch

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

folglich ist

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

Der Operator ${\displaystyle U_{\omega }}$ ist eine Spiegelung an der zu ${\displaystyle \left\vert \omega \right\rangle }$ orthogonalen Hyperebene; für Vektoren in der von ${\displaystyle \left\vert s\right\rangle }$ und ${\displaystyle \left\vert \omega \right\rangle }$ aufgespannten Ebene wirkt er als Spiegelung an der Geraden durch ${\displaystyle \vert \omega ^{\times }\rangle }$. Der Operator ${\displaystyle U_{s}}$ ist eine Spiegelung an der Geraden durch ${\displaystyle \left\vert s\right\rangle }$. Der Zustandsvektor bleibt also nach der Anwendung von ${\displaystyle U_{s}}$ und ${\displaystyle U_{\omega }}$ in der durch ${\displaystyle \left\vert s\right\rangle }$ und ${\displaystyle \left\vert \omega \right\rangle }$ aufgespannten Ebene. Damit rotiert der Operator ${\displaystyle U_{s}\ U_{\omega }}$ bei jedem Schritt der Grover-Iteration den Zustandsvektor um einen Winkel von ${\displaystyle 2\theta }$ nach ${\displaystyle \left\vert \omega \right\rangle }$.

Der Algorithmus muss also anhalten, sobald der Zustandsvektor ${\displaystyle \left\vert \omega \right\rangle }$ am nächsten gekommen ist. Weitere Iterationen würden ihn wieder davon weg drehen und damit die Wahrscheinlichkeit der korrekten Antwort wieder verkleinern. Für die optimale Anzahl ${\displaystyle r}$ an Iterationen zur exakten Übereinstimmung mit ${\displaystyle \left\vert \omega \right\rangle }$ gilt

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

also

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

Da ${\displaystyle r}$ aber eine ganze Zahl sein muss, setzen wir ${\displaystyle r}$ gleich der gerundeten Zahl ${\displaystyle {\tfrac {\pi }{4\theta }}-{\tfrac {1}{2}}}$. Damit beträgt die Wahrscheinlichkeit, eine falsche Antwort zu messen, ${\displaystyle {\mathcal {O}}\left(1-\cos ^{2}\theta \right)={\mathcal {O}}\left(\sin ^{2}\theta \right)}$. Die Irrtumswahrscheinlichkeit bei ${\displaystyle N}$ Datenbankeinträgen lautet also asymptotisch ${\displaystyle {\mathcal {O}}\left({\tfrac {1}{N}}\right)}$, d. h., sie ist vernachlässigbar klein für große ${\displaystyle N}$.

Für ${\displaystyle N\gg 1}$ gilt ${\displaystyle \theta \approx N^{-{\frac {1}{2}}}}$, also

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

Erweiterungen

Enthält die Datenbank nicht nur einen, sondern ${\displaystyle k}$ gesuchte Einträge, so funktioniert der Algorithmus ebenfalls, allerdings gilt für die Anzahl ${\displaystyle r}$ durchzuführender Iterationen nun ${\displaystyle {\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{k}}}}$ statt ${\displaystyle {\tfrac {\pi }{4}}{\sqrt {N}}}$. Ist ${\displaystyle k}$ unbekannt, so führt man den Grover-Algorithmus in

${\displaystyle {\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{1}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{2}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{4}}},\;{\tfrac {\pi }{4}}{\sqrt {\tfrac {N}{8}}},\ldots }$

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

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

Optimalität des Grover-Algorithmus

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

Ebenso ist die Anzahl i. A. notwendiger Iterationen für ${\displaystyle k}$ gesuchte Einträge, also ${\displaystyle \pi {\sqrt {\tfrac {N}{2k}}}}$, optimal.

Qualitatives Argument

Um ein heuristisches Verständnis des quantenmechanischen Verfahrens im Vergleich zum klassischen Vorgehen zu gewinnen, und für Verallgemeinerungen, ist es sinnvoll den folgenden Spezialfall zu betrachten: die gesuchte Information soll auf einem spezifischen Gitterpunkt eines Quadratgitters liegen. Die Suche erfordert also klassisch ${\displaystyle N}$ Schritte, wenn ${\displaystyle {\sqrt {N}}}$ die Kantenlänge des Quadrates ist. Quantenmechanische Zustände sind dagegen Strahlen im Hilbertraum, d. h., sie sind nur bis auf einen Faktor bestimmt, und wenn man vom Zentrum des Quadrates ausgeht, ist die Richtung ${\displaystyle \theta }$ des Strahls durch eine Punktmenge gegeben, welche nur dem Umfang und nicht dem Inhalt des Quadrates entspricht, also einer Menge ${\displaystyle \sim {\mathcal {O}}\left({\sqrt {N}}\right)}$. Um einen speziellen Punkt auf dem gewählten Strahl zu finden, muss man nur noch Interferenzexperimente mit anderen quantenmechanischen Zuständen durchführen, was praktisch ohne zusätzlichen Zeitaufwand möglich ist. Die gesuchte Information erhält man also quantenmechanisch in ${\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}$ Schritten.

Verwandte Themen

Ein g​anz anderes Problem, b​ei dem Quantencomputer ebenfalls e​ine wesentliche Beschleunigung bringen, betrifft d​ie Faktorisierung e​iner sehr großen Zahl (siehe Shor-Algorithmus).

Literatur

• M. Homeister: Quantum Computing verstehen Springer Vieweg, Wiesbaden 2018, fünfte Auflage, ISBN 978-3-6582-2883-5, S. 137ff.
• B. Lenze: Mathematik und Quantum Computing Logos Verlag, Berlin 2020, zweite Auflage, ISBN 978-3-8325-4716-5, S. 57ff.
• R.J. Lipton, K.W. Regan: Quantum Algorithms via Linear Algebra: A Primer MIT Press, Cambridge MA 2014, ISBN 978-0-2620-2839-4, S. 115ff.
• M.A. Nielsen, I.L. Chuang: Quantum Computation and Quantum Information Cambridge University Press, Cambridge MA 2010, ISBN 978-1-1070-0217-3, S. 248ff.
• W. Scherer: Mathematik der Quanteninformatik Springer-Verlag, Berlin-Heidelberg 2016, ISBN 978-3-6624-9079-2, S. 235ff.
• C.P. Williams: Explorations in Quantum Computing Springer-Verlag, London 2011, zweite Auflage, ISBN 978-1-8462-8886-9, S. 245ff.

Weblinks

• Grover L.K.: From Schrödinger's equation to quantum search algorithm, American Journal of Physics, 69(7): 769-777, 2001. Überblick über den Algorithmus und seine Geschichte (englisch)
• Grover L.K.: QUANTUM COMPUTING: How the weird logic of the subatomic world could make it possible for machines to calculate millions of times faster than they do today The Sciences, July/August 1999, S. 24–30. (englisch)
• What's a Quantum Phone Book? (Memento vom 1. Februar 2014 im Internet Archive), Lov Grover, Bell Labs
• Quanten-Suchalgorithmen auf arxiv.org

Einzelnachweise

1. 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
2. Zwar ist mit dem Shor-Algorithmus ein polynomiell schneller probabilistischer Faktorisierungsalgorithmus für Quantencomputer bekannt, während kein bekannter klassischer Faktorisierungsalgorithmus polynomielle Laufzeit besitzt; allerdings gibt es bisher keinen mathematischen Beweis, dass nicht doch ein solcher Algorithmus existiert.
3. 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)