Quantum Computing (4) – infaktum.de

[Abb: „A Wafer of the Latest D-Wave Quantum Computers“ by jurvetson (licensed under CC BY 2.0.)]

Der Algorithmus von Deutsch

Wir kommen nun zum bisherigen Höhepunkt der Reihe: Der erste Quantenalgorithmus überhaupt, der nach seinem Erfinder David Deutsch als Algorithmus von Deutsch bekannt ist.

Das behandelte Problem (wenn man es als Problem bezeichnen will) lautet: Es ist eine Funktion $f : \{0,1\} \rightarrow \{0,1\}$ definiert, die wir nicht kennen. Sie ist also eine Black Box, und auch die Bezeichnung Orakel ist üblich. Die Frage ist nun: Ist $f$ konstant, d.h. ist $f(0) = f(1)$ , oder ist f balanciert, d.h. ist $f(0) \ne f(1)$ ? Das Problem ist offensichtlich leicht zu lösen: Man bestimmt $f(0)$ und $f(1)$ und vergleicht die Werte – fertig! Dies entspricht der Situation, dass wir eine Münze bekommen und sagen sollen, ob es eine „faire“ Münze ist, d.h. ob auf Vorder- und Rückseite Kopf und Zahl sind, oder ob es eine Trickmünze ist, also dass z.B. auf beiden Seiten die Zahl ist. Wir schauen uns einfach beide Seiten an. Wo ist die Schwierigkeit?

Natürlich ist das Problem von Deutsch kein Problem im eigentlichen Sinne. Aber was ist, wenn wir zusätzlich fordern: Du darfst dir nur eine Seite der Münze ansehen! Dies entspricht der Bedingung: Man darf die Funktion $f$ nur einmal aufrufen. Jetzt ist es wirklich ein Problem. Und es ist klassisch unlösbar. Nicht so beim Quantum Computing!

Dabei haben wir erst einmal das Problem, dass die Funktion $f$ kein unitärer Operator ist, sondern einfach eine binäre Funktion. Man kann aber aus $f$ einen unitären Operator wie folgt konstruieren:

$F: \ket{a,b} \rightarrow \ket{a, f(a) \oplus b}.$

Dabei steht $\oplus$ für die klassische XOR-Verknüpfung, also die exklusive Oder-Verknüpfung, bei der $a\oplus b = 1$ ist wenn $a \ne b$ , und $a\oplus b = 0$ für $a = b$ . Das Pluszeichen im Kreis erinnert an die Addition der beiden Bits: 0+0 = 0, 1+1 = 10, und wir betrachten nur das kleinste Bit, das 0 ist, das höherwertige Bit werfen wir fort.. Umgekehrt ist 1+ 0 = 0 + 1 = 1.

Das ist aber genau unsere Frage an unser Orakel: Bist du konstant oder balanciert?

Wie wirkt F auf die Basisvektoren?

Wir rechnen jetzt einmal aus, wie der Operator $F$ auf den Basisvektoren wirkt. Dazu müssen wir die vier möglichen Fälle für $f$ unterscheiden, die wir entsprechend durchnumerieren:

$\begin{split}f_1(0) &= f_1(1) = 0\\f_2(0) &= f_2(1) = 1\\f_3(0) &= 0, f_3(1) = 1\\f_4(0) &= 1, f_4(1) = 0.\end{split}$

$f_1, f_2$ sind konstant, $f_3, f_4$ balanciert. Wie wirken die vier daraus abgeleiteten Operatoren $F_1, F_2, F_3, F_4$ auf die Basisvektoren? Das ist nun einfach eine Fleißaufgabe, und wir kommen zu dem Ergebnis:

$\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}$

Aufbau der Schaltung

Wir bauen jetzt einmal die Schaltung für unserer Register für die Implementierung des Algorithmus auf. Wir bringen zuerst beide Qubits in eine Superposition von 0 und 1:

Wie sieht die Wellenfunktion für unser System aus? Das können wir leicht ausrechnen, denn in Teil 3 der Reihe haben wir die Hadamard-Matrix für ein 2-Qubit-Register berechnet:

$H_2 = H \otimes H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1\end{pmatrix} \otimes \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1\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}.$

