imported>Nukelavee: /* growthexperiments-addlink-summary-summary:3|0|0 */

2024-11-13T09:34:01Z

growthexperiments-addlink-summary-summary:3|0|0

Neue Seite

Der '''Grover-Algorithmus''' ist ein [[Quantenalgorithmus]] zur Suche in einer un[[Sortierung|sortierten]] [[Datenbank]] mit <math>N</math> Einträgen in <math>\mathcal O\left(\sqrt{N}\right)</math> Schritten und mit <math>\mathcal O\left(\log N\right)</math> Speicherbedarf (siehe [[O-Notation]]). Er wurde von [[Lov Grover]] im Jahre [[1996]] veröffentlicht<ref name="GROVER-1996">{{Literatur |Autor=[[Lov Grover|L. K. Grover]] |Titel=A fast quantum mechanical algorithm for database search |Sammelwerk=Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC) |Datum=1996-05 |Seiten=212–219 |arXiv=quant-ph/9605043}}</ref> und gehört zu den ersten Quantenalgorithmen, für die bewiesen wurde, dass sie mit der Problemgröße besser skalieren als der beste klassische Algorithmus. Im Fall des Grover-Algorithmus handelt es sich um einen quadratischen Speedup.

Auf einem klassischen Computer ist der prinzipiell schnellstmögliche Suchalgorithmus in einer unsortierten Datenbank die [[lineare Suche]], die <math>\mathcal O\left(N\right)</math> Rechenschritte erfordert. Der Grover-Algorithmus liefert damit eine quadratische Beschleunigung, was für große <math>N</math> 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 wiederholte Ausführung des Algorithmus verkleinert werden kann.

== Anwendungen ==

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

Der Grover-Algorithmus kann ebenso zur Berechnung des [[Mittelwert]]s und des [[Median]]s einer Menge von Zahlen verwendet werden sowie zur Lösung des [[Kollisionsproblem]]s. Weiter kann er zur Lösung [[NP-vollständig]]er Probleme eingesetzt werden, indem er die Menge aller möglichen Probleme durchläuft. Obwohl damit NP-vollständige Probleme beträchtlich schneller gelöst werden können, ermöglicht auch der Grover-Algorithmus keine Lösung in [[P (Komplexitätsklasse)|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 Vorfeld bekannt ist.

=== Voraussetzungen ===

Gegeben sei eine unsortierte Datenbank mit <math>N</math> Einträgen, die in einem <math>N</math>-dimensionalen [[Quantenmechanischer Zustand|Zustandsraum]] <math>\mathcal{H}</math> durch <math>\log_2N</math> [[Qubit]]s dargestellt wird. Die Einträge seien mit <math>0, 1, \dots, (N-1)</math> durchnummeriert. Dann wählen wir eine auf <math>\mathcal{H}</math> wirkende [[Observable]] <math>\Omega</math> mit <math>N</math> verschiedenen [[Eigenzustand|Eigenzuständen]]

:<math>\left\{\left\vert 0\right\rang, \left\vert 1\right\rang, \cdots, \left\vert N-1\right\rang\right\}</math>

(in der [[Bra-Ket]]-Notation) und den zugehörigen [[Eigenwert]]en

:<math>\left\{\lambda_0, \lambda_1, \cdots, \lambda_{N-1} \right\}.</math>

Ferner sei ein [[unitärer Operator]] <math>U_\omega</math> gegeben, der eine [[Subroutine]], das sogenannte [[Orakel-Turingmaschine|Orakel]], darstellt, die die Datenbankeinträge [[P (Komplexitätsklasse)|effizient]] nach dem Suchkriterium vergleicht. Der Algorithmus legt nicht fest, wie das Orakel arbeitet, es muss allerdings die [[Superposition (Physik)|Superposition]] der Quantenzustände verarbeiten und den gesuchten Eigenzustand <math>\left\vert\omega\right\rang</math> erkennen:

:<math> U_\omega \left\vert\omega\right\rang = - \left\vert\omega\right\rang </math>
:<math> U_\omega \left\vert x\right\rang = \left\vert x\right\rang \qquad \forall x \ne \omega</math>

Ziel des Algorithmus ist es, diesen Eigenzustand <math>\left\vert\omega\right\rang</math>, bzw. äquivalent den Eigenwert <math>\lambda_\omega</math> zu identifizieren.

=== Schrittabfolge ===
#Initialisiere das System in den Zustand
#:<math>\left\vert s\right\rang = \frac{1}{\sqrt{N}} \sum_x \left\vert x\right\rang</math>
#Führe die folgende sog. Grover-Iteration <math>r(N)</math>-mal durch. (Die Funktion <math>r</math> wird weiter unten beschrieben.)
##Wende den Operator <math>U_\omega = I - 2 \left\vert \omega\right\rang\left\lang \omega\right\vert</math> an (erste [[Householdertransformation]]).
##Wende den Operator <math>U_s = -(I- 2 \left\vert s\right\rang \left\lang s\right\vert)</math> an (zweite [[Householdertransformation]]).
#Führe die [[Observable|Messung]] von <math>\Omega</math> durch. Das [[Messergebnis]] beträgt <math>\lambda_\omega</math> mit einer Wahrscheinlichkeit nahe <math>1</math>, falls <math>N\gg 1</math>. Mit der Messung von <math>\lambda_\omega</math> ist das System im Zustand <math>\omega</math>.

== Geometrische Sicht und Bestimmung der Schrittzahl ''r(N)'' ==
Der Anfangszustand lautet

:<math> |s\rang = \frac{1}{\sqrt{N}} \sum_x |x\rang. </math>

Betrachten wir die von <math>\left\vert s\right\rang</math> und <math>\left\vert\omega\right\rang</math> aufgespannte Ebene. Sei <math>\vert\omega^\times\rang</math> ein Ket-Vektor in dieser Ebene, senkrecht zu <math>\left\vert\omega\right\rang</math>. Da <math>\left\vert\omega\right\rang</math> einer der Basisvektoren ist, folgt

:<math> \lang\omega\mid s\rang = \frac{1}{\sqrt{N}} </math>

Geometrisch bedeutet das, dass <math>\left\vert\omega\right\rang</math> und <math>\left\vert s\right\rang</math> in einem Winkel von <math>\tfrac\pi 2 - \theta</math> zueinander stehen, wobei <math>\theta = \theta(N)</math> gegeben ist durch

:<math> \cos \left(\frac{\pi}{2} - \theta \right) = \frac{1}{\sqrt{N}} </math>

folglich ist
:<math> \sin \theta = \frac{1}{\sqrt{N}} </math>

Der Operator <math>U_\omega</math> ist eine [[Spiegelung (Geometrie)#Spiegelungen in Räumen beliebiger Dimension|Spiegelung]] an der zu <math>\left\vert\omega\right\rang</math> orthogonalen [[Hyperebene]]; für Vektoren in der von <math>\left\vert s\right\rang</math> und <math>\left\vert\omega\right\rang</math> aufgespannten Ebene wirkt er als Spiegelung an der Geraden durch <math>\vert\omega^\times\rang</math>. Der Operator <math>U_s</math> ist eine Spiegelung an der Geraden durch <math>\left\vert s\right\rang</math>. Der Zustandsvektor bleibt also nach der Anwendung von <math>U_s</math> und <math>U_\omega</math> in der durch <math>\left\vert s\right\rang</math> und <math>\left\vert\omega\right\rang</math> aufgespannten Ebene. Damit rotiert der Operator <math>U_s\ U_\omega</math> bei jedem Schritt der Grover-Iteration den Zustandsvektor um einen Winkel von <math>2\theta</math> nach <math>\left\vert\omega\right\rang</math>.

Der Algorithmus muss also anhalten, sobald der Zustandsvektor <math>\left\vert\omega\right\rang</math> 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 <math>r</math> an Iterationen zur exakten Übereinstimmung mit <math>\left\vert\omega\right\rang</math> gilt

:<math>\frac{\pi}{2} - \theta = 2 \theta r, </math>

also
:<math>r(N) = \frac{\pi}{4 \theta(N)} - \frac{1}{2} </math>

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

Für <math>N\gg 1</math> gilt <math>\theta\approx N^{-\frac 12}</math>, also
:<math>r(N) \longrightarrow \frac{\pi \sqrt N} 4</math>

== Erweiterungen ==

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

:<math> \tfrac\pi 4\sqrt\tfrac N1,\; \tfrac\pi 4\sqrt\tfrac N2,\; \tfrac\pi 4\sqrt\tfrac N4,\; \tfrac\pi 4\sqrt\tfrac N8, \ldots </math>

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

:<math> \pi \frac{\sqrt N}4 \left(1 + \frac{1}{\sqrt{2}} + \frac 12 + \cdots\right) = \mathcal O\left(\sqrt N\right)</math>

== Optimalität des Grover-Algorithmus ==
Der Grover-Algorithmus ist optimal in dem Sinne, dass es keinen Quantenalgorithmus mit weniger als <math>\mathcal O\left(\sqrt{N}\right)</math> Rechenschritten geben ''kann.''<ref name="BENNETT-ET-AL">{{Literatur|Autor=[[Charles H. Bennett (Physiker)|C. H. Bennett]], [[Gilles Brassard|G. Brassard]], [[Umesh Vazirani|Vazirani U.]]|Titel=''The strengths and weaknesses of quantum computation'' |Sammelwerk= SIAM Journal on Computing|Band= 26|Nummer=5 |Seiten= 1510–1523|Datum=1997|DOI=10.1137/s0097539796300933}}</ref> Dieses Resultat ist wichtig, um die Grenzen des Quantenrechnens zu verstehen.
Wäre das [[Suchproblem]] beispielsweise mit <math>\mathcal O\left(\log^c N\right)</math> Schritten lösbar, so wäre [[NP (Komplexitätsklasse)|NP]] in [[BQP]] enthalten.

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

== Qualitatives Argument ==
Um ein [[Heuristik|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 im schlimmsten Fall <math>N</math> Schritte, wenn <math>\sqrt N</math> 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 <math>\theta</math> des Strahls durch eine Punktmenge gegeben, welche nur dem Umfang und nicht dem Inhalt des Quadrates entspricht, also einer Menge <math>\sim \mathcal O\!\left(\sqrt N\right)</math>. 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 <math>\mathcal O\!\left(\sqrt N\right)</math> Schritten.

== Verwandte Themen ==
Ein ganz anderes Problem, bei dem [[Quantencomputer]] ebenfalls eine wesentliche Beschleunigung bringen, betrifft die Faktorisierung einer 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.
* [[Richard J. Lipton|R. J. Lipton]], [[Kenneth W. Regan|K. W. Regan]]: ''Quantum Algorithms via Linear Algebra: A Primer'' MIT Press, Cambridge MA 2014, ISBN 978-0-2620-2839-4, S. 115ff.
* {{Literatur|Autor=[[Michael Nielsen|M. A. Nielsen]], [[Isaac Chuang|I. L. Chuang]]|Titel=Quantum Computation and Quantum Information.|Verlag=Cambridge University Press|Ort=Cambridge MA|Datum=2010|ISBN=978-1-107-00217-3|Seiten= 248ff.|Online=https://profmcruz.files.wordpress.com/2017/08/quantum-computation-and-quantum-information-nielsen-chuang.pdf}}
* 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 ==
* L. K. Grover: ''[https://arxiv.org/abs/quant-ph/0109116 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)
* L. K. Grover: ''[https://cryptome.org/qc-grover.htm 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]'', In: ''The Sciences'', July/August 1999, S. 24–30. (englisch)
* {{Webarchiv | url=http://www.bell-labs.com/user/feature/archives/lkgrover/ | wayback=20140201230754 | text=''What's a Quantum Phone Book?''}}, Lov Grover, Bell Labs
* J. Marre: [https://www.quantencomputer-info.de/quantencomputer/grover-algorithmus/ ''Der Grover-Algorithmus und die Suche nach dem heiligen Gral''] In: quantencomputer-info veröffentlicht 11. September 2018
* ''Quanten-Suchalgorithmus'' In: {{Literatur|Autor=Norbert Linke, Markus Müller|Titel=Quantencomputer auf Basis von Ionen in Fallen. Mit Ionen ist zu rechnen |Sammelwerk= [[Physik in unserer Zeit]] |Datum=2020 |Seiten=162–173 |Online=https://onlinelibrary.wiley.com/doi/pdf/10.1002/piuz.202001571}}
* Reinhard Karnapke, Simon Rieche: ''Grover-Algorithmus'' In: [http://page.mi.fu-berlin.de/alt/vorlesungen/sem02/rieche-zsf.pdf ''Quantensuchalgorithmen''] S. 3–7 Seminarunterlagen Sommersemester 2002

== Einzelnachweise ==
<references/>

[[Kategorie:Suchalgorithmus]]
[[Kategorie:Quanteninformatik]]

Grover-Algorithmus - Versionsgeschichte

imported>Nukelavee: /* growthexperiments-addlink-summary-summary:3|0|0 */