Grover-Algorithmus für eine Datenbanksuche: Wo liegt der Quantenvorteil?

8

Ich habe versucht zu verstehen, was der Vorteil der Verwendung des Grover-Algorithmus für die Suche in einer beliebigen ungeordneten Datenbank D (Schlüssel, Wert) mit N Werten anstelle einer klassischen Suche sein könnte.

Ich nahm an, dass die Orakelfunktion eine Funktion f (Taste) = y ist, wobei y der Index des entsprechenden Werts in der klassischen Datenbank ist.

Mein Problem hängt mit dem Orakel zusammen. Die Orakelschaltung muss für jede Suche in der Datenbank geändert werden, da der Schlüssel im Orakel angegeben ist. Nehmen wir an, dies ist der Einfachheit halber eine vernachlässigbare Operation.

Angenommen, die Orakelschaltung muss klassisch berechnet werden, müsste eine Schaltung erzeugt werden, die sich wie die Funktion f (Taste) = y verhält. Diese Funktion würde in mindestens O (N) Schritten erhalten (mit Ausnahme einiger Sonderfälle). Die Orakelfunktionsschaltung muss jedes Mal neu berechnet werden, wenn ein Datenbankeintrag geändert / hinzugefügt / entfernt wird, was O (N) kostet.

Viele Artikel wie Quantenalgorithmus-Implementierungen für Anfänger , Quantenalgorithmen für Matching und Netzwerkflüsse scheinen das Orakel überhaupt nicht zu berücksichtigen.

Ich weiß nicht, ob ich eine Quantendatenbank in Betracht ziehen muss, um einen echten Vorteil zu erzielen oder nicht ( dies und die Unzuverlässigkeit der Quantenergebnisse haben mich überzeugt, dass dies keine sehr gute Idee ist, aber es ist nur eine Vermutung).

Wo wird also die Komplexität für den Bau des Orakels betrachtet? Habe ich etwas falsch verstanden?

Ist "Die Orakelfunktionsschaltung muss jedes Mal neu berechnet werden, wenn ein Datenbankeintrag geändert / hinzugefügt / entfernt wird, mit Kosten von O (N)" eine falsche Annahme?

algorithm grovers-algorithm quantum-advantage Moreno G.
quelle

Warum sagen Sie, dass " die Orakel-Funktionsschaltung jedes Mal neu berechnet werden muss, wenn ein Datenbankeintrag geändert / hinzugefügt / entfernt wird "? Die Orakelfunktion müsste nur eine reversible Version der klassischen Schaltung sein, die prüft, ob ein bestimmter Schlüssel derjenige ist, den Sie suchen. Das Ändern der Anzahl der Schlüssel (dh der Elemente in der Datenbank) erfordert nicht, dass Sie die Struktur des Orakels ändern, genauso wie Sie nicht die klassische Funktion ändern müssen, die Sie für eine normale Suche verwenden würden

glS

Nun, das Problem ist mit "muss nur eine reversible Version der klassischen Schaltung sein". Wenn es eine triviale 1: 1-Entsprechung zwischen einem klassischen Algorithmus und einem Quantenalgorithmus gewesen wäre, gäbe es eine Art Compiler von einer klassischen Programmiersprache zu einer Quantenschaltung. Das Konvertieren von Dingen vom klassischen Algorithmus "wie er ist" in Quantenalgorithmen schien mir immer eine schlechte Idee zu sein, auch weil die meisten Operationen kaum skalierbar sind ( siehe nCNOT-Implementierung ).

Moreno G

In der Quantenschaltung haben Sie keinen Zugriff auf eine physikalische klassische Datenbank. Das "Quantencomputersystem" interagiert mit: - einer Schaltungsschemabeschreibung, die von (normalerweise) einem klassischen Programm als Eingabe gegeben wird; - Die Ergebnisse der Ausführung als Ausgabe. Während der Ausführung gibt es keinen Zugriff auf andere externe Ressourcen (ich bin nicht sicher, ob dies beabsichtigt oder aufgrund der Grenzen der tatsächlichen Technologie ist). Da das Orakel sowohl die Datenbank als auch den Schlüssel beschreibt, muss es geändert werden. Und dies ist oft eine nicht triviale Operation

Moreno G

2

Der Grover-Algorithmus hat beim Durchsuchen einer ungeordneten Datenbank keinen Vorteil, da das Codieren des Orakels in eine Schaltung $\tilde \Omega(n)$ -Operationen erfordert . Sie können dies mit einem einfachen Zählargument beweisen. Wenn die Schaltung die Größe $O(n^{0.99})$ hätte, gäbe es weniger verschiedene Schaltungen als verschiedene Orakel. Die tatsächliche Betriebskomplexität beträgt also $\tilde \Omega(n^{1.5})$ , obwohl die Abfragekomplexität $O(n^{0.5})$ beträgt .

Der Algorithmus von Grover hat nur dann einen Vorteil, wenn das, worüber Sie suchen, abstrakt ist, wie mögliche Lösungen für ein SAT-Problem, im Gegensatz dazu, dass es buchstäblich irgendwo in Hardware gespeichert ist, wie in einer Datenbank.

Craig Gidney
quelle

n

$n$

n

$n$

n

$n$

O (\log_{2} n)

$O(\log_2 n)$

2^{w 2^{n}}

$2^{w 2^n}$

n

$n$

w

$w$

n^{O (1)}

$n^{O(1)}$

W

$W$

(n^{O (1)})^{M} = 2^{(2^{n})}

$(n^{O(1)})^M = 2^{(2^n)}$

n

$n$ One-Hot-Orakel, um das Zählen zu vermeiden, müssen Sie die klassischen Daten als Teil des Aufbaus der Quantenschaltung durchlaufen. Ich denke, philosophisch gesehen lehne ich die Verwendung des RAM-Modells ab, wenn ich solche wild unterschiedlichen Computertypen vergleiche.

Craig Gidney

w

$w$

w

$w$

2^{w}

$2^w$

w

$w$

n

$n$

w

$w$

M

$M$

W

$W$

Zusammenfassend möchte ich sagen, dass es großartig wäre, wenn Sie diese Antwort erweitern könnten. Hier scheint es nützliche Informationen zu geben. Ist diese Art von Zählargument von irgendwoher? Ich habe es noch nie gesehen

glS

w 2^{w}

$w 2^w$

w

$w$

w

$w$

w

$w$

6

Sie erkennen zu Recht die Komplexität des Aufbaus des Orakels, um es bei Grovers Suche zu verwenden - es ist in der Tat der schwierige Teil bei der Lösung des Problems, und tatsächlich berücksichtigen viele Quellen diese Komplexität nicht.

Ich denke gerne an das Orakel als Werkzeug, um die Antwort zu erkennen, nicht um sie zu finden. Wenn Sie beispielsweise ein SAT-Problem lösen möchten , codiert die Orakelschaltung die Boolesche Formel für eine bestimmte Instanz eines Problems, das Sie lösen möchten. Die Schaltungsgröße hängt in diesem Fall von der Größe der Formel und nicht von der Größe des Suchraums ab. Ein Beispiel für die Implementierung eines Orakels für eine Instanz eines SAT-Problems finden Sie in meinem Tutorial .

Wenn Sie den Grover-Algorithmus für die Datenbanksuche verwenden würden, müsste das Orakel die gesuchte Bedingung, aber auch die Kriterien, ob sich das Element in einer Datenbank befindet, codieren. Wenn Sie beispielsweise nach einem Namen suchen, der mit A beginnt, muss das Orakel alle Zeichenfolgen erkennen, die mit A beginnen, aber es muss auch erkennen, welche der Zeichenfolgen in der Datenbank vorhanden sind. Andernfalls liefert der Algorithmus eine zufällige Zeichenfolge beginnend mit A, was wahrscheinlich nicht das ist, wonach Sie gesucht haben. (Dies war kein Problem mit dem SAT-Problembeispiel, da jede Variablenzuweisung, die der Formel entspricht, eine gültige Variablenzuweisung ist.)

Ich kenne kein gutes Beispiel für die Verwendung der Grover-Suche zum Durchsuchen einer unstrukturierten Datenbank. Nach meinem besten Verständnis eignet sich dieser Algorithmus für Suchen mit einer bestimmten Struktur. Es lohnt sich, andere Fragen zu Grover auf dieser Website zu prüfen, da viele von ihnen Orakelimplementierungen in Betracht ziehen.

Mariia Mykhailova
quelle

Ich habe einige Zweifel an der Existenz einer guten generischen Methode, um ein Orakel zu bauen, sonst würde ich erwarten, dass es zumindest dort eine Orakel-Implementierung gibt. In der Tat scheint die Verwendung des Grover-Algorithmus für die Suche in einer Datenbank eine schlechte Anwendung zu sein. Ich stimme voll und ganz der SAT-Lösungsanwendung zu. Sie passt viel besser zu dem, was der Grover-Algorithmus zulässt.

Moreno G

5

Das Problem liegt in Ihrer anfänglichen Annahme: Das Orakel für Grover basiert auf einer Funktion f (Wert) = 0/1, wobei 1 angibt, dass der Wert Ihren Suchkriterien entspricht, und 0 angibt, dass dies nicht der Fall ist. Dies bedeutet, dass Sie für jede Suche ein neues Orakel erstellen müssen, jedoch nicht für jede Datenbank.

Der Grover-Algorithmus und eine Quantendatenbank sind jedoch kein guter Ersatz für klassische Datenbank-Suchmethoden. In diesem Artikel werden die praktischen Aspekte des Grover-Algorithmus in diesem Zusammenhang erörtert.

Der Grover-Algorithmus hat praktische Anwendung, wenn er auf die Amplitudenverstärkung verallgemeinert wird , die sich als Bestandteil vieler anderer Quantenalgorithmen zeigt. Die Amplitudenverstärkung ist ein Weg, um die Erfolgswahrscheinlichkeit eines probabilistischen Quantenalgorithmus zu verbessern.

Alan Geller
quelle

"Obwohl der Grover-Algorithmus die Anforderung 2 im Prinzip erfüllt, kann es in vielen Fällen schwierig sein, ihn mit einem signifikanten Abstand auf der logarithmischen Skala zu erfüllen, da eine Implementierung der Orakelfunktion p (x) in kleinen Schaltkreisen möglicherweise nicht existiert oder eine unangemessene erfordert Anstrengung zu finden. ". Dies ist praktisch die gleiche Vermutung, die ich mir ausgedacht habe. Ich würde gerne wissen, ob die Datenbanksuche eine schlechte Anwendung für den Grover-Algorithmus ist oder nicht. Gibt es einen formellen Beweis dafür, was hier oben gesagt wird?

Moreno G.

Auch das ist nicht ganz richtig, diese Implementierung liefert das Ergebnis (könnte nützlich sein, wenn mehr als ein Element markiert ist)

Moreno G

1

Der Grover-Algorithmus ist ein (Quanten-) Schaltungs-SAT-Löser. Ich nehme an, es könnte auch ein buchstäblicher Black-Box-Löser sein, aber es würde nur mit Black-Boxen funktionieren, die Ihren verschränkten Eingabestatus nicht entschlüsseln, und ich habe Probleme zu glauben, dass solche Dinge existieren.

Ich weiß nicht, warum Grover oder sonst jemand es jemals als Datenbanksuchalgorithmus bezeichnet hat. Sie können ihm natürlich eine Schaltung geben, die einen festgelegten Mitgliedschaftstest implementiert, wobei einige der Eingaben fest mit dem Schlüssel verknüpft sind, den Sie suchen, und der Rest den Ausgabewert darstellt, und ihn als Datenbanksuche bezeichnen. Aber Sie könnten dasselbe mit einem klassischen SAT-Löser tun, und meines Wissens nennt sie niemand Datenbanksuchalgorithmen. Und damit Grover (oder klassische SAT-Löser) bei dieser Art von Problem wettbewerbsfähig ist, muss die "Datenbank" grundsätzlich nicht indizierbar sein, was bedeutet, dass sie zu groß ist, um indexierbar zu sein, was bedeutet, dass sie nirgendwo gespeichert ist, was sie ausmacht Meiner Meinung nach keine Datenbank (und keine Daten).

Das Finden einer effizienten Schaltung, die eine bestimmte Funktion implementiert, ist ein wichtiges und interessantes Problem, aber es ist auch unglaublich umfassend. es enthält viel von dem, was man Informatik nennt. Ich sehe nicht, was im Kontext von Grovers Algorithmus darüber gesagt werden kann, der in keinem anderen Kontext gleichermaßen gelten würde. Der Grover-Algorithmus nimmt nur eine optimierte Schaltung, sobald Sie sie gefunden haben, und wertet sie ungefähr √N-mal aus. Die Schaltung muss reversibel sein, was sie etwas anders macht als die üblichen klassischen Schaltungen, aber das hängt immer noch nicht direkt mit Grover zusammen.

Zusammenfassend denke ich, dass die Leute nicht darüber reden, die Orakelschaltung zu finden, weil sie nicht wirklich mit dem Quantenalgorithmus zusammenhängt (trotz des Titels von Grovers Artikel) und weil es ein so komplexes und weitreichendes Thema ist, dass keine Behandlung es gerecht werden könnte .

benrg
quelle

Grover-Algorithmus für eine Datenbanksuche: Wo liegt der Quantenvorteil?

Antworten: