Circuits

In der Informatik sind Circuits Berechnungsmodelle, bei denen Information über Drähte durch ein Netz von Gates geleitet wird, die Operationen auf der durch die Drähte transportierten Information darstellen. Quantum Circuits sind ein spezifisches Berechnungsmodell, das auf diesem allgemeineren Konzept basiert.

Obwohl das Wort „Circuit" oft auf einen Kreisweg hindeutet, sind Kreispfade in den am häufigsten untersuchten Berechnungsmodellen tatsächlich nicht erlaubt. Das heißt, wir betrachten üblicherweise azyklische Circuits, wenn wir über Circuits als Berechnungsmodelle nachdenken. Quantum Circuits folgen diesem Muster; ein Quantum Circuit stellt eine endliche Folge von Operationen dar, die keine Rückkopplungsschleifen enthalten kann.

Boolesche Circuits

Hier ist ein Beispiel eines (klassischen) Booleschen Circuits, bei dem die Drähte binäre Werte tragen und die Gates boolesche Logikoperationen darstellen:

Der Informationsfluss entlang der Drähte verläuft von links nach rechts: Die Drähte auf der linken Seite der Abbildung, beschriftet mit $\mathsf{X}$ und $\mathsf{Y},$ sind Eingabebits, die jeweils auf einen beliebigen binären Wert gesetzt werden können, und der Draht auf der rechten Seite ist die Ausgabe. Die Zwischendrähte nehmen die Werte an, die durch die Gates bestimmt werden, welche von links nach rechts ausgewertet werden.

Die Gates sind AND-Gates (mit $\wedge$ gekennzeichnet), OR-Gates (mit $\vee$ gekennzeichnet) und NOT-Gates (mit $\neg$ gekennzeichnet). Die von diesen Gates berechneten Funktionen sind vielen Lesern vertraut, aber hier sind sie als Wertetabellen dargestellt:

$$\begin{array}{c} \begin{array}{c|c} a & \neg a\\ \hline 0 & 1\\ 1 & 0\\ \end{array}\\ \\ \\ \end{array} \qquad\quad \begin{array}{c|c} ab & a \wedge b\\ \hline 00 & 0\\ 01 & 0\\ 10 & 0\\ 11 & 1 \end{array} \qquad\quad \begin{array}{c|c} ab & a \vee b\\ \hline 00 & 0\\ 01 & 1\\ 10 & 1\\ 11 & 1 \end{array}$$

Die beiden kleinen ausgefüllten Kreise auf den Drähten direkt rechts von den Namen $\mathsf{X}$ und $\mathsf{Y}$ stellen Fan-out-Operationen dar, die einfach eine Kopie des auf dem Draht befindlichen Wertes erstellen und diesen Wert als Eingabe für mehrere Gates verfügbar machen. Fan-out-Operationen werden im klassischen Setting nicht immer als Gates betrachtet; manchmal werden sie behandelt, als ob sie in gewissem Sinne „kostenlos" wären. Wenn Boolesche Circuits in äquivalente Quantum Circuits umgewandelt werden, müssen Fan-out-Operationen jedoch explizit als Gates eingestuft werden, um sie korrekt zu handhaben und zu berücksichtigen.

Hier ist derselbe Circuit in einem in der Elektrotechnik gebräuchlicheren Stil dargestellt, der konventionelle Symbole für AND-, OR- und NOT-Gates verwendet:

Wir werden diesen Stil und diese Gate-Symbole im Weiteren nicht verwenden, aber wir werden verschiedene Symbole zur Darstellung von Gates in Quantum Circuits verwenden, die wir bei ihrer Einführung erklären werden.

Der hier gezeigte Circuit berechnet das exklusive ODER (kurz XOR), das durch das Symbol $\oplus$ bezeichnet wird:

$$\begin{array}{c|c} ab & a \oplus b\\ \hline 00 & 0\\ 01 & 1\\ 10 & 1\\ 11 & 0 \end{array}$$

Im nächsten Diagramm betrachten wir eine bestimmte Eingabe: $\mathsf{X}=0$ und $\mathsf{Y}=1.$ Jeder Draht ist mit dem Wert beschriftet, den er trägt, sodass du die Operationen verfolgen kannst. Der Ausgabewert ist in diesem Fall $1,$ was der korrekte Wert für das XOR ist: $0 \oplus 1 = 1.$

Die anderen drei möglichen Eingabebelegungen können auf ähnliche Weise überprüft werden.

Weitere Circuit-Typen

Wie oben angedeutet, ist das Konzept eines Circuits in der Informatik sehr allgemein. Zum Beispiel werden manchmal Circuits analysiert, deren Drähte andere Werte als $0$ und $1$ tragen, ebenso wie Gates, die andere Operationen darstellen.

In arithmetischen Circuits etwa können die Drähte ganzzahlige Werte tragen, während die Gates arithmetische Operationen wie Addition und Multiplikation darstellen. Die folgende Abbildung zeigt einen arithmetischen Circuit, der zwei variable Eingabewerte ($x$ und $y$) sowie eine dritte Eingabe mit dem festen Wert $1$ entgegennimmt. Die von den Drähten getragenen Werte als Funktionen von $x$ und $y$ sind in der Abbildung dargestellt.

Außerdem können Circuits betrachtet werden, die Zufälligkeit einbeziehen, etwa solche, bei denen Gates probabilistische Operationen darstellen.

Quantum Circuits

Im Quantum Circuit-Modell stellen Drähte Qubits dar und Gates Operationen auf diesen Qubits. Vorerst konzentrieren wir uns auf bisher behandelte Operationen, nämlich unitäre Operationen und Standard-Basismessungen. Wenn wir andere Arten von Quantenoperationen und -messungen kennenlernen, können wir unser Modell entsprechend erweitern.

Hier ist ein einfaches Beispiel eines Quantum Circuits:

In diesem Circuit haben wir ein einzelnes Qubit namens $\mathsf{X},$ das durch die horizontale Linie dargestellt wird, und eine Folge von Gates, die unitäre Operationen auf diesem Qubit darstellen. Genau wie in den obigen Beispielen verläuft der Informationsfluss von links nach rechts – die erste durchgeführte Operation ist also eine Hadamard-Operation, die zweite eine $S$-Operation, die dritte eine weitere Hadamard-Operation und die letzte eine $T$-Operation. Die Anwendung des gesamten Circuits entspricht also der Komposition dieser Operationen, $T H S H,$ auf dem Qubit $\mathsf{X}.$

Manchmal möchte man die Eingangs- oder Ausgangszustände von Circuits explizit angeben. Wenn wir beispielsweise die Operation $T H S H$ auf den Zustand $\vert 0\rangle$ anwenden, erhalten wir den Zustand $\frac{1+i}{2}\vert 0\rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle.$ Dies kann wie folgt dargestellt werden:

Quantum Circuits beginnen oft mit allen auf $\vert 0\rangle$ initialisierten Qubits, wie es hier der Fall ist, aber es gibt auch Situationen, in denen die Eingabe-Qubits zunächst auf verschiedene Zustände gesetzt werden. Hier ist ein weiteres Beispiel eines Quantum Circuits, diesmal mit zwei Qubits:

Wie immer bezieht sich das mit $H$ beschriftete Gate auf eine Hadamard-Operation, während das zweite Gate eine controlled-NOT-Operation ist: Der ausgefüllte Kreis stellt das Kontroll-Qubit dar und der Kreis mit dem $\oplus$-Symbol das Ziel-Qubit.

Bevor wir diesen Circuit genauer betrachten und erklären, was er tut, müssen wir zunächst klären, wie Qubits in Quantum Circuits geordnet sind. Dies hängt mit der Konvention zusammen, die Qiskit für die Benennung und Anordnung von Systemen verwendet, die in der vorherigen Lektion kurz erwähnt wurde.

Qiskits Qubit-Reihenfolgekonvention für Circuits

In Qiskit hat das oberste Qubit in einem Circuit-Diagramm den Index $0$ und entspricht der rechtsstehenden Position in einem Qubit-Tupel (oder in einem String, kartesischen Produkt oder Tensorprodukt dieses Tupels), das zweitoberste Qubit hat den Index $1$ und entspricht der zweitrechtsstehenden Position in einem Tupel usw. Das unterste Qubit, das den höchsten Index hat, entspricht daher der linksstehenden Position in einem Tupel. Insbesondere werden die Qubits in einem $n$-Qubit-Circuit in Qiskit standardmäßig durch das $n$-Tupel $(\mathsf{q_{n-1}},\ldots,\mathsf{q_{0}})$ benannt, wobei $\mathsf{q_{0}}$ das Qubit oben und $\mathsf{q_{n-1}}$ das Qubit unten in Quantum Circuit-Diagrammen ist.

Beachte, dass dies eine Umkehrung einer gebräuchlicheren Konvention zur Reihenfolge von Qubits in Circuits ist und häufig zu Verwirrung führt. Weitere Informationen zu dieser Reihenfolgekonvention findest du auf der Dokumentationsseite Bit-ordering in Qiskit.

Obwohl wir manchmal von den in Qiskit verwendeten Standardnamen $\mathsf{q_{0}},\ldots,\mathsf{q_{n-1}}$ abweichen, folgen wir in diesem Kurs stets der oben beschriebenen Reihenfolgekonvention bei der Interpretation von Circuit-Diagrammen. Unsere Interpretation des obigen Circuits ist daher, dass er eine Operation auf einem Qubit-Paar $(\mathsf{X},\mathsf{Y})$ beschreibt. Wenn die Eingabe des Circuits ein Quantenzustand $\vert\psi\rangle \otimes \vert\phi\rangle$ ist, bedeutet das zum Beispiel, dass das untere Qubit $\mathsf{X}$ im Zustand $\vert\psi\rangle$ und das obere Qubit $\mathsf{Y}$ im Zustand $\vert\phi\rangle$ beginnt.

Um zu verstehen, was der Circuit tut, gehen wir seine Operationen von links nach rechts durch.

1. Die erste Operation ist eine Hadamard-Operation auf $\mathsf{Y}$:

   

   Wenn ein Gate auf ein einzelnes Qubit angewendet wird, passiert mit den anderen Qubits nichts (in diesem Fall ist es nur ein weiteres Qubit). Nichts zu tun entspricht der Identitätsoperation. Das gepunktete Rechteck in der obigen Abbildung stellt daher diese Operation dar:

   $$\mathbb{I}\otimes H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0\\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & 0\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix}.$$

   Beachte, dass die Einheitsmatrix links im Tensorprodukt steht und $H$ rechts, was der Reihenfolgekonvention von Qiskit entspricht.

2. Die zweite Operation ist die controlled-NOT-Operation, wobei $\mathsf{Y}$ das Kontroll-Qubit und $\mathsf{X}$ das Ziel-Qubit ist:

   

   Die Wirkung des controlled-NOT-Gates auf Standard-Basiszustände ist wie folgt:

   

   Da wir die Qubits als $(\mathsf{X}, \mathsf{Y})$ anordnen, wobei $\mathsf{X}$ unten und $\mathsf{Y}$ oben in unserem Circuit ist, lautet die Matrixdarstellung des controlled-NOT-Gates wie folgt:

   $$\begin{pmatrix} 1 & 0 & 0 & 0\\[2mm] 0 & 0 & 0 & 1\\[2mm] 0 & 0 & 1 & 0\\[2mm] 0 & 1 & 0 & 0 \end{pmatrix}.$$

Die durch den gesamten Circuit implementierte unitäre Operation, die wir $U$ nennen, ist die Komposition der Operationen:

$$U = \begin{pmatrix} 1 & 0 & 0 & 0\\[2mm] 0 & 0 & 0 & 1\\[2mm] 0 & 0 & 1 & 0\\[2mm] 0 & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0\\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & 0\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix} = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & 0 \end{pmatrix}.$$

Unter Berücksichtigung unserer Notation für die Bell-Zustände,

$$\begin{aligned} \vert \phi^+ \rangle & = \frac{1}{\sqrt{2}} \vert 0 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 1 \rangle \\[2mm] \vert \phi^- \rangle & = \frac{1}{\sqrt{2}} \vert 0 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 1 \rangle \\[2mm] \vert \psi^+ \rangle & = \frac{1}{\sqrt{2}} \vert 0 1 \rangle + \frac{1}{\sqrt{2}} \vert 1 0 \rangle \\[2mm] \vert \psi^- \rangle & = \frac{1}{\sqrt{2}} \vert 0 1 \rangle - \frac{1}{\sqrt{2}} \vert 1 0 \rangle, \end{aligned}$$

ergibt sich:

$$\begin{aligned} U \vert 00\rangle & = \vert \phi^+\rangle\\ U \vert 01\rangle & = \vert \phi^-\rangle\\ U \vert 10\rangle & = \vert \psi^+\rangle\\ U \vert 11\rangle & = -\vert \psi^-\rangle. \end{aligned}$$

Dieser Circuit gibt uns also eine Möglichkeit, den Zustand $\vert\phi^+\rangle$ zu erzeugen, wenn wir ihn auf zwei Qubits anwenden, die auf $\vert 00\rangle$ initialisiert sind. Allgemeiner gesagt bietet er uns eine Möglichkeit, die Standardbasis in die Bell-Basis umzurechnen. (Beachte, dass der Phasenfaktor $-1$ beim letzten Zustand, $-\vert \psi^-\rangle,$ durch eine kleine Ergänzung des Circuits eliminiert werden könnte, falls gewünscht. Man könnte zum Beispiel am Anfang ein controlled-$Z$-Gate hinzufügen, das einem controlled-NOT-Gate ähnelt, außer dass eine $Z$-Operation auf das Ziel-Qubit angewendet wird, anstatt einer NOT-Operation, wenn das Kontroll-Qubit $1$ ist. Alternativ könnte man am Ende ein Swap-Gate hinzufügen. Beide Optionen eliminieren das Minuszeichen, ohne die Wirkung des Circuits auf die anderen drei Standard-Basiszustände zu beeinflussen.)

Im Allgemeinen können Quantum Circuits eine beliebige Anzahl von Qubit-Drähten enthalten. Wir können auch klassische Bit-Drähte einbeziehen, die durch doppelte Linien angezeigt werden, wie in diesem Beispiel:

Hier haben wir ein Hadamard-Gate und ein controlled-NOT-Gate auf zwei Qubits $\mathsf{X}$ und $\mathsf{Y},$ genau wie im vorherigen Beispiel. Außerdem haben wir zwei klassische Bits, $\mathsf{A}$ und $\mathsf{B},$ sowie zwei Mess-Gates. Die Mess-Gates stellen Standard-Basismessungen dar: Die Qubits wechseln in ihren Zustand nach der Messung, während die Messergebnisse auf die klassischen Bits überschrieben werden, auf die die Pfeile zeigen.

Es ist oft praktisch, eine Messung als ein Gate darzustellen, das ein Qubit als Eingabe nimmt und ein klassisches Bit ausgibt (anstatt das Qubit in seinem Zustand nach der Messung auszugeben und das Ergebnis in ein separates klassisches Bit zu schreiben). Das bedeutet, dass das gemessene Qubit verworfen wurde und danach sicher ignoriert werden kann, wobei sich sein Zustand je nach Messergebnis in $\vert 0\rangle$ oder $\vert 1\rangle$ geändert hat.

Das folgende Circuit-Diagramm stellt zum Beispiel denselben Prozess wie das vorherige dar, aber wir ignorieren $\mathsf{X}$ und $\mathsf{Y}$ nach ihrer Messung:

Im weiteren Verlauf des Kurses werden wir weitere Beispiele von Quantum Circuits kennenlernen, die in der Regel komplexer sind als die einfachen obigen Beispiele. Hier sind einige Beispiele für Symbole, die zur Bezeichnung von Gates verwendet werden, die häufig in Circuit-Diagrammen vorkommen:

• Einzelqubit-Gates werden im Allgemeinen als Quadrate mit einem Buchstaben dargestellt, der die Operation angibt, wie hier:

  

  NOT-Gates (oder äquivalent $X$-Gates) werden manchmal auch durch einen Kreis um ein Pluszeichen dargestellt:

  

• Swap-Gates werden wie folgt dargestellt:

  

• Controlled-Gates, also Gates, die controlled-unitäre Operationen beschreiben, werden durch einen ausgefüllten Kreis (der das Kontroll-Qubit anzeigt) dargestellt, der durch eine senkrechte Linie mit der gesteuerten Operation verbunden ist. Zum Beispiel werden controlled-NOT-Gates, controlled-controlled-NOT-Gates (oder Toffoli-Gates) und controlled-Swap-Gates (Fredkin-Gates) wie folgt dargestellt:

  

• Beliebige unitäre Operationen auf mehreren Qubits können als Gates betrachtet werden. Sie werden durch Rechtecke dargestellt, die mit dem Namen der unitären Operation beschriftet sind. Hier ist zum Beispiel eine Darstellung einer (nicht näher spezifizierten) unitären Operation $U$ als Gate zusammen mit einer kontrollierten Version dieses Gates: