www.wikidata.de-de.nina.az

Grover Algorithmus Der ist ein Quantenalgorithmus zur Suche in einer unsortierten Datenbank mit N displaystyle N Einträg

Grover-Algorithmus

Der Grover-Algorithmus ist ein Quantenalgorithmus zur Suche in einer unsortierten Datenbank mit Einträgen in Schritten und mit Speicherbedarf (siehe O-Notation). Er wurde von Lov Grover im Jahre 1996 veröffentlicht und gehört zu den ersten Quantenalgorithmen, für die bewiesen wurde, dass 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 Rechenschritte erfordert. Der Grover-Algorithmus liefert damit eine quadratische Beschleunigung, was für große 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 Bearbeiten

Der Grover-Algorithmus ermöglicht eigentlich nicht die direkte Suche in unsortierten Datenbanken, sondern die Umkehrung einer endlichen Funktion , denn zu einem gegebenen Wert entspricht ein Wert der Suche nach einem Wert im Definitionsbereich von .

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 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 Bearbeiten

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 Bearbeiten

Gegeben sei eine unsortierte Datenbank mit Einträgen, die in einem -dimensionalen Zustandsraum durch Qubits dargestellt wird. Die Einträge seien mit durchnummeriert. Dann wählen wir eine auf wirkende Observable mit verschiedenen Eigenzuständen

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

Ferner sei ein unitärer Operator 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:

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

Schrittabfolge Bearbeiten

  1. Initialisiere das System in den Zustand
  2. Führe die folgende sog. Grover-Iteration -mal durch. (Die Funktion wird weiter unten beschrieben.)
    1. Wende den Operator an (erste Householdertransformation).
    2. Wende den Operator an (zweite Householdertransformation).
  3. Führe die Messung von durch. Das Messergebnis beträgt mit einer Wahrscheinlichkeit nahe , falls . Mit der Messung von ist das System im Zustand .

Geometrische Sicht und Bestimmung der Schrittzahl r(N) Bearbeiten

Der Anfangszustand lautet

Betrachten wir die von und aufgespannte Ebene. Sei ein Ket-Vektor in dieser Ebene, senkrecht zu . Da einer der Basisvektoren ist, folgt

Geometrisch bedeutet das, dass und in einem Winkel von zueinander stehen, wobei gegeben ist durch

folglich ist

Der Operator ist eine Spiegelung an der zu orthogonalen Hyperebene; für Vektoren in der von und aufgespannten Ebene wirkt er als Spiegelung an der Geraden durch . Der Operator ist eine Spiegelung an der Geraden durch . Der Zustandsvektor bleibt also nach der Anwendung von und in der durch und aufgespannten Ebene. Damit rotiert der Operator bei jedem Schritt der Grover-Iteration den Zustandsvektor um einen Winkel von nach .

Der Algorithmus muss also anhalten, sobald der Zustandsvektor 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 an Iterationen zur exakten Übereinstimmung mit gilt

also

Da aber eine ganze Zahl sein muss, setzen wir gleich der gerundeten Zahl . Damit beträgt die Wahrscheinlichkeit, eine falsche Antwort zu messen, . Die Irrtumswahrscheinlichkeit bei Datenbankeinträgen lautet also asymptotisch , d. h., sie ist vernachlässigbar klein für große .

Für gilt , also

Erweiterungen Bearbeiten

Enthält die Datenbank nicht nur einen, sondern gesuchte Einträge, so funktioniert der Algorithmus ebenfalls, allerdings gilt für die Anzahl durchzuführender Iterationen nun statt . Ist unbekannt, so führt man den Grover-Algorithmus in

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

Optimalität des Grover-Algorithmus Bearbeiten

Der Grover-Algorithmus ist optimal in dem Sinne, dass es keinen Quantenalgorithmus mit weniger als Rechenschritten geben kann. Dieses Resultat ist wichtig, um die Grenzen des Quantenrechnens zu verstehen. Wäre das Suchproblem beispielsweise mit Schritten lösbar, so wäre NP in BQP enthalten.

Ebenso ist die Anzahl i. A. notwendiger Iterationen für gesuchte Einträge, also , optimal.

Qualitatives Argument Bearbeiten

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 im schmlimmsten Fall Schritte, wenn 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 des Strahls durch eine Punktmenge gegeben, welche nur dem Umfang und nicht dem Inhalt des Quadrates entspricht, also einer Menge . 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 Schritten.

Verwandte Themen Bearbeiten

Ein ganz anderes Problem, bei dem Quantencomputer ebenfalls eine wesentliche Beschleunigung bringen, betrifft die Faktorisierung einer sehr großen Zahl (siehe Shor-Algorithmus).

