Welche Anwendungen hat der Suchalgorithmus von Grover?

Abgesehen von denen, die Sie erwähnt haben, ist eine andere mir bekannte Anwendung des (modifizierten) Algorithmus von Grover die Lösung des Kollisionsproblems in der Komplexitätstheorie, im Quantencomputing und in der Rechenmathematik . Es wird auch als BHT-Algorithmus bezeichnet .

Einleitung :

Das Kollisionsproblem bezieht sich meist auf die 2-zu-1-Version, die Scott Aaronson in seiner Doktorarbeit beschrieben hat. Da gerade ist und eine Funktion wir wissen vorher, dass entweder 1-zu-1 oder 2-zu-1 ist. Wir sind nur zu machen , Anfragen über den Wert der erlaubten für jedes $n$ $f:\{1,...,n\}\to\{1,...,n\}$ $f$ $f(i)$ . Das Problem fragt dann, wie viele Abfragen wir machen müssen, um mit Sicherheit zu bestimmen, ob 1-zu-1 oder 2-zu-1 ist. $i\in\{1,2,...,n\}$ $f$

Das deterministische Lösen der 2-zu-1-Version erfordert Abfragen, und im Allgemeinen erfordert das Unterscheiden von r-zu-1-Funktionen von 1-zu-1-Funktionen Abfragen. $n/2+1$ $n/r+1$

Deterministische klassische Lösung :

Dies ist eine einfache Anwendung des Pigeonhole-Prinzips: Wenn eine Funktion r-to-1 ist, dann ist nach Abfragen garantiert, dass wir eine Kollision gefunden haben. Wenn eine Funktion 1 zu 1 ist, liegt keine Kollision vor. Wenn wir Pech haben, können Anfragen unterschiedliche Antworten liefern. Es sind also Abfragen erforderlich. $n/r+1$ $n/r$ $n/r+1$

Randomisierte klassische Lösung :

Wenn wir Zufälligkeit zulassen, ist das Problem einfacher. Nach dem Geburtstagsparadoxon finden wir mit hoher Wahrscheinlichkeit eine Kollision in einer festen 2-zu-1-Funktion nach ), wenn wir zufällig (verschiedene) Abfragen auswählen Abfragen. $\Theta(\sqrt{n})$

Quantum BHT Lösung :

Intuitiv kombiniert der Algorithmus die Quadratwurzel-Beschleunigung aus dem Geburtstagsparadoxon unter Verwendung der (klassischen) Zufälligkeit mit der Quadratwurzel-Beschleunigung aus dem (Quanten-) Algorithmus von Grover.

Erstens Eingaben werden zufällig ausgewählt , und bei allen von ihnen abgefragt. Wenn es eine Kollision zwischen diesen Eingaben gibt, geben wir das kollidierende Paar von Eingaben zurück. Andernfalls werden alle diese Eingaben unterschiedlichen Werten durch . Dann wird der Algorithmus von Grover verwendet, um eine neue Eingabe für , die kollidiert. Da es nur ist solche Eingaben kann Grover-Algorithmus nur einen finden , indem sie (falls vorhanden) $n^{1/3}$ $f$ $f$ $f$ $f$ $n^{2/3}$ $f$ $\mathcal{O}(\sqrt{n^{2/3}})=\mathcal{O}(n^{1/3})$ $f$

Quellen:

Sanchayan Dutta
quelle

Einige Kommentare zur BHT-Lösung (ich fand den Wikipedia-Artikel nicht sehr aufschlussreich): Wählen Sie zunächst

n^{1 / 3}

$n^{1/3}$ zu testende Eingänge

f

$f$ at random. Assume they don't collide. Sort these values

x

$x$ according to

f (x)

$f(x)$ . Now, if

f (x)

$f(x)$ is 2-to-1, there are

n^{1 / 3}

$n^{1/3}$ values

x

$x$ not already tested that collide with those tested. So, define a function that checks "not already tested and collides". This defines the marked entries. Collision is easy to test with the sorted list of values

f (x)

$f(x)$ . Knowing the exact number of marked entries (if 2-to-1), Grover's (almost) guarantees a solution.

DaftWullie

@DaftWullie Yes, that sure makes sense. Grover's algorithm doesn't guarantee a solution but has a high probability of providing the correct solution. But isn't that quite obvious from the Wikipedia description itself? I'm not sure I understand the point or objection you're making. Am I missing something?

Sanchayan Dutta

All I can say is that it wasn't obvious to me. On first reading, I understood (falsely) that for Grover's, instead of preparing a superposition of all possible states, it only prepared a superposition over the ones not already tested. But that seemed crucial to the way that the speed-up was explained. Also, I was initially concerned about how the collisions were being checked: which pairs were being checked for collisions, and how efficiently could the collision be calculated?

DaftWullie

@DaftWullie Ah, okay. I get your point. Wikipedia doesn't go into that much detail of the algorithm. You can always refer to the original paper (arxiv.org/abs/quant-ph/9705002) for the details (which I guess you already did). Later, I will try to expand on this answer to include all the details. I'm still reading the paper.

Sanchayan Dutta

Unless qubits and quantum gates turn out to be unbelievably cheaper than bits and classical gates, any discussion of BHT should include the caveat that the costs exceed state-of-the-art classical collision search with the van Oorschot–Wiener machine. See cr.yp.to/papers.html#collisioncost or blog.cr.yp.to/20171017-collisions.html for details. (The latter is a response to an alleged improvement on BHT that claims to be more cost-effective than classical collision search.)

Squeamish Ossifrage

Der Algorithmus von Grover kann verwendet werden, um jedes numerische Optimierungsproblem schneller als bei der Brute-Force-Suche zu lösen, da jedes Optimierungsproblem als Suchproblem formuliert werden kann (bei dem Sie nach einer Funktionsausgabe suchen, die größer / kleiner als eine festgelegte ist $M$ Innerhalb jedes Laufs wiederholen Sie diesen Vorgang für eine logarithmische Anzahl von Läufen mit der binären Suche, um das Optimum zu ermitteln $M$ ): https://epubs.siam.org/doi/abs/10.1137/040605072?journalCode=sjope8 .

Tatsächlich ist der Algorithmus von Grover der bekannteste Quantenalgorithmus für viele schwierige Optimierungsprobleme (z. B. NP-vollständige), bei denen die Struktur eines klassischen Algorithmus, der klüger als die Brute-Force-Suche ist, nicht besonders gut ist: https: // link.springer.com/chapter/10.1007/978-3-540-78773-0_67 .

tparker
quelle

Welche Anwendungen hat der Suchalgorithmus von Grover?

Antworten: