Wahl der Anzahl der Iterationen

Wir haben festgestellt, dass der Zustandsvektor des Registers $\mathsf{Q}$ in Grovers Algorithmus im zweidimensionalen Unterraum verbleibt, der von $\vert A_0\rangle$ und $\vert A_1\rangle$ aufgespannt wird, sobald der Initialisierungsschritt durchgeführt wurde.

Das Ziel ist es, ein Element $x\in A_1$ zu finden, und dieses Ziel wird erreicht, wenn wir den Zustand $\vert A_1\rangle$ erhalten – denn wenn wir diesen Zustand messen, erhalten wir garantiert ein Messergebnis $x\in A_1$. Da der Zustand von $\mathsf{Q}$ nach $t$ Iterationen in Schritt 2

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle$$

ist, sollten wir $t$ so wählen, dass

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

dem Betrag nach möglichst nahe an $1$ ist, um die Wahrscheinlichkeit zu maximieren, $x\in A_1$ bei der Messung zu erhalten. Für jeden Winkel $\theta \in (0,2\pi)$ oszilliert der Wert $\sin((2t + 1)\theta)$ mit zunehmendem $t$, ist aber nicht notwendigerweise periodisch – es gibt keine Garantie, dass wir denselben Wert je zweimal erhalten.

Natürlich möchten wir neben der großen Wahrscheinlichkeit, ein Element $x\in A_1$ aus der Messung zu erhalten, auch $t$ so klein wie möglich wählen, da $t$ Anwendungen der Operation $G$ $t$ Abfragen an die Funktion $f$ erfordern. Da wir darauf abzielen, $\sin( (2t + 1) \theta)$ dem Betrag nach nahe an $1$ zu bringen, ist eine natürliche Vorgehensweise, $t$ so zu wählen, dass

$$(2t + 1) \theta \approx \frac{\pi}{2}.$$

gilt. Auflösen nach $t$ ergibt

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

Da $t$ eine ganze Zahl sein muss, können wir diesen Wert nicht immer exakt treffen – aber wir können die nächste ganze Zahl zu diesem Wert nehmen, nämlich

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

Dies ist die empfohlene Anzahl von Iterationen für Grovers Algorithmus. Im Verlauf der Analyse werden wir sehen, dass die Nähe dieser ganzen Zahl zum Zielwert die Leistung des Algorithmus beeinflusst.

(Nebenbei bemerkt: Wenn der Zielwert $\pi/(4\theta) - 1/2$ genau in der Mitte zwischen zwei ganzen Zahlen liegt, ergibt dieser Ausdruck für $t$ das Aufrunden. Alternativ könnte man abrunden, was sinnvoll ist, da es eine Abfrage weniger bedeutet – aber das ist zweitrangig und für die Zwecke der Lektion unwichtig.)

Wenn wir uns daran erinnern, dass der Wert des Winkels $\theta$ durch die Formel

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr)$$

gegeben ist, sehen wir, dass die empfohlene Anzahl von Iterationen $t$ von der Anzahl der Zeichenketten in $A_1$ abhängt. Das stellt eine Herausforderung dar, wenn wir nicht wissen, wie viele Lösungen wir haben, wie wir später besprechen werden.

Eindeutige Suche

Konzentrieren wir uns zunächst auf die Situation, in der es genau eine Zeichenkette $x$ mit $f(x)=1$ gibt. Anders gesagt betrachten wir eine Instanz des Eindeutigen-Such-Problems. In diesem Fall gilt

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr),$$

was bequem als

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr) \approx \sqrt{\frac{1}{N}}$$

approximiert werden kann, wenn $N$ groß wird. Wenn wir $\theta = 1/\sqrt{N}$ in den Ausdruck

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

einsetzen, erhalten wir

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

Da $t$ nicht nur die Anzahl der Ausführungen der Operation $G$ ist, sondern auch die Anzahl der vom Algorithmus benötigten Abfragen an die Funktion $f$, sind wir auf dem Weg zu einem Algorithmus, der $O(\sqrt{N})$ Abfragen benötigt.

Untersuchen wir nun, wie gut die empfohlene Wahl von $t$ funktioniert. Die Wahrscheinlichkeit, dass die abschließende Messung die eindeutige Lösung ergibt, kann explizit ausgedrückt werden als

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

Das erste Argument, $N$, bezieht sich auf die Anzahl der Elemente, über die wir suchen, und das zweite Argument, hier $1$, auf die Anzahl der Lösungen. Etwas später werden wir dieselbe Notation allgemeiner verwenden, wenn es mehrere Lösungen gibt.

Hier ist eine Tabelle der Erfolgswahrscheinlichkeiten für zunehmende Werte von $N = 2^n$.

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

Beachte, dass diese Wahrscheinlichkeiten nicht streng monoton steigen. Insbesondere gibt es eine interessante Anomalie bei $N=4$, wo wir mit Sicherheit eine Lösung erhalten. Es lässt sich jedoch allgemein beweisen, dass

