Beschreibung von Grovers Algorithmus

In diesem Abschnitt beschreiben wir Grovers Algorithmus. Wir beginnen mit der Diskussion von Phasen-Abfrage-Gates und wie man sie konstruiert, gefolgt von der Beschreibung des Algorithmus selbst. Abschließend erörtern wir kurz, wie der Algorithmus natürlicherweise auf die Suche angewendet wird.

Phasen-Abfrage-Gates

Grovers Algorithmus verwendet Operationen, die als Phasen-Abfrage-Gates bekannt sind. Im Gegensatz zu einem gewöhnlichen Abfrage-Gate $U_f$, das für eine gegebene Funktion $f$ wie zuvor beschrieben definiert ist, wird ein Phasen-Abfrage-Gate für die Funktion $f$ wie folgt definiert:

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

für jede Zeichenkette $x\in\Sigma^n$.

Die Operation $Z_f$ kann mit einem einzigen Abfrage-Gate $U_f$ implementiert werden, wie dieses Diagramm zeigt:

Diese Implementierung macht sich das Phase-Kickback-Phänomen zunutze und erfordert, dass ein Hilfs-Qubit, das im Zustand $\vert -\rangle$ initialisiert ist, verfügbar ist. Dieses Qubit verbleibt nach der Implementierung im Zustand $\vert - \rangle$ und kann wiederverwendet werden (etwa zur Implementierung nachfolgender $Z_f$-Gates) oder einfach verworfen werden.

Zusätzlich zur Operation $Z_f$ verwenden wir auch ein Phasen-Abfrage-Gate für die $n$-stellige OR-Funktion, die für jede Zeichenkette $x\in\Sigma^n$ wie folgt definiert ist:

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

Explizit wirkt das Phasen-Abfrage-Gate für die $n$-stellige OR-Funktion so:

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

Um klar zu sein: So wirkt $Z_{\mathrm{OR}}$ auf Standard-Basiszustände; sein Verhalten bei beliebigen Zuständen ergibt sich durch Linearität aus diesem Ausdruck.

Die Operation $Z_{\mathrm{OR}}$ kann als Quantencircuit implementiert werden, indem man mit einem Booleschen Circuit für die OR-Funktion beginnt, diesen in eine $U_{\mathrm{OR}}$-Operation umwandelt (also ein Standard-Abfrage-Gate für die $n$-stellige OR-Funktion) – nach dem in der Lektion Algorithmische Grundlagen der Quantenberechnung beschriebenen Verfahren –, und schließlich eine $Z_{\mathrm{OR}}$-Operation mithilfe des Phase-Kickback-Phänomens konstruiert. Beachte, dass $Z_{\mathrm{OR}}$ keine Abhängigkeit von der Funktion $f$ hat und daher durch einen Quantencircuit ohne Abfrage-Gates implementiert werden kann.

Beschreibung des Algorithmus

Nun, da wir die beiden Operationen $Z_f$ und $Z_{\mathrm{OR}}$ haben, können wir Grovers Algorithmus beschreiben.

Der Algorithmus bezieht sich auf eine Zahl $t$, die die Anzahl der Iterationen angibt (und damit die Anzahl der Abfragen an die Funktion $f$). Diese Zahl $t$ wird von Grovers Algorithmus in der hier beschriebenen Form nicht festgelegt; wir erörtern später in der Lektion, wie sie gewählt werden kann.

Grovers Algorithmus

1. Initialisiere ein $n$-Qubit-Register $\mathsf{Q}$ im Nullzustand $\vert 0^n \rangle$ und wende dann eine Hadamard-Operation auf jedes Qubit von $\mathsf{Q}$ an.
2. Wende $t$ Mal die unitäre Operation $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ auf das Register $\mathsf{Q}$ an.
3. Miss die Qubits von $\mathsf{Q}$ in der Standardbasis und gib die resultierende Zeichenkette aus.

Die in Schritt 2 iterierte Operation $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ wird im Rest dieser Lektion als Grover-Operation bezeichnet. Hier ist eine Quantencircuit-Darstellung der Grover-Operation für $n=7\!:$

In diesem Diagramm wird die $Z_f$-Operation als größer als $Z_{\mathrm{OR}}$ dargestellt – ein informeller visueller Hinweis darauf, dass sie wahrscheinlich die aufwändigere Operation ist. Insbesondere erfordert $Z_f$ im Abfragemodell eine Abfrage, während $Z_{\mathrm{OR}}$ keine Abfragen benötigt. Wenn wir stattdessen einen Booleschen Circuit für die Funktion $f$ haben und diesen in einen Quantencircuit für $Z_f$ umwandeln, darf man davon ausgehen, dass der resultierende Quantencircuit größer und komplexer ist als einer für $Z_{\mathrm{OR}}$.

Hier ist ein Diagramm eines Quantencircuits für den gesamten Algorithmus bei $n=7$ und $t=3$. Für größere Werte von $t$ können wir einfach weitere Instanzen der Grover-Operation unmittelbar vor den Messungen einfügen.

Anwendung auf die Suche

Grovers Algorithmus kann wie folgt auf das Such-Problem angewendet werden:

• Wähle die Zahl $t$ in Schritt 2. (Dies wird später in der Lektion besprochen.)
• Führe Grovers Algorithmus für die Funktion $f$ mit der gewählten Zahl $t$ aus, um eine Zeichenkette $x\in\Sigma^n$ zu erhalten.
• Frage die Funktion $f$ für die Zeichenkette $x$ ab, um zu prüfen, ob sie eine gültige Lösung ist:
  • Falls $f(x) = 1,$ haben wir eine Lösung gefunden und können aufhören und $x$ ausgeben.
  • Falls $f(x) = 0,$ können wir das Verfahren entweder erneut ausführen, möglicherweise mit einer anderen Wahl für $t$, oder wir können aufgeben und „keine Lösung" ausgeben.

Sobald wir analysiert haben, wie Grovers Algorithmus funktioniert, werden wir sehen, dass wir durch die Wahl $t = O(\sqrt{N})$ mit hoher Wahrscheinlichkeit eine Lösung für unser Suchproblem erhalten (sofern eine existiert).