Wir haben als Ausgangspunkt vier mögliche Kombinationen der einzelnen Qubits: $\ket{00},\ket{01},\ket{10},\ket{11}$ . Dies entsprach in der Komponentendarstellung jeweils einem Vektor, an der Stelle k eine 1 stand und sonst 0. Rechnen wir als Beispiel einmal den Zustand nach der Hadamard-Operation für den Fall a = 0 und b = 1 aus:

$\begin{split} H_2 \ket{01} &= \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} 0\\1\\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} - \begin{pmatrix} 0\\1\\0\\0 \end{pmatrix} + \begin{pmatrix} 0\\0\\1\\0 \end{pmatrix} - \begin{pmatrix} 0\\0\\0\\1 \end{pmatrix} ) \\&=\frac{1}{2} (\ket{00} - \ket{01} + \ket{10} - \ket{11}).\end{split}$

Offensichtlich ist nun jedes Ergebnis einer Messung gleich wahrscheinlich, mit der Wahrscheinlichkeit $\frac{1}{4}$ . Wir haben keine Verschränkung, sondern einen Produktzustand.

Nun kommt unser Operator $F$ ins Spiel:

Durch die Anwendung von $F$ haben wir jetzt zwei verschränkte Qubits in einer Superposition. Nehmen wir einmal unser Beispiel $\ket{01}$ ; nach der Hadamard-Operation ist das System im Zustand $\frac{1}{2} (\ket{00} - \ket{01} + \ket{10} - \ket{11})$ . Wie wirken nun die $F_k$ aud diesen Zustand? Oben haben wir bereits die Vorarbeit geleistet:

$\begin{split}F_1 &: \ket{01} \overset{H_2}{\rightarrow} \frac{1}{2} (\ket{00} - \ket{01} + \ket{10} - \ket{11}) \overset{F_1}{\rightarrow} \frac{1}{2} (\ket{00} - \ket{01} + \ket{10} - \ket{11})\\F_2 &: \ket{01} \overset{H_2}{\rightarrow} \frac{1}{2} (\ket{00} - \ket{01} + \ket{10} - \ket{11}) \overset{F_2}{\rightarrow} \frac{1}{2} (\ket{01} - \ket{00} + \ket{11} - \ket{10})\\F_3 &: \ket{01} \overset{H_2}{\rightarrow} \frac{1}{2} (\ket{00} - \ket{01} + \ket{10} - \ket{11}) \overset{F_3}{\rightarrow} \frac{1}{2} (\ket{00} - \ket{01} + \ket{11} - \ket{10})\\F_4 &: \ket{01} \overset{H_2}{\rightarrow} \frac{1}{2} (\ket{00} - \ket{01} + \ket{10} - \ket{11}) \overset{F_4}{\rightarrow} \frac{1}{2} (\ket{01} - \ket{00} + \ket{10} - \ket{11}).\end{split}$

Die vier verschiedenen Versionen von $F$ haben die Basisvektoren noch etwas durcheinandergewürfelt. Aber wir haben eigentlich noch nichts erreicht: Jeder der vier möglichen Basiszustände ist nach wie vor gleich wahrscheinlich, wird also bei einer abschließenden Messung mit Wahrscheinlichkeit $\frac{1}{4}$ gemessen werden. Was nun?

Interferenz

Nun kommt das Geniale des Algorithmus. Nachdem die $F_k$ die Basisvektoren auf der rechten Seite etwas durcheinandergewürfelt hat, bzw. einige Vorzeichen umgekehrt hat, überlagern wir die Wellenfunktionen der beiden Qubits ein zweites Mal. Die dabei auftretenden Interferenzen – die Änderungen der Vorzeichen entsprechen ja Phasenverschiebungen um den Winkel $\pi$ – führen zum gewünschten Ergebnis. Grafisch sieht das so aus: Wir fügen die Hadamard-Operation zwischen $F$ und der Messung ein:

Was geschieht nun mit unserem Startzustand $\ket{01}$ , wenn er diese Schaltung durchlaufen hat? Dazu betrachten wir wieder die vier Fälle, wobei wir diesmal wieder mit den Komponenten arbeiten. Wir schreiben zuerst einmal unsere Zwischenergebnisse in Komponentenform

