Analyse

Jetzt werden wir Grovers Algorithmus analysieren, um zu verstehen, wie er funktioniert. Wir beginnen mit einer symbolischen Analyse, bei der wir berechnen, wie sich die Grover-Operation $G$ auf bestimmte Zustände auswirkt, und verknüpfen diese symbolische Analyse dann mit einem geometrischen Bild, das die Funktionsweise des Algorithmus veranschaulicht.

---

Lösungen und Nicht-Lösungen

Beginnen wir mit der Definition von zwei Gruppen von Zeichenfolgen.

$$\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 Zeichenfolgen enthält, die keine Lösungen sind (die wir der Einfachheit halber als „Nicht-Lösungen“ bezeichnen können). Diese beiden Mengen erfüllen die Bedingungen $A_0 \cap A_1 = \varnothing$ und $A_0 \cup A_1 = \Sigma^n$, was bedeutet, dass es sich hierbei um eine Zweiteilung von $\Sigma^n$ handelt.

Als Nächstes definieren wir zwei Einheitsvektoren, die einheitliche Ü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 dann definiert, wenn die zugehörige Menge nicht leer ist, aber wir werden uns im Folgenden auf den Fall konzentrieren, dass weder $A_0$ noch $A_1$ leer ist. Die Fälle, die $A_0 = \varnothing$ und $A_1 = \varnothing$ betreffen, können leicht getrennt behandelt werden, was wir später tun werden.

Nebenbei bemerkt ist die hier verwendete Notation üblich: Immer wenn wir eine endliche und nichtleere Menge $S$ haben, können wir $\vert S\rangle$ schreiben, um den Quantenzustandsvektor zu bezeichnen, der über die Elemente von $S$ gleichmäßig verteilt ist.

Definieren wir auch $\vert u \rangle$ als einheitlichen Quantenzustand über alle $n$ -Bit-Strings:

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

Beachten Sie, 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.$$

Da außerdem gilt: „ $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle$ “, stellt „ $\vert u\rangle$ “ den Zustand des Registers „ $\mathsf{Q}$ “ nach der Initialisierung in Schritt 1 des Grover-Algorithmus dar.

Dies bedeutet, dass unmittelbar vor den Iterationen von $G$ in Schritt 2 der Zustand von $\mathsf{Q}$ in dem zweidimensionalen Vektorraum enthalten ist, der durch $\vert A_0\rangle$ und $\vert A_1\rangle$ aufgespannt wird, und dass zudem die Koeffizienten dieser Vektoren reelle Zahlen sind. Wie wir sehen werden, weist der Zustand $\mathsf{Q}$ nach einer beliebigen Anzahl von Iterationen der Operation $G$ in Schritt 2 stets diese Eigenschaften auf – was bedeutet, dass der Zustand eine echte Linearkombination aus $\vert A_0\rangle$ und $\vert A_1\rangle$ ist.

---

Eine Beobachtung zur Grover-Operation

Wenden wir uns nun der Operation Grover zu

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

mit einer interessanten Beobachtung zu beginnen.

Stellen wir uns einmal vor, wir würden die Funktion $f$ durch die Zusammensetzung von $f$ mit der NOT-Funktion ersetzen – oder, mit anderen Worten, durch die Funktion, die wir erhalten, wenn wir das Ausgangsbit von $f$ umkehren. Wir nennen diese neue Funktion $g$ und können sie mithilfe von Symbolen auf verschiedene Arten darstellen.

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

Beachten Sie, dass

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

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

$$Z_g = - Z_f.$$

Das bedeutet: Würden wir die Funktion $f$ durch die Funktion $g$ ersetzen, würde sich die Funktionsweise des Grover-Algorithmus nicht ändern – denn die Zustände, die wir in beiden Fällen aus dem Algorithmus erhalten, sind bis auf eine globale Phase zwangsläufig äquivalent.

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

---

Aktion der Grover-Operation

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

Zunächst sei angemerkt, 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 gibt es die Operation „ $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ “. Die Operation „ $Z_{\mathrm{OR}}$ “ ist wie folgt definiert:

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

wieder für jede Zeichenkette $x\in\Sigma^n$, und eine praktische Alternative, um diese Operation auszudrücken, sieht folgendermaßen aus:

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

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

Die Operation $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ kann also 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},$$

unter Verwendung derselben Notation, $\vert u \rangle$, die wir oben für die gleichmäßige Überlagerung über alle $n$ -Bit-Zeichenfolgen verwendet haben.

Und nun haben wir alles, was wir brauchen, um die Wirkung von $G$ auf $\vert A_0\rangle$ und $\vert A_1\rangle$ zu berechnen. Berechnen wir zunächst 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 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 folgen.

Zusammenfassend lässt sich sagen, dass 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 in dem zweidimensionalen Raum, der durch „ $\vert A_0\rangle$ “ und „ $\vert A_1\rangle$ “ aufgespannt wird, und wir haben soeben festgestellt, dass „ $G$ “ jeden Vektor in diesem Raum auf einen anderen Vektor im selben Raum abbildet. Das bedeutet, dass wir uns für die Zwecke der Analyse ausschließlich auf diesen Unterraum konzentrieren können.

Um besser zu verstehen, was in diesem zweidimensionalen Raum geschieht, können wir die Wirkung von $G$ auf diesen Raum als Matrix darstellen,

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

dessen erste und zweite Zeile bzw. Spalte den Einträgen $\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 in Verbindung gebracht, doch Matrizen können auch dazu verwendet werden, die Abbildungen linearer Abbildungen auf verschiedene Basen zu beschreiben, wie wir es hier tun.

Auch wenn es auf den ersten Blick nicht offensichtlich ist, ist die Matrix $M$ das, was wir durch Quadrieren einer einfacher aussehenden Matrix erhalten.

$$\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 wie folgt ausdrücken können

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

nach

$$\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, so dass es sich lohnt, seine Bedeutung hier zu betonen, da wir ihn zum ersten Mal sehen.

In Anbetracht dieses Ausdrucks dieser Matrix stellen wir fest, 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 Drehung um den Winkel $\theta$ einer Drehung um den Winkel $2\theta$ entspricht. Eine andere Möglichkeit, dies zu veranschaulichen, besteht darin, die alternative Schreibweise zu verwenden

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

zusammen mit den Doppelwinkelformeln aus 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 lässt sich sagen, dass der Zustand des Registers $\mathsf{Q}$ zu Beginn von Schritt 2 folgender ist

$$\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 die Anwendung von „ $G$ “ auf diesen Zustand bewirkt eine Drehung um den Winkel „ $2\theta$ “ innerhalb des Raums, der durch „ $\vert A_0\rangle$ “ und „ $\vert A_1\rangle$ “ aufgespannt wird. So haben wir beispielsweise

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

Lassen Sie uns nun die soeben durchgeführte Analyse mit einer geometrischen Darstellung verknüpfen. Die Idee dahinter ist, dass die Operation $G$ das Produkt zweier Spiegelungen ist: $Z_f$ und $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$. Und das Endergebnis zweier Spiegelungen ist eine Drehung.

Beginnen wir mit „ $Z_f$ “. Wie wir bereits zuvor festgestellt 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}$$

In dem zweidimensionalen Vektorraum, der durch $\vert A_0\rangle$ und $\vert A_1\rangle$ aufgespannt wird, handelt es sich hierbei um eine Spiegelung an der Geraden parallel zu $\vert A_0\rangle$, die wir als $L_1$ bezeichnen. Die folgende Abbildung veranschaulicht die Wirkung dieser Spiegelung auf einen hypothetischen Einheitsvektor $\vert\psi\rangle$, von dem wir annehmen, dass er eine reelle Linearkombination aus $\vert A_0\rangle$ und $\vert A_1\rangle$ ist.

Zweitens haben wir die Operation „ $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ “, die, wie wir bereits gesehen haben, wie folgt geschrieben werden kann:

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

Dies ist ebenfalls eine Spiegelung, diesmal bezüglich der Geraden $L_2$, die parallel zum Vektor $\vert u\rangle$ verläuft. Hier ist eine Abbildung, die die Wirkung dieser Spiegelung auf einen Einheitsvektor $\vert\psi\rangle$ veranschaulicht.

Setzt man diese beiden Spiegelungen zusammen, erhält man eine Drehung - um den doppelten Winkel zwischen den Spiegelungslinien - wie diese Abbildung zeigt.

Dies erklärt aus geometrischer Sicht, warum die Grover-Operation dazu führt, dass Linearkombinationen von $\vert A_0\rangle$ und $\vert A_1\rangle$ um einen Winkel von $2\theta$ gedreht werden.