$$p(N,1) \geq 1 - \frac{1}{N}$$

für alle $N$ gilt, sodass die Erfolgswahrscheinlichkeit im Grenzwert für großes $N$ gegen $1$ strebt, wie die obigen Werte zu bestätigen scheinen. Das ist gut!

Aber beachte, dass selbst eine schwache Schranke wie $p(N,1) \geq 1/2$ den Nutzen von Grovers Algorithmus belegt. Für jedes Messergebnis $x$, das wir aus dem Ausführen des Verfahrens erhalten, können wir immer mit einer einzigen Abfrage an $f$ prüfen, ob $f(x) = 1$ gilt. Und wenn wir mit einer Wahrscheinlichkeit von höchstens $1/2$ die eindeutige Zeichenkette $x$ mit $f(x) = 1$ beim einmaligen Ausführen des Verfahrens nicht erhalten, dann werden wir nach $m$ unabhängigen Ausführungen diese eindeutige Zeichenkette $x$ mit einer Wahrscheinlichkeit von höchstens $2^{-m}$ nicht erhalten haben. Das heißt, mit $O(m \sqrt{N})$ Abfragen an $f$ erhalten wir die eindeutige Lösung $x$ mit einer Wahrscheinlichkeit von mindestens $1 - 2^{-m}$. Die bessere Schranke $p(N,1) \geq 1 - 1/N$ zeigt, dass die Wahrscheinlichkeit, $x\in A_1$ mit dieser Methode zu finden, tatsächlich mindestens $1 - N^{-m}$ beträgt.

Mehrere Lösungen

Mit der Anzahl der Elemente in $A_1$ variiert auch der Winkel $\theta$, was die Erfolgswahrscheinlichkeit des Algorithmus erheblich beeinflussen kann. Der Kürze halber schreiben wir $s = \vert A_1 \vert$ für die Anzahl der Lösungen, und wie zuvor nehmen wir an, dass $s\geq 1$ gilt.

Als motivierendes Beispiel stellen wir uns vor, dass wir $s = 4$ Lösungen statt einer einzigen haben, wie wir oben betrachtet haben. Das bedeutet, dass

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr)$$

gilt, was ungefähr das Doppelte des Winkels im Fall $\vert A_1 \vert = 1$ ist, wenn $N$ groß ist. Angenommen, wir wüssten es nicht besser und würden denselben Wert von $t$ wie im Fall mit eindeutiger Lösung wählen:

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

Die Auswirkung wäre katastrophal, wie die folgende Tabelle der Wahrscheinlichkeiten zeigt.

$$\begin{array}{ll} N & \text{Erfolgswahrscheinlichkeit}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

Diesmal geht die Erfolgswahrscheinlichkeit gegen $0$, wenn $N$ gegen Unendlich geht. Das liegt daran, dass wir uns doppelt so schnell drehen wie bei einer eindeutigen Lösung, sodass wir am Ziel $\vert A_1\rangle$ vorbeizischen und nahe bei $-\vert A_0\rangle$ landen.

Wenn wir stattdessen die empfohlene Wahl von $t$ verwenden, nämlich

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

für

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

wird die Leistung besser. Genauer gesagt führt diese Wahl von $t$ mit hoher Wahrscheinlichkeit zum Erfolg.

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

Verallgemeinernd lässt sich beweisen, dass

$$p(N,s) \geq 1 - \frac{s}{N}$$

gilt, wobei wir die oben vorgeschlagene Notation verwenden: $p(N,s)$ bezeichnet die Wahrscheinlichkeit, dass Grovers Algorithmus, der für $t$ Iterationen ausgeführt wird, eine Lösung aufdeckt, wenn es insgesamt $s$ Lösungen unter $N$ Möglichkeiten gibt.

Diese untere Schranke von $1 - s/N$ für die Erfolgswahrscheinlichkeit ist etwas eigenartig, da mehr Lösungen eine schlechtere untere Schranke implizieren – aber unter der Annahme, dass $s$ deutlich kleiner als $N$ ist, schließen wir dennoch, dass die Erfolgswahrscheinlichkeit vernünftig hoch ist. Wie zuvor impliziert die bloße Tatsache, dass $p(N,s)$ vernünftig groß ist, den Nutzen des Algorithmus.

Es gilt auch, dass

$$p(N,s) \geq \frac{s}{N}.$$

Diese untere Schranke beschreibt die Wahrscheinlichkeit, dass eine gleichmäßig zufällig ausgewählte Zeichenkette $x\in\Sigma^n$ eine Lösung ist – also arbeitet Grovers Algorithmus immer mindestens so gut wie das zufällige Raten. (Tatsächlich ist Grovers Algorithmus bei $t=0$ genau zufälliges Raten.)

