Analyse

Wir analysieren nun Grovers Algorithmus, um zu verstehen, wie er funktioniert. Wir beginnen mit dem, was man als symbolische Analyse beschreiben könnte, bei der wir berechnen, wie die Grover-Operation $G$ auf bestimmte Zustände wirkt, und verbinden diese symbolische Analyse dann mit einem geometrischen Bild, das dabei hilft, die Funktionsweise des Algorithmus zu visualisieren.

Lösungen und Nicht-Lösungen

Beginnen wir mit der Definition zweier Mengen von Zeichenketten.

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

Die Menge $A_1$ enthält alle Lösungen unseres Suchproblems, während $A_0$ die Zeichenketten enthält, die keine Lösungen sind (die wir als Nicht-Lösungen bezeichnen, wenn es praktisch ist). Diese beiden Mengen erfüllen $A_0 \cap A_1 = \varnothing$ und $A_0 \cup A_1 = \Sigma^n$, das heißt, dies ist eine Bipartition von $\Sigma^n$.

Als Nächstes definieren wir zwei Einheitsvektoren, die gleichmäßige Überlagerungen über die Mengen der Lösungen und Nicht-Lösungen darstellen.

$$\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}$$

Formal gesehen ist jeder dieser Vektoren nur definiert, wenn die entsprechende Menge nicht leer ist, aber im Folgenden konzentrieren wir uns auf den Fall, dass weder $A_0$ noch $A_1$ leer ist. Die Fälle $A_0 = \varnothing$ und $A_1 = \varnothing$ lassen sich leicht separat behandeln, was wir später tun werden.

Nebenbei sei bemerkt: Die hier verwendete Notation ist üblich – immer wenn wir eine endliche und nicht leere Menge $S$ haben, können wir $\vert S\rangle$ schreiben, um den Quantenzustandsvektor zu bezeichnen, der gleichmäßig über den Elementen von $S$ verteilt ist.

Definieren wir außerdem $\vert u \rangle$ als gleichmäßigen Quantenzustand über alle $n$-Bit-Zeichenketten:

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

Beachte, dass

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

Außerdem gilt $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle$, sodass $\vert u\rangle$ den Zustand des Registers $\mathsf{Q}$ nach der Initialisierung in Schritt 1 von Grovers Algorithmus darstellt.

Das impliziert, dass der Zustand von $\mathsf{Q}$ unmittelbar vor den Iterationen von $G$ in Schritt 2 im zweidimensionalen Vektorraum liegt, der von $\vert A_0\rangle$ und $\vert A_1\rangle$ aufgespannt wird, und dass die Koeffizienten dieser Vektoren reelle Zahlen sind. Wie wir sehen werden, werden diese Eigenschaften des Zustands – dass er eine reelle Linearkombination von $\vert A_0\rangle$ und $\vert A_1\rangle$ ist – nach jeder Anzahl von Iterationen der Operation $G$ in Schritt 2 erhalten bleiben.

Eine Beobachtung zur Grover-Operation

Wir wenden uns nun der Grover-Operation zu:

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

und beginnen mit einer interessanten Beobachtung dazu.

Stellen wir uns kurz vor, wir würden die Funktion $f$ durch die Komposition von $f$ mit der NOT-Funktion ersetzen – oder anders gesagt, durch die Funktion, die wir erhalten, wenn wir das Ausgabebit von $f$ invertieren. Wir nennen diese neue Funktion $g$ und können sie symbolisch auf einige alternative Weisen ausdrücken.

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

Beachte, dass

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

für jede Zeichenkette $x\in\Sigma^n$ gilt und daher

$$Z_g = - Z_f.$$

Das bedeutet, wenn wir die Funktion $f$ durch die Funktion $g$ ersetzen würden, würde Grovers Algorithmus nicht anders funktionieren – denn die Zustände, die wir aus dem Algorithmus in den beiden Fällen erhalten, sind notwendigerweise äquivalent bis auf eine globale Phase.

Das ist kein Problem! Intuitiv gesprochen ist es dem Algorithmus egal, welche Zeichenketten Lösungen sind und welche nicht – er muss nur in der Lage sein, Lösungen von Nicht-Lösungen zu unterscheiden, um korrekt zu funktionieren.

Wirkung der Grover-Operation

Betrachten wir nun die Wirkung von $G$ auf die Quantenzustandsvektoren $\vert A_0\rangle$ und $\vert A_1\rangle$.

Zunächst stellen wir fest, dass die Operation $Z_f$ eine sehr einfache Wirkung auf $\vert A_0\rangle$ und $\vert A_1\rangle$ hat.

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

Zweitens haben wir die Operation $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$. Die Operation $Z_{\mathrm{OR}}$ ist definiert als

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[2mm] -\vert x\rangle & x \neq 0^n, \end{cases}$$

wiederum für jede Zeichenkette $x\in\Sigma^n$, und eine praktische alternative Ausdrucksweise dieser Operation ist:

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

Eine einfache Möglichkeit, zu überprüfen, dass dieser Ausdruck mit der Definition von $Z_{\mathrm{OR}}$ übereinstimmt, besteht darin, seine Wirkung auf Standard-Basiszustände zu evaluieren.

