Quantum Computing (5) – infaktum.de

Mit dem im letzten Teil vorgestellten Algorithmus können wir ein Problem lösen, das klassisch unlösbar ist: Wir konnten feststellen, ob eine zweiwertige Funktion konstant ist oder nicht, wobei wir sie nur einmal ausgeführt haben. Möglich war dies durch die Zusammenschaltung zweier Qubits und anschließende Überlagerung, wobei wir Interferenzen geschickt ausgenutzt haben.

Dabei haben wir ziemlich viel herumgerechnet und sind zwischen der Komponentendarstellung und der Vektordarstellung der Zustände hin- und hergesprungen, wie es gerade passte. Ich möchte das Ganze jetzt einmal konsequent in der Komponentendarstellung vorführen. Schreiben wir erst einmal auf, was wir schon haben:

Die Hadamard-Matrix, mit der wir die Superposition erzeugen, hat die Form

$H_2 = \frac{1}{2} \begin{pmatrix} 1&1&1&1 \\ 1&-1&1&-1 \\ 1&1&-1&-1 \\ 1&-1&-1&1 \end{pmatrix}.$

Die $F_k$ wirken auf die Basisvektoren wie folgt:

$\begin{split} F_1 &: \ket{00} \rightarrow \ket{00}, \ket{01} \rightarrow \ket{01},\ket{10} \rightarrow \ket{10},\ket{11} \rightarrow \ket{11}, \\F_2 &: \ket{00} \rightarrow \ket{01}, \ket{01} \rightarrow \ket{00},\ket{10} \rightarrow \ket{11},\ket{11} \rightarrow \ket{10}, \\ F_3 &: \ket{00} \rightarrow \ket{00}, \ket{01} \rightarrow \ket{01},\ket{10} \rightarrow \ket{11},\ket{11} \rightarrow \ket{10}, \\F_4 &: \ket{00} \rightarrow \ket{01}, \ket{01} \rightarrow \ket{00},\ket{10} \rightarrow \ket{10},\ket{11} \rightarrow \ket{11}.\end{split}$

Basisvektoren werden also auf andere Basisvektoren abgebildet, d.h. die Basisvektoren werden vertauscht (im Fall von $F_1$ haben wir sogar die Identität). Die $F_k$ sind also Permutationsmatrizen, und man erhält durch genaues Hinsehen die Matrizen:

$\begin{split} F_1& = \begin{pmatrix} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&1&0 \\ 0&0&0&1 \end{pmatrix}, F_2 = \begin{pmatrix} 0&1&0&0 \\ 1&0&0&0 \\ 0&0&0&1 \\ 0&0&1&0 \end{pmatrix}, \\ F_3 &= \begin{pmatrix} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0 \end{pmatrix}, F_4 = \begin{pmatrix} 0&1&0&0 \\ 1&0&0&0 \\ 0&0&1&0 \\ 0&0&0&1 \end{pmatrix}. \end{split}$

Da die $F_k$ Permutationsmatrizen sind, sind sie auch automatisch unitär. Der Beweis ist eine schöne Übungsaufgabe!

Hier ist noch einmal unsere Schaltung:

Wir haben also zuerst ein Hadamard-Gatter, dann ein $F_k$ und dann noch einmal ein Hadamard-Gatter. Da die Operationen linear sind, kann man sie zu einer einzigen zusammenfassen, zumindest mathematisch. Dazu müssen wir die entsprechenden Matrizen einfach miteinander multiplizieren. Das ist eigentlich einfach, aber man muss schon aufpassen, dass man keine Fehler macht. Die Matrizen haben wir oben hingeschrieben, und hier kommen jetzt die Ergebnisse:

$\begin{split}H_2F_1H_2 &= \begin{pmatrix} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&1&0 \\ 0&0&0&1 \end{pmatrix}, H_2 F_2 H_2 = \begin{pmatrix} 1&0&0&0 \\ 0&-1&0&0 \\ 0&0&1&0 \\ 0&0&0&-1 \end{pmatrix}, \\H_2 F_3 H_2 &= \begin{pmatrix} 1&0&0&0 \\ 0&0&0&1 \\ 0&0&1&0 \\ 0&1&0&0 \end{pmatrix}, H_2 F_4 H_2 = \begin{pmatrix} 1&0&0&0 \\ 0&0&0&-1 \\ 0&0&1&0 \\ 0&-1&0&0 \end{pmatrix}.\end {split}$

Erinnern wir uns: $F_1$ und $F_2$ waren die konstanten Funktionen. Wir erhalten hier bei der Kombination mit $H_2$ jeweils die Identitätsmatrix! Wir stören uns dabei nicht an den Minuszeichen vor der 1 im Fall von $F_2$ , denn wir wissen, dass $\ket{a}$ und $-\ket{a}$ denselben Zustand beschreiben, lediglich die Phase unterscheidet sich. Im Fall von $F_3$ und $F_4$ werden die beiden Basisvektoren $\ket{01}$ und $\ket{11}$ miteinander vertauscht! Und das haben wir uns in Teil 4 der Reihe zunutze gemacht, als wir den Algorithmus auf $\ket{01}$ angewandt haben. Eine konstante Funktion bildet $\ket{01}$ auf sich selbst ab, eine balancierte Funktion bildet den Zustand auf $\ket{11}$ ab. So konnten wir mit einer Anwendung der Funktion entscheiden, ob sie konstant oder balanciert ist. (Mit $\ket{00}$ oder $\ket{10}$ hätte das nicht funktioniert.)