Unstrukturierte Suche

Zusammenfassung

Wir beginnen mit einer Beschreibung des Problems, das Grovers Algorithmus löst. Wie üblich schreiben wir $\Sigma = \{0,1\}$ für das binäre Alphabet in dieser gesamten Diskussion.

Sei

$$f:\Sigma^n \rightarrow \Sigma$$

eine Funktion von Binärzeichenketten der Länge $n$ auf Bits. Wir gehen davon aus, dass wir diese Funktion effizient berechnen können, ansonsten ist sie jedoch beliebig, und wir können uns nicht auf eine besondere Struktur oder eine spezifische Implementierung verlassen.

Was Grovers Algorithmus tut, ist nach einer Zeichenkette $x\in\Sigma^n$ zu suchen, für die $f(x) = 1$ gilt. Solche Zeichenketten bezeichnen wir als Lösungen des Suchproblems. Falls es mehrere Lösungen gibt, ist jede einzelne davon eine korrekte Ausgabe; gibt es keine Lösung, muss die Antwort lauten, dass keine Lösung existiert.

Diese Aufgabe wird als unstrukturiertes Suchproblem bezeichnet, weil wir nicht davon ausgehen können, dass $f$ eine besondere Struktur hat, die es einfach macht. Wir durchsuchen keine geordnete Liste und keine Datenstruktur, die speziell für die Suche konzipiert wurde – wir suchen im Grunde eine Nadel im Heuhaufen.

Intuitiv könnte man sich vorstellen, dass wir einen äußerst komplexen Booleschen Circuit haben, der $f$ berechnet, und diesen Circuit für eine ausgewählte Eingabezeichenkette leicht ausführen können. Da der Circuit jedoch so kompliziert ist, haben wir keine Chance, ihn durch Untersuchung zu verstehen (abgesehen von der Möglichkeit, ihn für ausgewählte Eingaben auszuwerten).

Eine Möglichkeit, diese Suchaufgabe klassisch durchzuführen, besteht darin, alle Zeichenketten $x\in\Sigma^n$ der Reihe nach durchzugehen und $f$ für jede zu evaluieren, um zu prüfen, ob sie eine Lösung ist. Schreiben wir im Folgenden

$$N = 2^n$$

der Einfachheit halber. Es gibt $N$ Zeichenketten in $\Sigma^n$, sodass das Durchlaufen aller $N$ Auswertungen von $f$ erfordert. Unter der Annahme, dass wir auf die Auswertung von $f$ auf ausgewählten Eingaben beschränkt sind, ist das das Beste, was wir mit einem deterministischen Algorithmus tun können, wenn wir Erfolg garantieren wollen. Mit einem probabilistischen Algorithmus könnte man Zeit sparen, indem man Eingaben für $f$ zufällig auswählt – aber auch dann benötigt man $O(N)$ Auswertungen von $f$, wenn die Methode mit hoher Wahrscheinlichkeit erfolgreich sein soll.

Grovers Algorithmus löst dieses Suchproblem mit hoher Wahrscheinlichkeit mit nur $O(\sqrt{N})$ Auswertungen von $f$. Diese Funktionsauswertungen müssen in Überlagerung stattfinden, ähnlich wie bei den Abfragealgorithmen, die in der Lektion Quanten-Abfragealgorithmen besprochen wurden, einschließlich Deutschs Algorithmus, des Deutsch-Jozsa-Algorithmus und Simons Algorithmus. Im Gegensatz zu diesen Algorithmen verfolgt Grovers Algorithmus einen iterativen Ansatz: Er wertet $f$ auf Überlagerungen von Eingabezeichenketten aus und verschränkt diese Auswertungen mit anderen Operationen, die Interferenzmuster erzeugen und nach $O(\sqrt{N})$ Iterationen mit hoher Wahrscheinlichkeit zu einer Lösung führen (sofern eine existiert).

Formale Problemstellung

Wir formalisieren das Problem, das Grovers Algorithmus löst, mithilfe des Abfragemodells der Berechnung. Das heißt, wir nehmen an, dass wir auf die Funktion $f:\Sigma^n\rightarrow\Sigma$ über ein Abfrage-Gate zugreifen können, das wie üblich definiert ist:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

für jedes $x\in\Sigma^n$ und $a\in\Sigma$. Dies ist die Wirkung von $U_f$ auf Standard-Basiszustände; seine Wirkung im Allgemeinen wird durch Linearität bestimmt.

Wie in der Lektion Algorithmische Grundlagen der Quantenberechnung besprochen, können wir eine Beschreibung eines Booleschen Circuits, der $f$ berechnet, in einen Quantencircuit umwandeln, der $U_f$ implementiert (unter Verwendung einiger Hilfs-Qubits, die die Berechnung im Zustand $\vert 0\rangle$ beginnen und beenden). Obwohl wir das Abfragemodell zur Formalisierung des Problems verwenden, ist Grovers Algorithmus nicht auf dieses Modell beschränkt; wir können ihn auf jede Funktion $f$ anwenden, für die wir einen Booleschen Circuit haben.

Hier ist eine präzise Aussage des Problems, das Such-Problem genannt wird, weil wir nach einer Lösung suchen – also nach einer Zeichenkette $x$, für die $f$ den Wert $1$ ergibt.

Such-Problem

Eingabe: eine Funktion $f:\Sigma^n\rightarrow\Sigma$
Ausgabe: eine Zeichenkette $x\in\Sigma^n$ mit $f(x) = 1,$ oder „keine Lösung", falls keine solche Zeichenkette $x$ existiert

Beachte, dass dies kein Promise-Problem ist – die Funktion $f$ ist beliebig. Es ist jedoch hilfreich, die folgende Promise-Variante des Problems zu betrachten, bei der genau eine Lösung garantiert ist. Dieses Problem wurde in der Lektion Quanten-Abfragealgorithmen als Beispiel für ein Promise-Problem eingeführt.

Eindeutiges Such-Problem

Eingabe: eine Funktion der Form $f:\Sigma^n \rightarrow \Sigma$
Versprechen: Es gibt genau eine Zeichenkette $z\in\Sigma^n$, für die $f(z) = 1$ gilt, und $f(x) = 0$ für alle Zeichenketten $x\neq z$
Ausgabe: die Zeichenkette $z$

Beachte auch, dass das Or-Problem aus derselben Lektion eng mit dem Such-Problem verwandt ist. Bei jenem Problem ist das Ziel lediglich festzustellen, ob eine Lösung existiert – und nicht eine Lösung tatsächlich zu finden.