Der Algorithmus von Grover wird unter anderem verwendet, um einen Artikel in einer ungeordneten Liste von Artikeln zu suchen der Länge . Auch wenn es hier viele Fragen zu diesem Thema gibt, vermisse ich den Punkt. $\mathbf{y}$ $[\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}]$ $n$

Auf klassische Weise in einer Liste suchen

Normalerweise würde ich eine Suchfunktion auf diese Weise entwerfen. Also gebe ich die Liste und den gewünschten Gegenstand als Eingabe an und erhalte die Position des Elements in der Liste als Ausgabe. Ich glaube, ich habe verstanden, dass die Informationen über durch das Orakeltor in den Algorithmus eingebettet sind , sodass unsere Funktion zu Lassen Sie uns ein make praktisches Beispiel. Betrachten Sie die Suche nach dem Pik-As Pik-

s e a r c h ([x_{0}, x_{1}, . . ., x_{n - 1}], y) = i \in N such that x_{i} = y

$\mathrm{search}([\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}], \mathbf{y}) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y}$

y

$\mathbf{y}$

O

$O$

{s e a r c h}_{y} ([x_{1}, x_{2}, . . ., x_{n}]) = i \in N such that x_{i} = y

$\mathrm{search}_\mathbf{y}([\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n] ) = i \in \mathbb{N} \quad \text{such that } \mathbf{x}_i = \mathbf{y}$

1 ♠

$1\spadesuit$ in einer Folge von 8 Karten aus einem Standardstapel mit 52 Karten :

Die Liste der Länge ist . $8$ $[ \mathbf{x}_0 = J\clubsuit,$ $\mathbf{x}_1 = 10\diamondsuit,$ $\mathbf{x}_2 = 4\heartsuit,$ $\mathbf{x}_3 = Q\clubsuit,$ $\mathbf{x}_4 = 3\spadesuit,$ $\mathbf{x}_5 = 1\spadesuit,$ $\mathbf{x}_6 = 6\spadesuit,$ $\mathbf{x}_7 = 6\clubsuit]$

Das gesuchte Element ist . Ich sollte . Jede Karte kann mit Bits codiert werden. Die Liste enthält Elemente. Wir benötigen also Bits, um die Liste zu codieren. In diesem Fall implementiert das Orakel die Funktion: $\mathbf{x}_5$ $\mathrm{search}_{\spadesuit}(cards) = 5$ $\lceil{\log_2 52}\rceil = 6$ $8$ $6\times 8 = 48$ $O$

