Der Algorithmus von Grover ist ein Quant-Algorithmus, für eine unsortierte Datenbank mit N Einträgen in O (N) Zeit zu suchen, und O zu verwenden (loggen Sie N) Abstellraum (sieh große O Notation). Es wurde von Lov Grover 1996 entdeckt.

In Modellen der klassischen Berechnung, eine unsortierte Datenbank suchend, kann in weniger nicht getan werden als geradlinige Zeit (so ist bloß das Durchsuchen jedes Artikels optimal). Der Algorithmus von Grover illustriert, dass in der Quant-Mustersuche schneller getan werden kann als das; tatsächlich ist seine Zeitkompliziertheit O (N) asymptotisch schnellstmöglich, für eine unsortierte Datenbank im Quant-Modell zu suchen. Es stellt eine quadratische Beschleunigung verschieden von anderen Quant-Algorithmen zur Verfügung, die Exponentialbeschleunigung über ihre klassischen Kollegen zur Verfügung stellen können. Jedoch ist sogar quadratische Beschleunigung beträchtlich, wenn N groß ist.

Wie viele Quant-Algorithmen ist der Algorithmus von Grover probabilistic im Sinn, dass es die richtige Antwort mit der hohen Wahrscheinlichkeit gibt. Die Wahrscheinlichkeit des Misserfolgs kann durch das Wiederholen des Algorithmus vermindert werden. (Ein Beispiel eines deterministischen Quant-Algorithmus ist der Deutsch-Jozsa Algorithmus, der immer die richtige Antwort erzeugt.)

Anwendungen

Obwohl der Zweck des Algorithmus von Grover gewöhnlich als "Suche einer Datenbank beschrieben wird" kann es genauer sein, es als das "Umkehren einer Funktion" zu beschreiben. Grob sprechend, wenn wir eine Funktion y=f (x) haben, der auf einem Quant-Computer bewertet werden kann, erlaubt dieser Algorithmus uns, x, wenn gegeben, y zu berechnen. Das Umkehren einer Funktion ist mit der Suche einer Datenbank verbunden, weil wir eine Funktion präsentieren konnten, die einen besonderen Wert von y erzeugt, wenn x einen gewünschten Zugang in einer Datenbank und einen anderen Wert von y für andere Werte von x vergleicht.

Der Algorithmus von Grover kann auch verwendet werden, für das bösartige und die Mittellinie von einer Reihe von Zahlen zu schätzen, und für das Kollisionsproblem zu beheben. Der Algorithmus kann weiter optimiert werden, wenn es mehr als einen zusammenpassenden Zugang gibt und die Zahl von Matchs im Voraus bekannt ist.

Einstellung

Denken Sie eine unsortierte Datenbank mit N Einträgen. Der Algorithmus verlangt einen Raum des Staates N-dimensional H, der durch n=log N qubits geliefert werden kann. Denken Sie das Problem, den Index der Datenbankeintragung zu bestimmen, die einen Suchbegriff befriedigt. Lassen Sie f die Funktion sein, die Datenbankeintragungen zu 0 oder 1 kartografisch darstellt, wo f (ω) = 1 wenn, und nur wenn ω den Suchbegriff befriedigt. Wir werden mit (Quant schwarzer Kasten) Zugang zu einem Unterprogramm in der Form eines einheitlichen Maschinenbedieners, U zur Verfügung gestellt, der als handelt:

:

:

Unsere Absicht ist, den Index zu identifizieren.

Algorithmus-Schritte

Die Schritte des Algorithmus von Grover werden wie folgt gegeben. Lassen Sie zeigen die gleichförmige Überlagerung über alle Staaten an

:.

Dann der Maschinenbediener

:

ist als der Verbreitungsmaschinenbediener von Grover bekannt.

Hier ist der Algorithmus:

::

1. Wenden Sie den Maschinenbediener an.

Wenden Sie den Maschinenbediener an.

</ol>

Die erste Wiederholung

Eine einleitende Beobachtung, in der Parallele mit unserer Definition

:

ist das U kann auf eine abwechselnde Weise ausgedrückt werden:

:.

Um das zu beweisen, genügt es, um zu überprüfen, wie U Basisstaaten folgt:

:.

: für alle.

Die folgende Berechnung zeigt, was in der ersten Wiederholung geschieht:

:.:.:.::.

Nach der Anwendung der zwei Maschinenbediener (und) der Umfang des gesuchten hat Element von dazu zugenommen.

Beschreibung dessen

Der Algorithmus von Grover verlangt einen "Quant Orakel" Maschinenbediener, der Lösungen des Suchproblems anerkennen und ihnen ein negatives Zeichen geben kann. Um den Suchalgorithmus allgemein zu halten, werden wir die innere Tätigkeit des Orakels als ein schwarzer Kasten verlassen, aber werden erklären, wie das Zeichen geschnipst wird. Das Orakel enthält eine Funktion, die zurückkehrt, wenn eine Lösung des Suchproblems und sonst ist. Das Orakel ist ein einheitlicher Maschinenbediener, der auf zwei quibits, der Index qubit und das Orakel qubit funktioniert:

:

Wie gewöhnlich, zeigt Hinzufügung modulo 2 an. Die Operation schnipst das Orakel qubit, wenn und es sonst allein lässt. Im Algorithmus von Grover wollen wir das Zeichen des Staates schnipsen, wenn es eine Lösung etikettiert. Das wird durch das Setzen des Orakels qubit im Staat erreicht, der dazu geschnipst wird, wenn eine Lösung ist:

:

Wir, betrachten wie geschnipst, so wird das Orakel qubit nicht geändert, so durch die Tagung wird das Orakel qubits gewöhnlich in der Spezifizierung des Algorithmus von Grover nicht erwähnt. So wird die Operation des Orakels einfach als geschrieben:

:

Geometrischer Beweis der Genauigkeit

Betrachten Sie das Flugzeug als abgemessen durch und, wo ein ket in der Subraumsenkrechte dazu ist. Wir werden die erste Wiederholung denken, der Initiale ket folgend. Seitdem ist einer der Basisvektoren im Übergreifen ist

:

Durch in geometrischen Begriffen, dem Winkel dazwischen und wird gegeben:

:

Der Maschinenbediener ist ein Nachdenken am Hyperflugzeug, das zu für Vektoren im Flugzeug orthogonal ist, das durch abgemessen ist und; d. h. es handelt als ein Nachdenken darüber. Der Maschinenbediener ist ein Nachdenken durch. Deshalb bleibt der Zustandvektor im Flugzeug, das durch und nach jeder Anwendung der Maschinenbediener abgemessen ist, und, und es ist aufrichtig, um zu überprüfen, dass der Maschinenbediener jedes Wiederholungsschritts von Grover den Zustandvektoren durch einen Winkel dessen rotieren lässt.

Wir müssen anhalten, wenn der Zustandvektor in der Nähe davon geht; danach lassen nachfolgende Wiederholungen den Zustandvektoren weg rotieren von, die Wahrscheinlichkeit reduzierend, die richtige Antwort zu erhalten. Die genaue Wahrscheinlichkeit, die richtige Antwort zu messen, ist:

:

wo r (ganze Zahl) Zahl von Wiederholungen von Grover ist.

Die frühste Zeit, dass wir ein nah-optimales Maß bekommen, ist deshalb.

Algebraischer Beweis der Genauigkeit

Um die algebraische Analyse zu vollenden, müssen wir herausfinden, was geschieht, wenn wir uns wiederholt wenden. Eine natürliche Weise zu tun ist das durch die eigenvalue Analyse einer Matrix. Bemerken Sie, dass während der kompletten Berechnung der Staat des Algorithmus eine geradlinige Kombination ist und. Wir können die Handlung und im Raum schreiben, der durch als abgemessen ist:

:

- 1 & 0 \\

2/\sqrt {N} & 1 \end {pmatrix }\\beginnen {pmatrix} \\b\end {pmatrix}. </Mathematik>

:

- 1 &-2/\sqrt {N} \\

0 & 1 \end {pmatrix }\\beginnt {pmatrix} \\b\end {pmatrix}. </Mathematik>

So in der Basis (der weder orthogonal ist noch eine Basis des ganzen Raums) wird die Handlung, gefolgt davon zu gelten, durch die Matrix gegeben

:

\begin {pmatrix }\

- 1 &-2/\sqrt {N} \\

0 & 1 \end {pmatrix }\

=

\begin {pmatrix }\

1 & 2/\sqrt {N} \\

- 2/\sqrt {N} & 1-4/N \end {pmatrix}. </Mathematik>

Diese Matrix hat zufällig eine sehr günstige Form von Jordan. Wenn wir definieren, ist es

: wo

Hieraus folgt dass die rth Macht der Matrix (entsprechend r Wiederholungen) ist

:

Mit dieser Form können wir trigonometrische Identität verwenden, um die Wahrscheinlichkeit zu schätzen, &omega zu beobachten; danach r Wiederholungen, die in der vorherigen Abteilung, erwähnt sind

:.

Wechselweise könnte man sich vernünftig vorstellen, dass eine nah-optimale Zeit, um zu unterscheiden, sein würde, wenn die Winkel 2rt und-2rt so einzeln weit sind wie möglich, der entspricht oder. Dann ist das System im Staat

:

Eine kurze Berechnung zeigt jetzt, dass die Beobachtung die richtige Antwort &omega nachgibt; mit dem Fehler O (1/N).

Erweiterung auf den Raum mit vielfachen Zielen

Wenn, statt 1 zusammenpassenden Zugangs, es k das Zusammenbringen von Einträgen, denselben Algorithmus-Arbeiten gibt, aber die Zahl von Wiederholungen muss &pi sein; (N/k)/4 statt

&pi;N/4.

Es gibt mehrere Weisen, den Fall zu behandeln, wenn k unbekannt ist. Zum Beispiel konnte man den Algorithmus von Grover mehrere Male mit führen

:

\pi \frac {(N/4) ^ {1/2}} {4}, \ldots </Mathematik>

Wiederholungen. Für jeden k wird eine von Wiederholungen einen zusammenpassenden Zugang mit einer genug hohen Wahrscheinlichkeit finden. Die Gesamtzahl von Wiederholungen ist am grössten Teil von

:

der noch O (N) ist. Es kann gezeigt werden, dass das verbessert werden konnte. Wenn die Zahl von gekennzeichneten Sachen k ist, wo k unbekannt ist, gibt es einen Algorithmus, der die Lösung in Abfragen findet. Diese Tatsache wird verwendet, um das Kollisionsproblem zu beheben.

Quant teilweise Suche

Eine Modifizierung des Algorithmus von Grover hat Quant genannt teilweise Suche wurde von Grover und Radhakrishnan 2004 beschrieben. In der teilweisen Suche interessiert man sich für die Entdeckung der genauen Adresse des Zielartikels, nur die ersten paar Ziffern der Adresse nicht. Gleichwertig können wir an "chunking" der Suchraum in Blöcke und dann das Fragen denken "in welcher Block ist der Zielartikel?". In vielen Anwendungen gibt solch eine Suche genug Information nach, wenn die Zieladresse die gewollte Information enthält. Zum Beispiel, um das von L.K. Grover angeführte Beispiel zu verwenden, wenn man eine Liste von durch die Klassenreihe organisierten Studenten hat, können wir uns nur dafür interessieren, ob ein Student in den niedrigeren 25 %, 25-50 %, 50-70-%- oder 75-100-%-Prozentanteil ist.

Um teilweise Suche zu beschreiben, betrachten wir eine Datenbank als getrennt in Blöcke, jede der Größe. Offensichtlich ist das teilweise Suchproblem leichter. Denken Sie die Annäherung, die wir klassisch nehmen würden - picken wir einen Block aufs Geratewohl auf, und führen dann eine normale Suche durch den Rest der Blöcke (auf der Mengenlehre-Sprache, dem Kompliment) durch. Wenn wir das Ziel nicht finden, dann wissen wir, dass es im Block ist, den wir nicht gesucht haben. Die durchschnittliche Zahl von Wiederholungen fällt von dazu.

Der Algorithmus von Grover verlangt Wiederholungen. Teilweise Suche wird durch einen numerischen Faktor schneller sein, der die Zahl von Blöcken abhängt. Teilweise Suche verwendet globale Wiederholungen und lokale Wiederholungen. Der globale Maschinenbediener von Grover wird benannt, und der lokale Maschinenbediener von Grover wird benannt.

Der globale Maschinenbediener von Grover handelt folgt den Blöcken. Im Wesentlichen wird es wie folgt gegeben:

1. Führen Sie Standard Wiederholungen von Grover auf der kompletten Datenbank durch.
2. Führen Sie lokale Wiederholungen von Grover durch. Eine lokale Wiederholung von Grover ist eine direkte Summe von Wiederholungen von Grover über jeden Block.
3. Führen Sie einen Standard Wiederholung von Grover durch

Die optimalen Werte dessen und werden im Vortrag von Grover und Radhakrishnan besprochen. Man könnte sich auch fragen, was geschieht, wenn man aufeinander folgende teilweise Suchen an verschiedenen Niveaus "der Entschlossenheit" anwendet. Diese Idee wurde im Detail von Korepin und Xu studiert, der sie binäre Quant-Suche genannt hat. Sie haben bewiesen, dass es nicht tatsächlich etwas schneller ist als das Durchführen einer einzelnen teilweisen Suche.

Optimality

Es ist bekannt, dass der Algorithmus von Grover optimal ist. D. h. jeder Algorithmus, der auf die Datenbank nur durch das Verwenden des Maschinenbedieners U zugreift, muss U mindestens so oft anwenden wie der Algorithmus von Grover. Dieses Ergebnis ist im Verstehen der Grenzen der Quant-Berechnung wichtig.

Wenn das Suchproblem von Grover mit dem Klotz N Anwendungen von U lösbar war, der andeuten würde, dass NP in BQP, durch das Umwandeln von Problemen in NP in Grover-Typ-Suchprobleme enthalten wird. Der optimality von

Der Algorithmus von Grover deutet an (aber erweist sich nicht), dass NP in BQP nicht enthalten wird.

Die Zahl von Wiederholungen für k das Zusammenbringen von Einträgen, &pi; (N/k)/4, ist auch optimal.

Siehe auch

• Umfang-Erweiterung
• Der Algorithmus von Shor

Referenzen

• Grover L.K.: Ein schnelles Quant mechanischer Algorithmus für die Datenbanksuche, die Verhandlungen, das 28. Jährliche ACM Symposium auf der Theorie der Computerwissenschaft, (Mai 1996) p. 212
• Grover L.K.: Von der Gleichung von Schrödinger bis Quant sucht Algorithmus, amerikanische Zeitschrift der Physik, 69 (7): 769-777, 2001. Pädagogische Rezension des Algorithmus und seiner Geschichte.
• Nielsen, M.A. und Chuang, Berechnung von I.L. Quantum und Quant-Information. Universität von Cambridge Presse, 2000. Kapitel 6.
• Was ist ein Quant-Telefonbuch? Lov Grover, Lucent Technologies
• Der Algorithmus von Grover: Quant-Datenbanksuche, C. Lavor, L.R.U. Manssur, R. Portugal
• Der Algorithmus von Grover auf arxiv.org