Literatur Bearbeiten

  • 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-107-00217-3, S. 248 ff. (wordpress.com [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 Bearbeiten

Einzelnachweise Bearbeiten

  1. L. K. Grover: A fast quantum mechanical algorithm for database search. In: Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC). Mai 1996, S. 212–219, arxiv:quant-ph/9605043.
  2. C. H. Bennett, G. Brassard, Vazirani U.: The strengths and weaknesses of quantum computation. In: SIAM Journal on Computing. Band 26, Nr. 5, 1997, S. 1510–1523, doi:10.1137/s0097539796300933.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Grover Algorithmus ist ein Quantenalgorithmus zur Suche in einer unsortierten Datenbank mit N displaystyle N Eintragen in O N displaystyle mathcal O left sqrt N right Schritten und mit O log N displaystyle mathcal O left log N right Speicherbedarf siehe O Notation Er wurde von Lov Grover im Jahre 1996 veroffentlicht 1 und gehort zu den ersten Quantenalgorithmen fur die bewiesen wurde dass mit der Problemgrosse 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 schnellstmogliche Suchalgorithmus in einer unsortierten Datenbank die lineare Suche die O N displaystyle mathcal O left N right Rechenschritte erfordert Der Grover Algorithmus liefert damit eine quadratische Beschleunigung was fur grosse N displaystyle N betrachtlich 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 Ausfuhrung des Algorithmus verkleinert werden kann Inhaltsverzeichnis 1 Anwendungen 2 Detaillierter Ablauf 2 1 Voraussetzungen 2 2 Schrittabfolge 3 Geometrische Sicht und Bestimmung der Schrittzahl r N 4 Erweiterungen 5 Optimalitat des Grover Algorithmus 6 Qualitatives Argument 7 Verwandte Themen 8 Literatur 9 Weblinks 10 EinzelnachweiseAnwendungen BearbeitenDer Grover Algorithmus ermoglicht eigentlich nicht die direkte Suche in unsortierten Datenbanken sondern die Umkehrung einer endlichen Funktion y f x displaystyle y f x nbsp denn zu einem gegebenen Wert y displaystyle y nbsp entspricht ein Wert x f 1 y displaystyle x f 1 y nbsp der Suche nach einem Wert x displaystyle x nbsp im Definitionsbereich von f displaystyle f nbsp Der Grover Algorithmus kann ebenso zur Berechnung des Mittelwerts und des Medians einer Menge von Zahlen verwendet werden sowie zur Losung des Kollisionsproblems Weiter kann er zur Losung NP vollstandiger Probleme eingesetzt werden indem er die Menge aller moglichen Probleme durchlauft Obwohl damit NP vollstandige Probleme betrachtlich schneller gelost werden konnen ermoglicht auch der Grover Algorithmus keine Losung in polynomialer Zeitkomplexitat Detaillierter Ablauf BearbeitenDer folgende Ablauf des Algorithmus bezieht sich auf die Suche nach einem einzelnen Sucheintrag Der Algorithmus kann weiter optimiert werden um einen von mehreren moglichen Eintragen zu finden wobei deren Anzahl im Vorfeld bekannt ist Voraussetzungen Bearbeiten Gegeben sei eine unsortierte Datenbank mit N displaystyle N nbsp Eintragen die in einem N displaystyle N nbsp dimensionalen Zustandsraum H displaystyle mathcal H nbsp durch log 2 N displaystyle log 2 N nbsp Qubits dargestellt wird Die Eintrage seien mit 0 1 N 1 displaystyle 0 1 dots N 1 nbsp durchnummeriert Dann wahlen wir eine auf H displaystyle mathcal H nbsp wirkende Observable W displaystyle Omega nbsp mit N displaystyle N nbsp verschiedenen Eigenzustanden 0 1 N 1 displaystyle left left vert 0 right rangle left vert 1 right rangle cdots left vert N 1 right rangle right nbsp in der Bra Ket Notation und den zugehorigen Eigenwerten l 0 l 1 l N 1 displaystyle left lambda 0 lambda 1 cdots lambda N 1 right nbsp Ferner sei ein unitarer Operator U w displaystyle U omega nbsp gegeben der eine Subroutine das sogenannte Orakel darstellt die die Datenbankeintrage effizient nach dem Suchkriterium vergleicht Der Algorithmus legt nicht fest wie das Orakel arbeitet es muss allerdings die Superposition der Quantenzustande verarbeiten und den gesuchten Eigenzustand w displaystyle left vert omega right rangle nbsp erkennen U w w w displaystyle U omega left vert omega right rangle left vert omega right rangle nbsp U w x x x w displaystyle U omega left vert x right rangle left vert x right rangle qquad forall x neq omega nbsp Ziel des Algorithmus ist es diesen Eigenzustand w displaystyle left vert omega right rangle nbsp bzw aquivalent den Eigenwert w displaystyle omega nbsp zu identifizieren Schrittabfolge Bearbeiten Initialisiere das System in den Zustand s 1 N x x displaystyle left vert s right rangle frac 1 sqrt N sum x left vert x right rangle nbsp Fuhre die folgende sog Grover Iteration r N displaystyle r N nbsp mal durch Die Funktion r displaystyle r nbsp wird weiter unten beschrieben Wende den Operator U w I 2 w w displaystyle U omega I 2 left vert omega right rangle left langle omega right vert nbsp an erste Householdertransformation Wende den Operator U s I 2 s s displaystyle U s I 2 left vert s right rangle left langle s right vert nbsp an zweite Householdertransformation Fuhre die Messung von W displaystyle Omega nbsp durch Das Messergebnis betragt l w displaystyle lambda omega nbsp mit einer Wahrscheinlichkeit nahe 1 displaystyle 1 nbsp falls N 1 displaystyle N gg 1 nbsp Mit der Messung von l w displaystyle lambda omega nbsp ist das System im Zustand w displaystyle omega nbsp Geometrische Sicht und Bestimmung der Schrittzahl r N BearbeitenDer Anfangszustand lautet s 1 N x x displaystyle s rangle frac 1 sqrt N sum x x rangle nbsp Betrachten wir die von s displaystyle left vert s right rangle nbsp und w displaystyle left vert omega right rangle nbsp aufgespannte Ebene Sei w displaystyle vert omega times rangle nbsp ein Ket Vektor in dieser Ebene senkrecht zu w displaystyle left vert omega right rangle nbsp Da w displaystyle left vert omega right rangle nbsp einer der Basisvektoren ist folgt w s 1 N displaystyle langle omega mid s rangle frac 1 sqrt N nbsp Geometrisch bedeutet das dass w displaystyle left vert omega right rangle nbsp und s displaystyle left vert s right rangle nbsp in einem Winkel von p 2 8 displaystyle tfrac pi 2 theta nbsp zueinander stehen wobei 8 8 N displaystyle theta theta N nbsp gegeben ist durch cos p 2 8 1 N displaystyle cos left frac pi 2 theta right frac 1 sqrt N nbsp folglich ist sin 8 1 N displaystyle sin theta frac 1 sqrt N nbsp Der Operator U w displaystyle U omega nbsp ist eine Spiegelung an der zu w displaystyle left vert omega right rangle nbsp orthogonalen Hyperebene fur Vektoren in der von s displaystyle left vert s right rangle nbsp und w displaystyle left vert omega right rangle nbsp aufgespannten Ebene wirkt er als Spiegelung an der Geraden durch w displaystyle vert omega times rangle nbsp Der Operator U s displaystyle U s nbsp ist eine Spiegelung an der Geraden durch s displaystyle left vert s right rangle nbsp Der Zustandsvektor bleibt also nach der Anwendung von U s displaystyle U s nbsp und U w displaystyle U omega nbsp in der durch s displaystyle left vert s right rangle nbsp und w displaystyle left vert omega right rangle nbsp aufgespannten Ebene Damit rotiert der Operator U s U w displaystyle U s U omega nbsp bei jedem Schritt der Grover Iteration den Zustandsvektor um einen Winkel von 2 8 displaystyle 2 theta nbsp nach w displaystyle left vert omega right rangle nbsp Der Algorithmus muss also anhalten sobald der Zustandsvektor w displaystyle left vert omega right rangle nbsp am nachsten gekommen ist Weitere Iterationen wurden ihn wieder davon weg drehen und damit die Wahrscheinlichkeit der korrekten Antwort wieder verkleinern Fur die optimale Anzahl r displaystyle r nbsp an Iterationen zur exakten Ubereinstimmung mit w displaystyle left vert omega right rangle nbsp gilt p 2 8 2 8 r displaystyle frac pi 2 theta 2 theta r nbsp also r N p 4 8 N 1 2 displaystyle r N frac pi 4 theta N frac 1 2 nbsp Da r displaystyle r nbsp aber eine ganze Zahl sein muss setzen wir r displaystyle r nbsp gleich der gerundeten Zahl p 4 8 1 2 displaystyle tfrac pi 4 theta tfrac 1 2 nbsp Damit betragt die Wahrscheinlichkeit eine falsche Antwort zu messen O 1 cos 2 8 O sin 2 8 displaystyle mathcal O left 1 cos 2 theta right mathcal O left sin 2 theta right nbsp Die Irrtumswahrscheinlichkeit bei N displaystyle N nbsp Datenbankeintragen lautet also asymptotisch O 1 N displaystyle mathcal O left tfrac 1 N right nbsp d h sie ist vernachlassigbar klein fur grosse N displaystyle N nbsp Fur N 1 displaystyle N gg 1 nbsp gilt 8 N 1 2 displaystyle theta approx N frac 1 2 nbsp also r N p N 4 displaystyle r N longrightarrow frac pi sqrt N 4 nbsp Erweiterungen BearbeitenEnthalt die Datenbank nicht nur einen sondern k displaystyle k nbsp gesuchte Eintrage so funktioniert der Algorithmus ebenfalls allerdings gilt fur die Anzahl r displaystyle r nbsp durchzufuhrender Iterationen nun p 4 N k displaystyle tfrac pi 4 sqrt tfrac N k nbsp statt p 4 N displaystyle tfrac pi 4 sqrt N nbsp Ist k displaystyle k nbsp unbekannt so fuhrt man den Grover Algorithmus in p 4 N 1 p 4 N 2 p 4 N 4 p 4 N 8 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 nbsp Iterationen durch Fur beliebiges k displaystyle k nbsp wird ein gesuchter Eintrag mit genugend hoher Wahrscheinlichkeit gefunden Die Gesamtzahl von Iterationen betragt hochstens p N 4 1 1 2 1 2 O N displaystyle pi frac sqrt N 4 left 1 frac 1 sqrt 2 frac 1 2 cdots right mathcal O left sqrt N right nbsp Optimalitat des Grover Algorithmus BearbeitenDer Grover Algorithmus ist optimal in dem Sinne dass es keinen Quantenalgorithmus mit weniger als O N displaystyle mathcal O left sqrt N right nbsp Rechenschritten geben kann 2 Dieses Resultat ist wichtig um die Grenzen des Quantenrechnens zu verstehen Ware das Suchproblem beispielsweise mit O log c N displaystyle mathcal O left log c N right nbsp Schritten losbar so ware NP in BQP enthalten Ebenso ist die Anzahl i A notwendiger Iterationen fur k displaystyle k nbsp gesuchte Eintrage also p N 2 k displaystyle pi sqrt tfrac N 2k nbsp optimal Qualitatives Argument BearbeitenUm ein heuristisches Verstandnis des quantenmechanischen Verfahrens im Vergleich zum klassischen Vorgehen zu gewinnen und fur 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 schmlimmsten Fall N displaystyle N nbsp Schritte wenn N displaystyle sqrt N nbsp die Kantenlange des Quadrates ist Quantenmechanische Zustande 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 8 displaystyle theta nbsp des Strahls durch eine Punktmenge gegeben welche nur dem Umfang und nicht dem Inhalt des Quadrates entspricht also einer Menge O N displaystyle sim mathcal O left sqrt N right nbsp Um einen speziellen Punkt auf dem gewahlten Strahl zu finden muss man nur noch Interferenzexperimente mit anderen quantenmechanischen Zustanden durchfuhren was praktisch ohne zusatzlichen Zeitaufwand moglich ist Die gesuchte Information erhalt man also quantenmechanisch in O N displaystyle mathcal O left sqrt N right nbsp Schritten Verwandte Themen BearbeitenEin ganz anderes Problem bei dem Quantencomputer ebenfalls eine wesentliche Beschleunigung bringen betrifft die Faktorisierung einer sehr grossen Zahl siehe Shor Algorithmus Literatur BearbeitenM Homeister Quantum Computing verstehen Springer Vieweg Wiesbaden 2018 funfte 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 107 00217 3 S 248 ff wordpress com 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 BearbeitenL K Grover From Schrodinger s equation to quantum search algorithm American Journal of Physics 69 7 769 777 2001 Uberblick uber den Algorithmus und seine Geschichte englisch L K Grover 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 J Marre Der Grover Algorithmus und die Suche nach dem heiligen Gral In quantencomputer info veroffentlicht 11 September 2018Einzelnachweise Bearbeiten L K Grover A fast quantum mechanical algorithm for database search In Proceedings 28th Annual ACM Symposium on the Theory of Computing STOC Mai 1996 S 212 219 arxiv quant ph 9605043 C H Bennett G Brassard Vazirani U The strengths and weaknesses of quantum computation In SIAM Journal on Computing Band 26 Nr 5 1997 S 1510 1523 doi 10 1137 s0097539796300933 Abgerufen von https de wikipedia org w index php title Grover Algorithmus amp oldid 239486731