Die Operation $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ kann daher wie folgt geschrieben werden:

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

wobei wir dieselbe Notation $\vert u \rangle$ wie oben für die gleichmäßige Überlagerung über alle $n$-Bit-Zeichenketten verwenden.

Und nun haben wir, was wir brauchen, um die Wirkung von $G$ auf $\vert A_0\rangle$ und $\vert A_1\rangle$ zu berechnen. Zuerst berechnen wir die Wirkung von $G$ auf $\vert A_0\rangle$.

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

Und zweitens berechnen wir die Wirkung von $G$ auf $\vert A_1\rangle$.

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

In beiden Fällen verwenden wir die Gleichung

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

zusammen mit den daraus folgenden Ausdrücken

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{and}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

die sich daraus ergeben.

Zusammenfassend erhalten wir

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

Wie bereits erwähnt, liegt der Zustand von $\mathsf{Q}$ unmittelbar vor Schritt 2 im zweidimensionalen Raum, der von $\vert A_0\rangle$ und $\vert A_1\rangle$ aufgespannt wird, und wir haben gerade gezeigt, dass $G$ jeden Vektor in diesem Raum auf einen anderen Vektor im selben Raum abbildet. Das bedeutet, dass wir uns für die Analyse ausschließlich auf diesen Unterraum konzentrieren können.

Um besser zu verstehen, was in diesem zweidimensionalen Raum passiert, wollen wir die Wirkung von $G$ auf diesen Raum als Matrix ausdrücken,

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

deren erste und zweite Zeile/Spalte jeweils $\vert A_0\rangle$ und $\vert A_1\rangle$ entsprechen. Bisher haben wir in dieser Reihe die Zeilen und Spalten von Matrizen stets mit den klassischen Zuständen eines Systems verknüpft, aber Matrizen können auch verwendet werden, um die Wirkung linearer Abbildungen auf unterschiedlichen Basen zu beschreiben, wie wir es hier tun.

Obwohl es auf den ersten Blick überhaupt nicht offensichtlich ist, erhalten wir die Matrix $M$, indem wir eine einfacher aussehende Matrix quadrieren.

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

Die Matrix

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

ist eine Rotationsmatrix, die wir alternativ ausdrücken können als

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

für

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

Dieser Winkel $\theta$ wird in der folgenden Analyse eine sehr wichtige Rolle spielen, deshalb lohnt es sich, seine Bedeutung zu betonen, wenn wir ihn hier zum ersten Mal sehen.

Angesichts dieses Ausdrucks beobachten wir, dass

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

Das liegt daran, dass eine zweimalige Rotation um den Winkel $\theta$ einer Rotation um den Winkel $2\theta$ entspricht. Eine weitere Möglichkeit, das einzusehen, ist die Verwendung des alternativen Ausdrucks

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

zusammen mit den Doppelwinkelformeln der Trigonometrie:

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

Zusammenfassend ist der Zustand des Registers $\mathsf{Q}$ zu Beginn von Schritt 2

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

und der Effekt, $G$ auf diesen Zustand anzuwenden, besteht darin, ihn um einen Winkel $2\theta$ im von $\vert A_0\rangle$ und $\vert A_1\rangle$ aufgespannten Raum zu rotieren. So haben wir zum Beispiel

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

und allgemein

$$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.$$

Geometrisches Bild

Verbinden wir nun die gerade durchgeführte Analyse mit einem geometrischen Bild. Die Idee ist, dass die Operation $G$ das Produkt zweier Spiegelungen ist: $Z_f$ und $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$. Und der Nettoeffekt von zwei Spiegelungen ist eine Rotation.

Beginnen wir mit $Z_f$. Wie wir bereits zuvor beobachtet haben, gilt

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

Im zweidimensionalen Vektorraum, der von $\vert A_0\rangle$ und $\vert A_1\rangle$ aufgespannt wird, ist das eine Spiegelung an der Geraden parallel zu $\vert A_0\rangle$, die wir $L_1$ nennen werden. Hier ist eine Abbildung, die die Wirkung dieser Spiegelung auf einen hypothetischen Einheitsvektor $\vert\psi\rangle$ illustriert, der als reelle Linearkombination von $\vert A_0\rangle$ und $\vert A_1\rangle$ angenommen wird.

Zweitens haben wir die Operation $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$, die sich, wie wir bereits gesehen haben, schreiben lässt als

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

Auch das ist eine Spiegelung, diesmal an der Geraden $L_2$ parallel zum Vektor $\vert u\rangle$. Hier ist eine Abbildung, die die Wirkung dieser Spiegelung auf einen Einheitsvektor $\vert\psi\rangle$ zeigt.

Wenn wir diese beiden Spiegelungen zusammensetzen, erhalten wir eine Rotation — um den doppelten Winkel zwischen den Spiegelungslinien —, wie diese Abbildung zeigt.

Das erklärt in geometrischen Begriffen, warum der Effekt der Grover-Operation darin besteht, Linearkombinationen von $\vert A_0\rangle$ und $\vert A_1\rangle$ um einen Winkel $2\theta$ zu drehen.