f (x) = {\begin{cases} 1, & x = 1 ♠ \\ 0, & otherwise \end{cases}

$f(\mathbf{x}) = \begin{cases} 1, & \mathbf{x} = 1\spadesuit \\ 0, & \text{otherwise} \end{cases}$

Die Eingabe von Grovers Algorithmus ist jedoch kein Zustand von Qubits. $48$

(NB: Das Bild des gemischten Decks ist hier zu sehen. )

Grover und sein Orakel

Mehrere Quellen (z. B. hier - grafisch erklärt) sagen, dass die Eingabe des Algorithmus unterschiedlich ist: Die Eingabe ist ein aus dem Suchraum entnommener Zustand wobei die Anzahl der Elemente der Liste ist. Jede Zahl entspricht der Position eines Elements in der Liste. $S = \{ 0, 1, 2, ..., N \} = \{0, 1, 2, ..., 7 \}$ $N$

Die Eingabe von ist nun ein Qubit-Vektor , der eine Überlagerung aller Elemente im Suchraum sein muss . $\mathrm{search}_{\spadesuit}(\cdot)$ $\lceil \log_2 8 \rceil = 3$ $|\psi\rangle$ $S$

Wir wissen

$|0_{3\text{qubits}}\rangle = |000\rangle$ entspricht ; $J\clubsuit$
$|1_{3\text{qubits}}\rangle = |001\rangle$ entspricht ; $10\diamondsuit$
$|2_{3\text{qubits}}\rangle = |010\rangle$ entspricht ; $4\heartsuit$
$|5_{3\text{qubits}}\rangle = |101\rangle$ entspricht welches das gewünschte Element ist; $1\spadesuit$
und so weiter...

In diesem Fall haben wir Aber in diesem Fall müsste unser Orakel die Funktion implementieren.

{s e a r c h}_{♠} (| ψ ⟩) = | 5_{3 qubits} ⟩

$\mathrm{search}_{\spadesuit}(|\psi\rangle) = |5_{3\text{qubits}}\rangle$

f (| ψ ⟩) = {\begin{cases} 1, & | ψ ⟩ = | 5_{3 qubits} ⟩ \\ 0, & otherwise \end{cases}

$f(|\psi\rangle) = \begin{cases} 1, & |\psi\rangle = |5_{3\text{qubits}}\rangle \\ 0, & \text{otherwise} \end{cases}$

Um das Orakel zu bauen, müssen wir wissen, dass an Position 5 ist. Wozu dient der Algorithmus, wenn wir bereits nach dem Element gesucht haben, um das Orakel zu bauen? $\spadesuit$

grovers-algorithm einschließen
quelle

Ich habe auch Schwierigkeiten, den Vorteil von Grovers Algorithmus zu verstehen. Angenommen, ich habe N Elemente in der Liste. Wurden bei jedem Aufruf von Oracle alle N Möglichkeiten bewertet? Auch wenn die Evaluierung sehr schnell ist, wir aber dennoch alle Konfigurationen durchlaufen müssen, ist die Komplexität der Oracle-Evaluierung O (N). Der Algorithmus des Grovers scheint also nicht schneller zu sein als eine blöde Suche. Ist das richtig?

Sanparith Marukatat

@ SanparithMarukatat Es ist nicht richtig. Die Elemente Ihrer Liste sind die Begriffe der Überlagerung des Staates, der an der Suche beteiligt ist. Wenn das Oracle in diesem Zustand arbeitet, zählt es als eine einzelne Operation. Die Fähigkeit des Orakels, den gesuchten Begriff Ihrer Überlagerung zu markieren, ist ein grundlegender Teil von Grovers Einsicht. Um den Algorithmus von Grover zu verstehen, empfehle ich Ihnen zunächst zu verstehen, wie diese Markierung des gewünschten Zustands erfolgt. Danach müssen Sie die Rolle des Staates verstehen

im Oracle.

| - ⟩

$|- \rangle$

R. Chopin

Wenn Sie das verstehen, sollten Sie den Operator untersuchen, der in der Lage ist, die Amplitude des gewünschten Terms in der Überlagerung zu erhöhen und gleichzeitig die Amplitude der unerwünschten Terme der Überlagerung zu verringern. Für mich ist der einfachste Weg, sich Grovers zu nähern, den invers-about-mean-Operator zu betrachten. (Einige Leute nehmen die geometrische Ansicht, aber ich finde es nicht so klar.)

R. Chopin

10

Wenn Sie 8 Elemente in der Liste haben (wie im Beispiel Ihrer Karte), beträgt die Eingabe des Orakels 3 (qu) Bits. Die Anzahl der Karten im Deck (52) spielt keine Rolle, Sie benötigen nur 3 Bits, um 8 Karten zu codieren.

Sie können sich vorstellen, dass 3 Bits die Position in der Liste der gesuchten Karte codieren. dann kennst du die Position nicht, aber das Orakel weiß es. Wenn Sie also das Pik-Ass suchen, dann weiß das Orakel, dass das Pik-Ass die sechste Karte ist (oder die fünfte von Null an) und implementiert die Funktion

f (x) = {\begin{cases} 1, & if x = 5, or binary '101' \\ 0, & otherwise \end{cases}

$f(\mathbf{x}) = \begin{cases} 1, & \text{if x = 5, or binary '101'} \\ 0, & \text{otherwise} \end{cases}$

PS: Es ist besser, den Algorithmus des Grovers anders zu betrachten: Sie haben ein Orakel, das eine Boolesche Funktion implementiert, die für eine einzelne Kombination von Eingabebits ausgibt, andernfalls null ausgibt, und Ihre Aufgabe ist es, die Kombination zu finden. Das Problem ist genauso komplex wie die Suche in einer unsortierten Liste oder Datenbank. Deshalb wird der Algorithmus des Grovers normalerweise als Suche in einer unsortierten Datenbank beschrieben. Die Anwendung des Algorithmus auf eine reale Datenbanksuche wirft jedoch Fragen auf, die über den eigentlichen Algorithmus hinausgehen. Grovers Algorithmus sucht nur nach dem, was das Orakel weiß. $1$

kludg
quelle

Ja, sorry, diese 6 war von einer vorherigen Bearbeitung

einschließlich

2

Vielen Dank für Ihre Antwort. Ich habe die falsche Schreibweise korrigiert. Was nützt es, den Algorithmus auszuführen, wenn ich zum Aufbau des Orakels die Position des gesuchten Elements kennen muss?

Einbeziehung des

1

@incud In der Tat macht es keinen Sinn. Ich habe die Antwort aktualisiert.

kludg

" Grovers Algorithmus sucht nur nach dem, was das Orakel weiß ": nicht unbedingt. Das Orakel prüft möglicherweise nur auf bestimmte Eigenschaften der Eingabe, sodass das Ergebnis, das am Ende angezeigt wird, mehr Informationen enthält als das, das im Orakel selbst codiert ist. Ein typisches Beispiel ist die Suche in einem Telefonbuch. Das Orakel "fragt" nach einem Datensatz, der an einen bestimmten Namen angehängt ist, aber sobald der richtige Datensatz gefunden ist, erhält man auch die zusätzlichen Informationen der Telefonnummer, die an diesen Datensatz angehängt ist und die im Orakel überhaupt nicht verschlüsselt wurde

glS

4

$x$ $x$ entspricht und prüft dann, ob diese Karte die markierte Karte ist. Die Idee ist, dass jedes Mal, wenn Sie das Orakel anrufen, dieser Prozess einmal durchlaufen wird. Insgesamt bewerten Sie die Funktion so oft, wie Sie das Orakel anrufen. Das Ziel eines Suchalgorithmus ist es, dieses Orakel so selten wie möglich aufzurufen.

$x$ $x$

Die wichtigsten Unterschiede in Ihrem Beispiel im Vergleich zu einem realistischeren Nutzungsszenario sind:

Der Suchraum ist normalerweise sehr groß. Es gibt keine realistische Aussicht, alle Werte vorab zu berechnen. Genau das versuchen wir zu vermeiden.
$f(x)$ $x$

$x$ $y=f(x)$ $y=1$ $x$ $f(x)$ $x_0$

DaftWullie
quelle

2

Die Frage ist letztendlich: "Was bringt es, den Algorithmus auszuführen, wenn wir bereits nach dem Element gesucht haben, um das Orakel zu bauen?"

Während jemand das Orakel vorgefertigt hat, war es möglicherweise nicht die Person, die das Orakel benutzt.

Der Algorithmus von Grover erfordert, dass das Orakel nicht öfter als abgefragt wird $\sqrt{\text{size of list}}$

Wir fragen das Orakel: Was ist die Antwort auf die Frage, die es bereits hat? Sogar Mateus und Omar würden das "Orakel für ein bestimmtes Alphabet-Symbol" während der Laufzeit fragen, an welcher Stelle (n) sich das Symbol in der Zeichenfolge befindet, die es bereits kompiliert hat. Das Orakel gibt die Antwort auf unsere Frage nach nur einer Konsultation, aber in dieser Geschichte kann es beispielsweise die Antwort nicht einfach als Binärzeichenfolge ausschreiben und über einen klassischen Kommunikationskanal an uns senden. Es wird seine Antwort in einer Überlagerung verbergen, damit wir es herausziehen können.

Ich lasse Phantasie oder Metapher in diesem nächsten Teil davonlaufen: Wir hören die Antwort nicht ganz beim ersten Mal, und wir müssen das Orakel bitten, die gleiche Antwort immer wieder zu wiederholen, bis wir sicher sind, was das Orakel gesagt hat. außer wir fangen an, durch Fehlinformationen im Diffusionsprozess zu halluzinieren, wenn wir zu oft fragen.

Brendan M
quelle

2

Angesichts des von Ihnen angegebenen Orakels ist die Suche in der Tat sinnlos. Dieses Orakel verfehlt jedoch den Punkt von Grovers Algorithmus, da das Suchen nach einer Karte in einem Kartenspiel keine unstrukturierte Suche ist, da Sie, wie Sie sagten, die Reihenfolge bereits kennen. Ergo ist Ihre Suche strukturiert. Der Grund, warum dieses Orakel verwendet wird, ist, dass es demonstriert, wie Grovers angewendet werden kann, ohne dass ein Orakel besprochen werden muss, das Grovers nützlich machen würde, da ein solches Orakel komplizierter als wertvoll wäre. Daher könnte ein besseres Orakel, um die Nützlichkeit von Grovers zu demonstrieren, etwa so aussehen:

f (x) = {\begin{cases} 1, & x [0, \dots, 3] + x [4, \dots, 7] = 1010 \\ 0, & otherwise \end{cases}

$f(x) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & \text{otherwise} \end{cases}$

Was dieses Orakel impliziert ist, dass Sie eine 8-Qubit-Suche haben, bei der Sie die ersten vier Qubits nehmen und zu den zweiten vier Qubits addieren und M umdrehen, wenn die Addition 10 ergibt (1010 in binär). Der Unterschied zwischen diesem und dem von Ihnen bereitgestellten Orakel besteht darin, dass dieses Orakel ein Muster testet (addieren Sie die Operanden zu 10), während Ihr Orakel die Gleichheit testet (ist dieser Index 5). Dieses Orakel ist viel schwieriger zu bauen, nutzt aber die wahre Kraft von Grover, die im Wesentlichen eine Brute-Force-Suche ist, bei der Ihr Orakel den Suchraum definiert.

Woody1193
quelle

Grovers Algorithmus: Wo ist die Liste?

Auf klassische Weise in einer Liste suchen

Grover und sein Orakel

Antworten: