Quantencomputer für Angeber

In ein paar Jahren dürfte es soweit sein, dass die ersten Quantencomputer einsatzbereit sind. Während aktuell hauptsächlich Physiker mit der Quantentechnologie arbeiten werden dann auch erste Informatiker anfangen Algorithmen für die neue Technologie zu schreiben.

Aktuelle Programmiersprachen wie QASM sind sehr schlicht aufgebaut und erlauben nur rudimentäre Operationen. Dies ist nicht verwunderlich, da technisch noch nicht viel mehr realisiert werden kann. Die Assembler ähnelnden Sprachen dürften bald von höheren Programmiersprachen abgelöst werden. Die Grundlagen für das Rechnen mit Qauantenbits (Qubits) dürften jedoch die selben bleiben und sollten daher von jedem Informatiker der sich mit diesem Thema beschäftigt im Ansatz verstanden werden.

Die hier gezeigten Beispiele basieren auf dem Buch Quantum Computing verstehen von Matthias Homeister. Wer nicht nur damit angeben möchte sondern sich wirklich für Quantencomputer interessiert sollte sich dieses Buch als Einsteigerhilfe zulegen.

Qubit

Ein Qubit beschreibt in der Quantenmechanik die kleinste Einheit. Wie ein herkömmliches Bit kann auch ein Qubit die Zustände 1 und 0 annehmen. Dies basiert beispielsweise auf Polarisation oder dem Spin eines Teilchens. Das Qubit wird dabei in der Dirac-Notation $\ket{0}$ und $\ket{1}$ aufgeschrieben. Anders als ein herkömmliches Bit kann das Qubit beide Zustände gleichzeitig annehmen.

(1) $\begin{gather*} \alpha \ket{0} + \beta \ket{1} \end{gather*}$

Die komplexen Zahlen $\alpha$ und $\beta$ beschreiben die Wahrscheinlichkeit des jeweiligen Zustands und werden als Amplitude bezeichnet. Für die Amplituden gilt, dass die Summe ihrer Quadrate den Wert 1 ergeben muss.

(2) $\begin{gather*} |\alpha|^2 + |\beta|^2 = 1 \end{gather*}$

Ein Qubit in dem Zustand $\frac{1}{\sqrt{2}} \ket{0} + \frac{1}{\sqrt{2}} \ket{1}$ ist gleichermaßen im Zustand $\ket{0}$ und $\ket{1}$ , da für beide Zustände $|\frac{1}{\sqrt{2}}|^2 = \frac{1}{2}$ gilt. Wird das Qubit gemessen, so wird einer dieser Zustände mit der entsprechenden Wahrscheinlichkeit angenommen. Wichtig dabei ist, dass sich das Qubit bis zu dieser Messung tatsächlich in beiden Zuständen gleichzeitig befindet. Diese Überlagerung beider Zustände wird als Superposition bezeichnet.

Um die Arbeitsweise eines Quantencomputers zu verstehen und mit Superpositionen arbeiten zu können werden die Qubits als Basisvektoren angegeben mit der Basis { $\ket{0}$ , $\ket{1}$ }.

(3) $\begin{gather*}\ket{0} \doteq \begin{pmatrix} 1\\0 \end{pmatrix},\ket{1} \doteq \begin{pmatrix} 0\\1 \end{pmatrix}\end{gather*}$

Eine Superposition ergibt sich aus der Linearkombination der Basisvektoren.

(4) $\begin{gather*}\alpha \ket{0} + \beta \ket{1} \doteq \alpha \begin{pmatrix}1\\ 0 \end{pmatrix}+ \beta \begin{pmatrix}0\\ 1 \end{pmatrix}=\begin{pmatrix} \alpha\\ \beta \end{pmatrix} \end{gather*}$

Der Vorteil des Qubit im Vergleich zum herkömmlichen Bit liegt in seiner Superposition. Wird der Zustand des Qubits gemessen zerfällt diese Superposition und einer der Basiszustände wird angenommen. Um die Superposition zu erhalten darf das Qubit daher nicht gemessen werden. Klassische Rechenoperationen wie mit einem Bit sind mit einem Qubit daher nicht möglich. Um auf einem Qubit zu arbeiten werden quadratische 2×2-Matrizen der Form

(5) $\begin{gather*}A =\begin{pmatrix} a & b\\ c & d \end{pmatrix}\end{gather*}$

benötigt. Mit diesen Matrizen lässt sich das Qubit transformieren ohne seinen Zustand zu messen. Durch geschickten Einsatz mehrerer Qubits und Matrizen lassen sich die Qubits so verändern, dass diese Rechenoperationen durchführen können. Die manipulation dieser Qubits geschieht in der Realität durch Mikrowellen welche auf das Qubit geschossen werden. Ohne den Zustand des Qubits zu messen kann dieser dadurch manipuliert werden. Eine mögliche Superposition bleibt dabei erhalten.

Die erwähnten Matrizen müssen unitär sein. Unitär heißt, dass eine konjungiert komplexe und transponierte Matrix ihre inverse $(A^*)^T=A^{-1}$ ergibt. Mit sich selber multipliziert ergibt sich die Einheitsmatrix $I_2$ .

(6) $\begin{gather*}(A^*)^T A = A^{-1}A =I_2 = \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix} \end{gather*}$

Quantengatter

Die wahrscheinlich wichtigste unitäre Matrix ist die Hadamard-Matrix $H$ . In dem Bereich des Quantencomputers werden diese 2×2-Matrizen auch Gatter genannt, da die Matrizen selbst nur mathematische Hilfsmittel darstellen. Die Hadamard-Matrix wird daher auch Hadamard-Gatter genannt.

(7) $\begin{gather*}H = \begin{pmatrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix} \end{gather*}$

Das Hadamard-Gatter überführt ein Qubit, wie beispielsweise $\ket{0}$ , in eine Superposition mit gleich großen Amplituden. Um eine Matrix auf den Vektor eines Qubit anzuwenden wird eine simple Matrix-Multiplikation durchgeführt.

(8) $\begin{gather*}\begin{split} H \ket{0} &\doteq \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}\begin{pmatrix} 1\\ 0 \end{pmatrix}\\&= \frac{1}{\sqrt{2}} \begin{pmatrix} 1\\ 1 \end{pmatrix}\\&= \frac{1}{\sqrt{2}} \begin{pmatrix} 0\\ 1 \end{pmatrix} + \frac{1}{\sqrt{2}} \begin{pmatrix} 1\\ 0 \end{pmatrix} \\ &\doteq \frac{1}{\sqrt{2}} \ket{0} + \frac{1}{\sqrt{2}} \ket{1}\end{split} \end{gather*}$

Weitere dieser Gatter sind die Pauli-Matrizen, welche sich zusammensetzen aus der Pauli-X-Transformation (Bitflip), der Pauli-Y-Transformation und der Pauli-Z-Transformation (Phaseflip), welche häufig durch Buchstaben $X$ , $Y$ und $Z$ notiert werden.

(9) $\begin{gather*}\begin{split}&X = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}\\&Y = \begin{pmatrix} 0 & -i\\ i & 0 \end{pmatrix}\\ &Z = \begin{pmatrix} 1 & 0\\ 0 & -1 \end{pmatrix}\end{split}\end{gather*}$

Quantenregister

Mit einem Bit alleine lässt sich nicht viel anstellen. Wie bei herkömmlichen Rechnern ist auch bei einem Quantencomputer das Zusammenspiel mehrerer Bits entscheidend. Jedes Qubit kann dabei eine Superposition einnehmen.

Das klassische Register aus $n$ Bits kann $2^n$ verschiedene Zustände annehmen. Bei einem gebräuchlichen Register von 16 Bit können damit 65.536 verschiedene Zustände angenommen werden. Das Quantenregister kann durch seine Superposition alle diese Zustände gleichzeitig annehmen. Um diese Leistung zu erzielen bräuchte ein herkömmlicher Rechner also 65.536 x 16 Bit. Das wäre ein Register in der Größe von einem Megabit. So eine Größe ist selbst in weiter Zukunft unvorstellbar. Selbst mit einem Register von 64 Bit und 4 Kernen müsste ein herkömmlicher Rechner noch immer 4096 Operationen ausführen um eine einzige Operation eines Quantencomputers zu simulieren.

Das Einsatzgebiet dieser Operationen auf Superpositionen ist natürlich sehr beschränkt. In den meisten Fällen möchte man mit dem Ergebnis der letzten Operation weiterrechnen und interessiert sich nicht dafür, was passiert wäre, wenn die Rechnung mit einer anderen Zahl durchgeführt worden wäre. In seltenen Fällen ist die Superposition dennoch hilfreich. Bei einer verschlüsselten Datei beispielsweise könnten so alle möglichen Passwörter gleichzeitig getestet werden.

Um zwei Qubits $\ket{x}$ und $\ket{y}$ zu einem Register zusammenzufügen müssen diese Ausmultipliziert werden.

(10) $\begin{gather*}\ket{x} = x_0 \ket{0} + x_1 \ket{1} \\\ket{y} = y_0 \ket{0} + y_1 \ket{1}\end{gather*}$

(11) $\begin{gather*}\begin{split}\ket{x} \ket{y} &= (x_0 \ket{0} + x_1 \ket{1} ) ( y_0 \ket{0} + y_1 \ket{1} ) \\&= x_0 y_0 \ket{0} \ket{0} + x_0 y_1 \ket{0} \ket{1} + x_1 y_0 \ket{1} \ket{0} + x_1 y_1 \ket{1} \ket{1}\end{split}\end{gather*}$

Aus vier Amplituden der Superpositionen werden paarweise multiplizierte Amplituden mit den entsprechenden Zuständen $\ket{0} \ket{0}$ , $\ket{0} \ket{1}$ , $\ket{1} \ket{0}$ und $\ket{1} \ket{1}$ . Auch für diese Amplituden gilt, dass die Summe ihrer Quadrate 1 ergeben muss.

(12) $\begin{gather*}\sum_{i,j} x_i y_j = 1\end{gather*}$

Die vier neuen Zustände, welche aus den beiden Qubits resultieren können ebenfalls als Basisvektoren betrachtet werden. Dazu werden sie durch das Tensorprodukt vereint. In den hier vorgestellten Beispielen kann jedoch auf das Kronecker-Produkt zurückgegriffen werden. Dieses lässt sich bildlich sehr einfach darstellen und nachvollziehen. Einfach ausgedrückt wird das Kronecker-Produkt zweier Matrizen dadurch gebildet, dass die Elemente der ersten Matrix durch die gesamte zweite Matrix ersetzt werden. Alle inneren Elemente werden zudem mit dem Wert des Elements der ersten Matrix multipliziert.

(13) $\begin{gather*}\begin{split}&A = \begin{pmatrix}a_1 & a_2\\a_3 & a_4\end{pmatrix} \\&B = \begin{pmatrix}b_1 & b_2\\ b_3 & b_4\end{pmatrix}\end{split}\end{gather*}$

(14) $\begin{gather*}\begin{split}&A \otimes B = \begin{pmatrix} a_1 B & a_2 B\\ a_3 B & a_4 B \end{pmatrix}= \begin{pmatrix} a_1 \begin{pmatrix} b_1 & b_2\\b_3 & b_4\end{pmatrix} & a_2 \begin{pmatrix} b_1 & b_2\\b_3 & b_4\end{pmatrix} \\ a_3 \begin{pmatrix} b_1 & b_2\\b_3 & b_4\end{pmatrix} & a_4 \begin{pmatrix} b_1 & b_2\\b_3 & b_4\end{pmatrix} \end{pmatrix} = \begin{pmatrix} a_1 b_1 & a_1 b_2 & a_2 b_1 & a_2 b_2\\ a_1 b_3 & a_1 b_4 & a_2 b_3 & a_2 b_4\\ a_2 b_1 & a_2 b_2 & a_4 b_1 & a_4 b_2\\ a_2 b_3 & a_2 b_4 & a_4 b_3 & a_4 b_4\\ \end{pmatrix}\end{split}\end{gather*}$

Mit dem Kronecker-Produkt lassen sich einzelne Qubits verbinden.

(15) $\begin{gather*}\ket{1} \ket{0} \doteq \begin{pmatrix} 0 \\ 1 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}\end{gather*}$

Anstelle von $\ket{1} \ket{0}$ kann vereinfacht auch $\ket{10}$ geschrieben werden. Für die Basis { $\ket{00}$ , $\ket{01}$ , $\ket{10}$ , $\ket{11}$ } ergeben sich folgende Einheitsvektoren:

(16) $\begin{gather*}\ket{00} \doteq \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix},\ket{01} \doteq \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}, \ket{10} \doteq \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \ket{11} \doteq \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \end{gather*}$

Eine Superposition des gesamten Registers kann hergestellt werden, indem jedes Qubit über die Hadamard-Matrix transformiert wird.

(17) $\begin{gather*}\begin{split}H \ket{0} H \ket{0} &= \left ( \frac{1}{\sqrt{2}} \ket{0} + \frac{1}{\sqrt{2}} \ket{1} \right ) \left ( \frac{1}{\sqrt{2}} \ket{0} + \frac{1}{\sqrt{2}} \ket{1} \right ) \\&= \frac{1}{2} \ket{00} + \frac{1}{2} \ket{01} + \frac{1}{2} \ket{10} + \frac{1}{2} \ket{11}\end{split}\end{gather*}$

Falls eine Matrix $A$ auf dem Vektorraum $V$ agiert und Matrix $B$ auf dem Vektorraum $W$ , dann gilt:

(18) $\begin{gather*}(A v) \otimes (B w) = (A \otimes B)(v \otimes w)\end{gather*}$

Die Formel $H \ket{0} H \ket{0}$ kann somit umgestellt werden zu $H \otimes H \ket{00}$ .

(19) $\begin{gather*}\begin{split}H_2 \ket{00} = H \otimes H \ket{00} &\doteq \frac{1}{\sqrt{2}}\begin{pmatrix} H & H \\ H & -H \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \\&= \frac{1}{2}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \\&= \frac{1}{2} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} \\&= \frac{1}{2} \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} +\frac{1}{2} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} +\frac{1}{2} \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} +\frac{1}{2} \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \\& \doteq \frac{1}{2} \ket{00} + \frac{1}{2} \ket{01} + \frac{1}{2} \ket{10} + \frac{1}{2} \ket{11} \end{split} \end{gather*}$

Durch die Berechnung mit Vektoren ergibt sich das gleiche Ergebnis, welches weiter oben durch Ausmultiplizieren berechnet wurde. Wichtig dabei ist, dass die jewiligen Matrizen auf dem zugehörigen Vektorraum agieren müssen. Möchten wir beispielsweise für den Zustand $\ket{000}$ das erste und dritte bit mit der Hadarmard-Matrix $H$ transformieren, das zweite jedoch beibehalten, so muss die Identitätsmatrix $I_2$ für das zweite Qubit angewandt werden damit die Dimensionen wieder passen. Die Transformationmatrix berechnet sich dann aus $H \otimes I_2 \otimes H$ .

Gesteuerte Quantengatter

Das simpelste Schaltnetz, dass ein Computer benötigt um rechnen zu können ist der Halbaddierer. Dieser setzt sich aus einem XOR-Gatter und einem AND-Gatter zusammen. Auch der Quantencomputer braucht diese Gatter. Sie werden realisiert durch einen zusätzlichen Eingang, mit dem es möglich ist ein inneres Gatter zu steuern.

Bei dem gesteuerten Gatter wird eine Operation $U$ auf Eingang $b$ ausgeführt, sofern das Qubit an Eingang $a$ aktiv ist. Das gesteuerte Gatter lässt sich durch eine 4×4-Matrix beschreiben.

(20) $\begin{gather*}\begin{pmatrix}\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} &\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix} \\ \begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix} & U\end{pmatrix}\end{gather*}$

Da Quantengatter mathematisch durch unitäre Matrizen beschrieben werden, welche die Dimension des Vektors bei einer Operation beibehalten muss bei der bildlichen Darstellung des Schaltkreises darauf geachtet werden, dass die gleiche Anzahl an Ein- und Ausgängen existiert. Ein zusätzliches Bit kann in einem Schaltkreis weder erzeugt werden, noch verschwinden. Auch eine Verzweigung ist nicht möglich. Eingang $a$ wird daher unverändert auf Ausgang $a$ gelegt.

Wird das gesteuerte Gatter auf den Bitflip $X$ angewandt, so erhält man ein XOR-Gatter, das explizite Oder. Dieses Gatter ist als CNOT (Controlled NOT) bekannt.

(21) $\begin{gather*}CNOT = \begin{pmatrix}1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 \\0 & 0 & 0 & 1 \\0 & 0 & 1 & 0\end{pmatrix} \end{gather*}$

Mit dem CNOT-Gatter lassen sich durch geschicktes Hintereinanderschalten bereits alle wichtigen Operationen realisieren. Es gibt jedoch noch ein weiteres Gatter welches Operationen wie AND erheblich vereinfacht. Das Toffoli-Gatter $T$ . Um das Toffoli-Gatter zu erzeugen wird das CNOT-Gatter erneut in ein gesteuertes Gatter gepackt.

(22) $\begin{gather*}T = \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 & 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 & 1 \\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\end{pmatrix} \end{gather*}$

Legt man Eingang $b$ und $c$ auf 1, so ist der Ausgang ein negiertes $a$ .

(23) $\begin{gather*}(a \wedge 1) \oplus 1 = \bar{a}\end{gather*}$

Wird der Eingang $c$ auf 0 gesetzt, so lassen sich $a$ und $b$ zu einem Und zusammenfassen.

(24) $\begin{gather*}(a \wedge b) \oplus 0 = (a \wedge b) \end{gather*}$

Mit dem Toffoli-Gatter ist es nun möglich auf einfache Weiße einen Halbaddierer zu konstruieren. Das Toffoli-Gatter muss dazu zu einem AND- und einem XOR-Gatter gemacht werden. Dies geschieht durch zwei Hilfsbits 1 und 0.

Möchten wir den dargestellten Schaltkreis mathematisch beschreiben benötigen wir für beide Operationen eine entsprechende Matrix. Das AND-Gatter bezieht sich auf das zweite, dritte und vierte Bit des Eingangsregisters $\ket{1ab0}$ und kombiniert diese mit dem ersten Toffoli-Gatter $T$ . Das erste Bit wird zunächst einfach nur durchgereicht. Aus diesem Grund wird auf das erste Bit die Identitätsmatrix $I_2$ angewandt. Die resultierende 16×16-Matrix ergibt sich aus $I_2 \otimes T$ . Für das XOR-Gatter ist dies genau umgekehrt und das vierte Bit wird durchgereicht $T \otimes I_2$ . Um das Ausgangsregister $\ket{1asc}$ zu berechnen wird das Eingangsregister nacheinander mit beiden Matrizen multipliziert.

(25) $\begin{gather*}\ket{1asc} = (T \otimes I_2)((I_2 \otimes T) \ket{1ab0})\end{gather*}$

Möchte man den nun einen Addierer erstellen, der zwei 4 Bit-Werte addiert, so benötigt man ein viel größeres Register. Das erste Bit 1 kann öfter verwendet werden, da sich im Verlauf der Berechnung sein Wert nicht ändert. Das vierte Bit, die 0 die zu dem Carry-Bit $c$ wird, benötigt man jedoch auch für die anderen Additionen. Für jeden zusätzlichen Bit-Wert der addiert werden soll, werden daher 3 zusätzliche Bit benötigt. Für 4 Bit-Werte ergibt sich ein Eingangsregister von $\ket{1a_1b_10a_2b_20a_3b_30a_4b_40}$ mit 13 Qubits. Bei den acht benötigten Matrizen handelt es sich dann jeweils um eine 8192×8192-Matrix. Würde ein normaler Rechner das simulieren müssen, so wäre das schon ein erheblicher Rechenaufwand nur um zwei 4-Bit-Werte zu addieren.

Auf dem Blatt Papier ist das ganze viel einfacher, da man oft durch genausen hinsehen erkennen kann, wie sich die Bits verhalten. Betrachten wir beispielsweise das Eingabe-Register $\ket{1110}$ für den Halbaddierer, so lässt sich leicht sagen, dass nach dem UND-Gatter das vierte Bit zu 1 wird $\ket{1111}$ und nach dem XOR-Gatter das dritte Bit zu 0 und wir als Ergebnis $\ket{1101}$ erhalten. Bei Superpositionen muss diese Logik auf jeden Zustand der Superpositionen einzeln angewandt werden.

Verschränkung

Wird ein Quantenbit gemessen, so wird die Superposition zerstört und das Messergebnis ist entweder $\ket{0}$ oder $\ket{1}$ . Betrachtet man nicht nur ein einziges Bit sondern ein ganzes Register, welches in eine Superposition überführt wurde, so treten Eigenschaften der Quantenmechanik auf, welche weitaus schwerer zu begreifen sind als ein bloßes Teilchen, welches sich in zwei Zuständen gleichzeitig befindet. Eine dieser Eigenschaften ist die Quantenverschränkung.

Betrachten wir hierzu den Basiszustand $\ket{00}$ und wenden auf das erste Bit die Hadamard-Matrix an und auf das gesamte Register im Anschluss das CNOT-Gatter.

(26) $\begin{gather*}\begin{split}CNOT ((H \otimes I) \ket{00}) &= CNOT (\frac{1}{\sqrt{2}}(\ket{0} + \ket{1})\ket{0}) \\ &= CNOT (\frac{1}{\sqrt{2}}(\ket{00} + \ket{10}) \\&= \frac{1}{\sqrt{2}}(\ket{00} + \ket{11} \end{split}\end{gather*}$

Das Quantenregister besitz nun zwei gleich wahrscheinliche Zustände $\ket{00}$ und $\ket{11}$ . Bei einer Messung können die Bits einen dieser beiden Zustände annehmen. Das interessante daran ist, dass dieser Zustand auch angenommen wird, wenn nur eines der beiden Qubits gemessen wird. Wird beispielsweise eine $\ket{0}$ für das erste Qubit gemessen, so kann davon völlig unabhängig das zweite Qubit gemessen werden und man würde auf jeden Fall $\ket{0}$ erhalten. Diese miteinander verschränkten Qubits werden als EPR-Paare bezeichnet, benannt nach den Wissenschaftlern Einstein, Podolsky und Rosen. Das Einstein-Podolsky-Rosen-Paradoxon ist eines der am häufigsten diskutierten Phänomene unter Physikern und lässt sich in einer Vielzahl von SiFi-Filmen und Büchern wieder finden.

Die entsprechenden Zustände der verschränkten Qubits werden als Bell-Zustände bezeichnet. Es gibt vier verschiedene Bell-Zustände.

(27) $\begin{gather*}\Phi^+= \frac{1}{\sqrt{2}}(\ket{00} + \ket{11}) \\\Phi^-= \frac{1}{\sqrt{2}}(\ket{00} - \ket{11}) \\\Psi^+= \frac{1}{\sqrt{2}}(\ket{01} + \ket{10}) \\\Psi^-= \frac{1}{\sqrt{2}}(\ket{10} - \ket{01})\end{gather*}$

Quantenteleportation

Ein Qubit zu kopieren ist nicht möglich. Es ist möglich ein Qubit zu messen, was zur Folge hat, dass seine Superposition zerstört wird. Es gibt jedoch keine Operation $U$ die ein Qubit $\ket{\phi }$ auf ein anderes Qubit $\ket{b}$ kopieren könnte.

(28) $\begin{gather*}U \ket{\phi b} = \ket{\phi \phi}\end{gather*}$

Diese Eigenschaft der Qubits wird als No-Cloning-Theorem bezeichnet.

Zwar kann ein Qubit nicht kopiert werden. Es ist jedoch möglich den Zustand eines Qubits auf ein anderes Qubit zu übertragen. Der Zustand des ursprünglichen Qubits wird damit zwar zerstört, das überschriebene Qubit muss sich für diesen Vorgang jedoch nicht am selben Ort wie das ursprüngliche Qubit befinden. Dieser Vorgang wird daher auch als Quantenteleportation beschrieben.

Der Grundgedanke ist schnell erklärt: Für die Teleportation werden zwei verschränkte Qubits benötigt. Eines davon erhält Alice $a$ , das andere Bob $b$ . Alice möchte daraufhin Bob den Zustand eines weiteren Qubit $\Psi$ zukommen lassen. Sie führt dazu eine Operation auf $a$ und $\Psi$ aus um herauszubekommen welche Aktion Bob ausführen muss um sein Qubit $b$ in $\Psi$ zu überführen.

(29) $\begin{gather*}\begin{split}\ket{\Psi a b} = \ket{\phi_0} &= (\alpha \ket{0} + \beta \ket{1}) \frac{1}{\sqrt{2}}(\ket{00} + \ket{11}) \\&= \frac{\alpha}{\sqrt{2}}(\ket{000} + \ket{011}) + \frac{\beta}{\sqrt{2}}(\ket{100} + \ket{111}) \\CNOT \otimes I_2 \ket{\phi_0} = \ket{\phi_1} &= \frac{\alpha}{\sqrt{2}}(\ket{000} + \ket{011}) + \frac{\beta}{\sqrt{2}} (\ket{110} + \ket{101}) \\H \otimes I_4 \ket{\phi_1} = \ket{\phi_2} &= \frac{\alpha}{\sqrt{2}} \left ( \frac{1}{\sqrt{2}} (\ket{0} + \ket{1}) \right ) (\ket{00} + \ket{11}) + \frac{\beta}{\sqrt{2}} \left ( \frac{1}{\sqrt{2}} (\ket{0} - \ket{1}) \right ) (\ket{10} + \ket{01}) \\& = \frac{\alpha}{2}(\ket{000} + \ket{011} + \ket{100} + \ket{111}) + \frac{\beta}{2} (\ket{010} + \ket{001} - \ket{110} - \ket{101}) \\&= \frac{1}{2} \left ( \ket{00}(\alpha \ket{0} + \beta \ket{1}) + \ket{01}(\alpha \ket{1} + \beta \ket{0}) + \ket{10}(\alpha \ket{0} - \beta \ket{1}) + \ket{11}(\alpha \ket{1} - \beta \ket{0}) \right )\end{split}\end{gather*}$

In dem hier gezeigten Beispiel hat das Qubit $\ket{\Psi}$ den Zustand $\alpha \ket{0} + \beta \ket{1}$ und soll auf $\ket{b}$ übertragen werden. Das verschränkte EPR-Paar $\ket{ab}$ befindet sich in dem Bell Zustand $\ket{\Phi^+} = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$ . Das gesamte Register aus den drei Qubit wird mit $\ket{\phi_1}$ abgekürzt.

In dem ersten Schritt wird auf die ersten beiden Qubits von Register $\ket{\phi_0}$ Das CNOT-Gatter angewandt woraus $\ket{\phi_1}$ folgt. Auf das erste Qubit wird anschließend die Hadarmard-Matrix angewandt was $\ket{\phi_2}$ zur Folge hat. Die Formel wird daraufhin so umgestellt, dass die beiden ersten Qubit des Registers ausgeklammert stehen. Dadurch ist es einfacher zu erkennen, welchen Zustand das dritte Qubit annimmt, sobald die Messung der ersten beiden Bits erfolgt. Während der oben gezeigten Transformationen wurde das dritte Bit $b$ nicht angetastet. Es kann daher angenommen werden, dass sich dieses Qubit an einem anderen Ort als die anderen beiden befindet.

In unserem Beispiel würde Alice nun die beiden ersten Qubits von $\ket{\phi_2}$ messen und kann damit auf den Zustand von Bobs Qubit schließen.

Alice teilt Bob nun nicht mit, in welchen Zustand sein Qubit ist, sondern sagt Bob nur was er machen muss, damit er sein Qubit in den Zustand $\Psi = \alpha \ket{0} + \beta \ket{1}$ versetzten kann. Misst Alice beispielsweise $\ket{00}$ so befindet sich Bobs Qubit bereits in dem gewünschten Zustand und er könnte mit diesem arbeiten. Misst Alice hingegen $\ket{00}$ so sagt sie zu Bob, dass er auf sein Qubit das Bitflip-Gatter $X$ anwenden muss um $\ket{\Psi}$ zu erhalten. Bei $\ket{10}$ führt Bob einen Phaseflip $Z$ aus und bei $\ket{11}$ beide Operationen hintereinander.

Würde eine dritte Person Alice und Bob dabei belauschen, welche Operationen Bob ausführen muss, so würde er dadurch keine brauchbare Information erhalten. Ohne das anfängliche Qubit $\ket{b}$ , welches sich in Bobs Besitzt befindet, kann auch nicht auf das geheime Ergebnis $\ket{\Psi}$ der Transformation geschlossen werden.

Die Quantenteleportation kann nicht schneller als Lichtgeschwindigkeit stattfinden. Zwar ist das EPR-Paar verschränkt und nimmt bei einer Messung einen auf beiden Seiten gekoppelten Zustand ein, Alice benötigt jedoch immer noch einen weiteren Informationskanal um Bob mitzuteilen welche Operationen er auf seinem Qubit ausführen muss um die gewünschte Information zu übertragen.

Quantenalgorithmen

Die folgenden Algorithmen beschreiben die aktuellen Einsatzmöglichkeiten von Quantencomputern. Eine genaue Beschreibung und Herleitung der einzelnen Algorithmen findet sich in dem bereits erwähnten Buch von Matthias Homeister.

Mit dem Deutsch-Jozsa-Algorithmus lässt sich ermitteln ob eine Funktion $f$ balanciert $f(0) \neq f(1)$ oder konstant
$f(0) = f(1)$ ist. Die Fragestellung wird als Problem von Deutsch bezeichnet und lässt sich durch Quantencomputer mit nur einem Zugriff auf die Funktion auswerten.
Durch den Shor-Algorithmus lässt sich eine Zahl in polynomischer Zeit
faktorisieren. Dies ist vor allen Dingen bei kryptographischen Verfahren bedeutsam, da diese auf der nicht trivialen Berechnung von Primzahlen beruhen.
Bestandteil des Shor-Algorithmus ist die Quanten-Fouriertransformation, welche es erlaubt eine Funktion in ihre Frequenzen zu zerlegen.
Das BB84-Protokoll beschreibt ein Verfahren zum sicheren Austausch von privaten Schlüsseln um eine sichere Kommunikation zu ermöglichen. Wie der Name vermuten lässt wurde das Protokoll bereits 1984 entwickelt.
Der Grover-Algorithmus erlaubt es eine Suche in einer unsortierten Datenbank mit $O(\sqrt{N})$ Schritten durchzuführen. Da sich viele Probleme in der Informatik auf Suchen herunterbrechen lassen bieten Quantencomputer hier einen erheblichen Vorteil gegenüber anderen Suchverfahren.