Klassische Berechnungen auf Quantencomputern

Wir wenden uns nun der Implementierung klassischer Algorithmen auf Quantencomputern zu. Wir werden sehen, dass jede Berechnung, die mit einem klassischen Booleschen Circuit durchgeführt werden kann, auch von einem Quantencircuit mit ähnlichen asymptotischen Berechnungskosten durchgeführt werden kann. Darüber hinaus kann dies auf eine „saubere" Weise geschehen, die gleich beschrieben wird und eine wichtige Voraussetzung für die Verwendung dieser Berechnungen als Unterroutinen in größeren Quantenberechnungen ist.

Simulation Boolescher Circuits mit Quantencircuits

Boolesche Circuits bestehen aus AND-, OR-, NOT- und FANOUT-Gates. Um Boolesche Circuits mit Quantencircuits zu simulieren, zeigen wir zunächst, wie jedes dieser vier Gates durch Quanten-Gates simuliert werden kann. Danach ist die Umwandlung eines gegebenen Booleschen Circuits in einen Quantencircuit eine einfache Angelegenheit: Gate für Gate simulieren. Dafür brauchen wir nur NOT-Gates, controlled-NOT-Gates und Toffoli-Gates – allesamt deterministische und unitäre Operationen.

Toffoli-Gates

Toffoli-Gates können alternativ als controlled-controlled-NOT-Gates beschrieben werden, deren Wirkung auf Standard-Basiszustände in der folgenden Abbildung dargestellt ist.

Mit der Qiskit-Konvention im Hinterkopf, bei der die Qubits von oben nach unten in aufsteigender Bedeutung geordnet sind, lautet die Matrixdarstellung dieses Gates wie folgt.

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Eine andere Sichtweise auf Toffoli-Gates ist, dass sie im Wesentlichen Abfrage-Gates für die AND-Funktion sind, in dem Sinne, dass sie dem Muster folgen, das wir in der vorherigen Lektion für unitäre Abfrage-Gate-Implementierungen beliebiger Funktionen mit binären Zeichenketten als Ein- und Ausgabe gesehen haben.

Toffoli-Gates sind nicht im zuvor besprochenen Standard-Gate-Satz enthalten, aber es ist möglich, ein Toffoli-Gate aus $H$-, $T$-, $T^{\dagger}$- und CNOT-Gates wie folgt zu konstruieren.

Simulation Boolescher Gates mit Toffoli-, controlled-NOT- und NOT-Gates

Ein einzelnes Toffoli-Gate kann in Verbindung mit einigen NOT-Gates ein AND- und ein OR-Gate implementieren, und FANOUT-Gates lassen sich leicht mit controlled-NOT-Gates implementieren, wie die folgenden Diagramme zeigen.

In allen drei Fällen kommen die Qubits, auf die AND-, OR- und FANOUT-Gates wirken, von links als Eingaben, und für jedes Gate benötigen wir außerdem ein Hilfs-Qubit, das auf den Nullzustand initialisiert ist. Diese Hilfs-Qubits erscheinen innerhalb der Boxen, die die Gate-Implementierungen darstellen, um anzudeuten, dass sie neu sind und daher zu den Kosten dieser Implementierungen gehören.

Bei den AND- und OR-Gates haben wir neben dem Ausgabe-Qubit auch zwei weitere Qubits übrig. Zum Beispiel befinden sich innerhalb der Box im Diagramm, die die Simulation eines AND-Gates darstellt, die beiden oberen Qubits in den Zuständen $\vert a\rangle$ und $\vert b\rangle$. Diese Qubits werden als innerhalb der Boxen verbleibend dargestellt, da sie nicht mehr benötigt werden und nicht Teil der Ausgabe sind. Sie können zunächst ignoriert werden, obwohl wir uns bald wieder mit ihnen befassen werden.

Das verbleibende Boolesche Gate, das NOT-Gate, ist in unserem Standard-Satz von Quanten-Gates enthalten, sodass wir dafür keine Simulation benötigen.

Gate-für-Gate-Simulation Boolescher Circuits

Nehmen wir nun an, wir haben einen gewöhnlichen Booleschen Circuit namens $C$, der aus AND-, OR-, NOT- und FANOUT-Gates besteht und $n$ Eingabebits sowie $m$ Ausgabebits hat. Sei $t = \operatorname{size}(C)$ die Anzahl der Gates in $C$, und nennen wir die von $C$ berechnete Funktion $f$, die die Form

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

für $\Sigma = \{0,1\}$ hat.

Betrachten wir nun, was passiert, wenn wir die AND-, OR- und FANOUT-Gates von $C$ nacheinander durchgehen und jedes durch die entsprechende oben beschriebene Simulation ersetzen, einschließlich der Hinzufügung der erforderlichen Hilfs-Qubits. Nennen wir den resultierenden Circuit $R$ und ordnen die Qubits von $R$ so, dass die $n$ Eingabebits von $C$ den oberen $n$ Qubits von $R$ entsprechen und die Hilfs-Qubits unten sind.

Hierbei ist $k$ die Anzahl der erforderlichen Hilfs-Qubits – eines für jedes AND-, OR- und FANOUT-Gate von $C$ – und $g$ ist eine Funktion der Form $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$, die die Zustände der übrig gebliebenen Qubits beschreibt, die durch die Gate-Simulationen nach dem Ausführen von $R$ entstehen. In der Abbildung befinden sich die Qubits, die der Ausgabe $f(x)$ entsprechen, oben und die verbleibenden, übrig gebliebenen Qubits, die $g(x)$ speichern, unten. Wir können das erzwingen, wenn wir möchten, indem wir die Qubits mithilfe von SWAP-Gates umordnen, die mit drei controlled-NOT-Gates wie folgt implementiert werden können:

Wie wir im nächsten Abschnitt sehen werden, ist es nicht unbedingt notwendig, die Ausgabe-Qubits umzuordnen, aber es ist einfach genug zu tun, wenn wir es möchten.

Die Funktion $g$, die die klassischen Zustände der übrig gebliebenen Qubits beschreibt, wird durch den Circuit $C$ bestimmt, aber wir müssen uns nicht allzu viel darum kümmern, in welchem Zustand sich diese Qubits am Ende der Berechnung befinden. Der Buchstabe $g$ folgt im Alphabet auf $f$, was ein vernünftiger Name ist – aber es gibt einen besseren Grund, den Namen $g$ zu wählen: er steht für Garbage (Abfall).

Bereinigung des Abfalls

Wenn wir nur daran interessiert sind, die von einem gegebenen Booleschen Circuit $C$ berechnete Funktion $f$ mit einem Quantencircuit auszuwerten, müssen wir nicht weiter gehen als die soeben beschriebene Gate-für-Gate-Simulation. Das bedeutet, dass wir neben der Funktionsausgabe auch einen Haufen Abfall übrig behalten.

Dies reicht jedoch nicht aus, wenn wir klassische Berechnungen als Unterroutinen in größeren Quantenberechnungen verwenden wollen, denn diese Abfall-Qubits verursachen Probleme. Das Phänomen der Interferenz ist für Quantenalgorithmen von entscheidender Bedeutung, und Abfall-Qubits können die Interferenzmuster zerstören, die für das Funktionieren von Quantenalgorithmen notwendig sind.

Glücklicherweise ist es nicht schwer, den Abfall zu beseitigen. Der Schlüssel liegt darin, die Tatsache zu nutzen, dass wir $R$, da es sich um einen Quantencircuit handelt, rückwärts ausführen können, indem wir jedes Gate durch seine Inverse ersetzen und sie in umgekehrter Reihenfolge anwenden, wodurch wir einen Quantencircuit für die Operation $R^{\dagger}$ erhalten. Toffoli-Gates, CNOT-Gates und NOT-Gates sind tatsächlich ihre eigenen Inversen, sodass das Rückwärtsausführen von $R$ wirklich nur eine Frage der Anwendung der Gates in umgekehrter Reihenfolge ist – aber im Allgemeinen kann jeder Quantencircuit wie soeben beschrieben umgekehrt werden.

Konkret können wir $m$ weitere Qubits hinzufügen (unter Berücksichtigung, dass die Funktion $f$ $m$ Ausgabebits hat), CNOT-Gates verwenden, um die Ausgabe von $R$ auf diese Qubits zu kopieren, und $R$ umkehren, um den Abfall zu beseitigen. Die folgende Abbildung zeigt den resultierenden Circuit und beschreibt seine Wirkung auf Standard-Basiszustände.

Wenn wir eine Box um den gesamten Circuit legen und ihn $Q$ nennen, sieht er so aus:

Da $C$ $t$ Gates hat, wird der Circuit $Q$ $O(t)$ Gates haben.

Wenn wir die $k$ zusätzlichen Hilfs-Qubits außer Acht lassen, haben wir einen Circuit $Q$, der genau wie ein Abfrage-Gate für die Funktion $f$ funktioniert. Wenn wir die Funktion $f$ für eine Zeichenkette $x$ berechnen wollen, können wir $y = 0^m$ setzen, und der resultierende Wert $f(x)$ erscheint auf den unteren $m$ Qubits – oder wir können einen anderen Zustand in die unteren $m$ Qubits einspeisen, wenn wir möchten (vielleicht um einen Phase-Kickback zu nutzen, wie bei Deutschs oder dem Deutsch-Jozsa-Algorithmus).

Das bedeutet, dass wir für jeden Abfragealgorithmus, wenn wir einen Booleschen Circuit haben, der die Eingabefunktion berechnet, jedes Abfrage-Gate durch eine Circuit-Implementierung ersetzen können, und der Abfragealgorithmus wird korrekt funktionieren.

Beachte, dass die Hilfs-Qubits notwendig sind, damit dieser Prozess funktioniert, aber sie werden nach der Ausführung des kombinierten Circuits in ihre Ausgangszustände zurückversetzt. Dadurch können diese Qubits erneut als Hilfs-Qubits für andere Zwecke verwendet werden. Es gibt auch bekannte Strategien, um die Anzahl der benötigten Hilfs-Qubits zu reduzieren (was auf Kosten größerer Circuits geht), aber wir werden diese Strategien hier nicht besprechen.

Implementierung invertierbarer Funktionen

Die soeben beschriebene Konstruktion ermöglicht es uns, jeden Booleschen Circuit auf abfallfreie Weise mit einem Quantencircuit zu simulieren. Wenn $C$ ein Boolescher Circuit ist, der eine Funktion $f:\Sigma^n \rightarrow \Sigma^m$ implementiert, erhalten wir einen Quantencircuit $Q$, der auf Standard-Basiszuständen wie folgt wirkt.

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

Die Zahl $k$ gibt an, wie viele Hilfs-Qubits insgesamt benötigt werden. Dies ist für die Zwecke dieses Kurses ausreichend, aber es ist möglich, diese Methodik einen Schritt weiter zu treiben, wenn die Funktion $f$ selbst invertierbar ist.

Genauer gesagt, nehmen wir an, dass die Funktion $f$ die Form $f:\Sigma^n \rightarrow \Sigma^n$ hat, und nehmen wir außerdem an, dass eine Funktion $f^{-1}$ existiert, sodass $f^{-1}(f(x)) = x$ für jedes $x\in\Sigma^n$ gilt (die bei Existenz notwendigerweise eindeutig ist). Das bedeutet, dass die Operation, die $\vert x \rangle$ für jedes $x\in\Sigma^n$ in $\vert f(x) \rangle$ transformiert, unitär ist. Daher könnten wir hoffen, einen Quantencircuit zu konstruieren, der die durch

$$U \vert x \rangle = \vert f(x) \rangle$$

für jedes $x\in\Sigma^n$ definierte unitäre Operation implementiert.

Um klar zu sein: Die Tatsache, dass dies eine unitäre Operation ist, beruht darauf, dass $f$ invertierbar ist – sie ist nicht unitär, wenn $f$ nicht invertierbar ist. Abgesehen von den Hilfs-Qubits unterscheidet sich $U$ von der Operation, die der Circuit $Q$ implementiert, weil wir keine Kopie der Eingabe aufbewahren und mit einer beliebigen Zeichenkette XOR-verknüpfen, sondern $x$ durch $f(x)$ ersetzen.

Die Frage ist: Wenn $f$ invertierbar ist, können wir das tun?

Die Antwort ist ja, vorausgesetzt, wir dürfen Hilfs-Qubits verwenden und haben neben einem Booleschen Circuit, der $f$ berechnet, auch einen, der $f^{-1}$ berechnet. Das ist also keine Abkürzung für die rechnerische Invertierung von Funktionen, wenn wir nicht bereits wissen, wie das geht! Das folgende Diagramm zeigt, wie es durch die Komposition zweier Quantencircuits $Q_f$ und $Q_{f^{-1}}$ erfolgen kann, die individuell für die Funktionen $f$ und $f^{-1}$ nach der oben beschriebenen Methode erhalten werden, zusammen mit $n$ SWAP-Gates, wobei $k$ das Maximum der Anzahlen der von $Q_f$ und $Q_{f^{-1}}$ benötigten Hilfs-Qubits ist.