Grover-Algorithmus

Quantenalgorithmus

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[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 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 einfache Wiederholung des Algorithmus verkleinert werden kann.

AnwendungenBearbeiten

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 AblaufBearbeiten

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.

VoraussetzungenBearbeiten

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.

SchrittabfolgeBearbeiten

  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

 

ErweiterungenBearbeiten

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

Der Grover-Algorithmus ist optimal in dem Sinne, dass es keinen Quantenalgorithmus mit weniger als   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   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 ArgumentBearbeiten

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

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

LiteraturBearbeiten

  • 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.

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  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)