Betrachten wir nun die Anzahl der Iterationen (und damit die Anzahl der Abfragen)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

für

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{s}{N}}\biggr).$$

Für jedes $\alpha \in [0,1]$ gilt $\sin^{-1}(\alpha)\geq \alpha$, und daher

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

Das impliziert, dass

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

Das entspricht einer Einsparung bei der Anzahl der Abfragen, wenn $s$ wächst. Insbesondere ist die benötigte Anzahl von Abfragen

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

Unbekannte Anzahl von Lösungen

Wenn die Anzahl der Lösungen $s = \vert A_1 \vert$ unbekannt ist, ist ein anderer Ansatz erforderlich, da wir in dieser Situation keine Kenntnis von $s$ haben, um unsere Wahl von $t$ zu informieren. Es gibt tatsächlich mehrere Ansätze.

Ein einfacher Ansatz ist, $t$ gleichmäßig zufällig aus

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

zu wählen. Eine solche Wahl von $t$ findet immer eine Lösung (sofern eine existiert) mit einer Wahrscheinlichkeit von mehr als 40%, obwohl das nicht offensichtlich ist und eine Analyse erfordert, die hier nicht enthalten ist. Es ergibt jedoch Sinn, besonders wenn wir das geometrische Bild betrachten: Den Zustand von $\mathsf{Q}$ eine zufällige Anzahl von Malen zu drehen ist nicht unähnlich der Wahl eines zufälligen Einheitsvektors im von $\vert A_0\rangle$ und $\vert A_1\rangle$ aufgespannten Raum, bei dem es wahrscheinlich ist, dass der Koeffizient von $\vert A_1\rangle$ vernünftig groß ist. Durch Wiederholen dieses Verfahrens und Überprüfen des Ergebnisses auf die gleiche Weise wie zuvor beschrieben kann die Wahrscheinlichkeit, eine Lösung zu finden, sehr nahe an $1$ gebracht werden.

Es gibt eine verfeinerte Methode, die eine Lösung findet, wenn eine existiert, mit $O(\sqrt{N/s})$ Abfragen, auch wenn die Anzahl der Lösungen $s$ nicht bekannt ist, und die $O(\sqrt{N})$ Abfragen benötigt, um festzustellen, dass es keine Lösungen gibt, wenn $s=0$ gilt.

Die grundlegende Idee besteht darin, $t$ iterativ gleichmäßig zufällig aus der Menge $\{1,\ldots,T\}$ zu wählen, für zunehmende Werte von $T$. Insbesondere können wir mit $T = 1$ beginnen und es exponentiell erhöhen, den Prozess stets zu beenden, sobald eine Lösung gefunden wird, und $T$ zu begrenzen, um keine Abfragen zu verschwenden, wenn es keine Lösung gibt. Das Verfahren nutzt die Tatsache aus, dass weniger Abfragen erforderlich sind, wenn mehr Lösungen existieren. Es ist jedoch Sorgfalt geboten, um die Wachstumsrate von $T$ mit der Erfolgswahrscheinlichkeit jeder Iteration in Einklang zu bringen. ($T \leftarrow \lceil \frac{5}{4}T\rceil$ funktioniert beispielsweise, wie eine Analyse zeigt. Eine Verdopplung von $T$ hingegen nicht – das ist eine zu schnelle Erhöhung.)

Die trivialen Fälle

In der gesamten bisherigen Analyse haben wir angenommen, dass die Anzahl der Lösungen nicht null ist. Tatsächlich haben wir durch den Bezug auf die Vektoren

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

implizit angenommen, dass $A_0$ und $A_1$ beide nicht leer sind. Hier werden wir kurz betrachten, was passiert, wenn eine dieser Mengen leer ist.

Bevor wir uns mit einer Analyse befassen, stellen wir das Offensichtliche fest: Wenn jede Zeichenkette $x\in\Sigma^n$ eine Lösung ist, werden wir bei der Messung eine Lösung sehen; und wenn es keine Lösungen gibt, werden wir keine sehen. In gewissem Sinne muss man nicht tiefer gehen als das.

Wir können jedoch schnell die Mathematik für diese trivialen Fälle überprüfen. Die Situation, in der eine von $A_0$ und $A_1$ leer ist, tritt auf, wenn $f$ konstant ist; $A_1$ ist leer, wenn $f(x) = 0$ für jedes $x\in\Sigma^n$ gilt, und $A_0$ ist leer, wenn $f(x) = 1$ für jedes $x\in\Sigma^n$ gilt. Das bedeutet, dass

$$Z_f \vert u\rangle = \pm \vert u\rangle$$

gilt und daher

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

Unabhängig von der Anzahl der Iterationen $t$, die wir in diesen Fällen durchführen, werden die Messungen also immer eine gleichmäßig zufällige Zeichenkette $x\in\Sigma^n$ ergeben.