$\begin{split}F_1 &: \ket{00} \rightarrow \frac{1}{2} \begin{pmatrix} +1\\-1\\+1\\-1 \end{pmatrix}\\F_2 &: \ket{01} \rightarrow \frac{1}{2} \begin{pmatrix} -1\\+1\\-1\\+1 \end{pmatrix}\\F_3 &: \ket{10} \rightarrow \frac{1}{2} \begin{pmatrix} +1\\-1\\-1\\+1 \end{pmatrix}\\F_4 &: \ket{11} \rightarrow \frac{1}{2} \begin{pmatrix} -1\\+1\\+1\\-1 \end{pmatrix}.\end{split}$

Nun wenden wir die Hadamard-Operation auf diese Zwischenergebnisse an und erhalten:

$\begin{split}F_1 &: \frac{1}{4} \begin{pmatrix} 1&1&1&1 \\ 1&-1&1&-1 \\ 1&1&-1&-1 \\ 1&-1&-1&1 \end{pmatrix} \begin{pmatrix} +1\\-1\\+1\\-1 \end{pmatrix} = \frac{1}{4} \begin{pmatrix} 0\\+4\\0\\0 \end{pmatrix} = +\begin{pmatrix} 0\\1\\0\\0 \end{pmatrix} = +\ket{01}\\F_2 &: \frac{1}{4} \begin{pmatrix} 1&1&1&1 \\ 1&-1&1&-1 \\ 1&1&-1&-1 \\ 1&-1&-1&1 \end{pmatrix} \begin{pmatrix} -1\\+1\\-1\\+1\end{pmatrix} = \frac{1}{4} \begin{pmatrix} 0\\-4\\0\\0 \end{pmatrix} = -\begin{pmatrix} 0\\1\\0\\0 \end{pmatrix} = -\ket{01}\\F_3 &:\frac{1}{4} \begin{pmatrix} 1&1&1&1 \\ 1&-1&1&-1 \\ 1&1&-1&-1 \\ 1&-1&-1&1 \end{pmatrix} \begin{pmatrix} +1\\-1\\-1\\+1 \end{pmatrix} = \frac{1}{4} \begin{pmatrix} 0\\0\\0\\+4 \end{pmatrix} = +\begin{pmatrix} 0\\0\\0\\1 \end{pmatrix} = +\ket{11}\\F_4 &: \frac{1}{4} \begin{pmatrix} 1&1&1&1 \\ 1&-1&1&-1 \\ 1&1&-1&-1 \\ 1&-1&-1&1 \end{pmatrix} \begin{pmatrix}-1\\+1\\+1\\-1 \end{pmatrix} = \frac{1}{4} \begin{pmatrix} 0\\0\\0\\-4 \end{pmatrix} = -\begin{pmatrix} 0\\0\\0\\1 \end{pmatrix} = -\ket{11}.\end{split}$

Wie durch Geisterhand sind die Superpositionen verschwunden! Jedes der $F_k$ in der beschriebenen Schaltung führt bei Anwendung auf den Startzustand zu einem festen Ergebnis. Und wir sehen: Ist $F$ konstant (also $F_1$ oder $F_2$ ), so hat das erste Qubit bei der Messung mit Sicherheit den Wert 0, und ist $F$ balanciert ( also $F_3$ oder $F_4$ ), so hat dieses Qubit mit Sicherheit den Wert 1. Stören euch die Vorzeichen auf der rechten Seite? Dann erinnert euch, dass $\ket{01}$ und $-\ket{01}$ für denselben Zustand stehen! Sie unterscheiden sich nur durch die Phase.

Ich habe hier etwas schlampig formuliert; natürlich sind die $f_k$ die Funktionen, die konstant oder nicht konstant sind, und nicht die $F_k$ . Es dürfte aber klar sein, was gemeint ist.

Zusammenfassung

Wir haben das Problem von Deutsch kennengelernt und gelöst. Mit Hilfe der beschriebenen Schaltung konnten wir entscheiden, ob $F$ bzw. $f$ konstant oder balanciert ist, obwohl wir es nur einmal angewendet haben. Wir haben also gleichzeitig beide Seiten der Münze gesehen. Das ist nur mit der Quantenmechanik möglich gewesen!