5.2.1 Der Algorithmus von Deutsch

Es ist ein später Sonntagabend. Alice und Bob haben gerade eben ihre Hausaufgaben für den Quantencomputerkurs gemacht und wollen jetzt einen 3D-Film schauen. Als sie ihren holografischen Fernseher anschalten, stellen sie fest, dass der Film wegen unerwarteter dramatischer Neuigkeiten von der Internationalen Transgalaktischen Station verschoben wurde. Es gab einen schrecklichen Unfall: ein Modul mit den zwei Crew-Mitgliedern Hila und Iman hat sich vom Hauptschiff getrennt. Die letzte empfangene Nachricht vom Modul war, dass Iman verletzt wurde und blutete – er braucht dringend eine Bluttransfusion. Leider stehen sowohl Hila als auch Iman unter Schock und haben ihren eigenen Blutgruppen vergessen – sie können sich nur daran erinnern, dass sie jeweils entweder Blutgruppe A oder B hatten. Die Moderation der Sendung appelliert an alle Zuschauende, Vorschläge zu machen, wie Hila und Iman herausfinden könnten, ob sie die selbe Blutgruppe haben, dann könnte Hila nämlich ihr Blut an Iman übertragen um sein Leben zu retten. An Bord befindet sich nämlich ein Lympho-Transcoder, der die beiden Blutgruppen in den jeweils anderen umwandeln kann. Selbst wenn sie also nicht die gleiche Blutgruppe haben, könnte Hila den Transcoder nutzen um ihr Blut zum richtigen Typ umzuwandeln.

Nachdem sie diese Nachrichten gehört haben, entscheiden sich Alice und Bob zu überlegen, wie man Hila und Iman helfen könnte, anstelle den Film zu schauen. Die Nachrichtensendung setzt fort mit weiteren Informationen. Glücklicherweise hat das Modul einen Datenbank-Chip, auf dem Hila und Imans Blutgruppe gespeichert ist. Wir können diesen durch eine Funktion $f\colon\{0,1\}\to\{0,1\}$ modellieren, wobei

Nun muss herausgefunden werden, ob $f(0)=f(1)$ gilt oder nicht!

Die Lösung scheint einfach: Hila und Iman fragen die Datenbank einfach zweimal ab um ihre jeweiligen Blutgruppen $f(0)$ und $f(1)$ herauszufinden und vergleichen anschließend die Werte. Unglücklicherweise wurde der Chip bei dem Unfall beschädigt und die Nachrichtensendung berichtet, dass die Datenbank höchstwahrscheinlich nach einer einzigen Abfrage völlig zerstört sein würde.

Unsere beiden Protagonisten befinden sich in einer Pattsituation. Offensichtlich muss jeder klassische Algorithmus $f$ genau zweimal auswerten um herauszufinden, ob $f(0)=f(1)$. Wenn wir den Wert von $f(0)$ kennen hängt $f(0)=f(1)$ immer noch von $f(1)$ ab und lässt sich nicht bestimmen, außer man berechnet $f(1)$. Genauso lässt sich ein bekanntes $f(1)$ nicht mit einem unbekannten $f(0)$ vergleichen. Egal welchen Ansatz man verfolgt, man muss sowohl den Wert von $f(0)$ als auch von $f(1)$ kennen, um $f(0)=f(1)$ zu bestimmen. Gibt es da wirklich keinen Ausweg?

Nachdem Bob ein paar Bedienungsanleitungen durchblättert hat, stellt Bob fest, dass der Datenbank-Chip auch einen Quantenmodus besitzt. Wenn dieser aktiviert ist, wertet die Datenbank die Funktion nicht mehr klassisch aus, sondern nutzt stattdessen das Phasen-Orakel $O_{f}$. Könnte das vielleicht dabei helfen, das Problem zu lösen? Alice überlegt eine Weile und stellt dann überrascht fest, dass es genau für dieses Problem den Algorithmus von Deutsch gibt! Die beiden prüfen mit ein paar Berechnungen noch schnell, dass alles funktioniert und senden dann eine intergalaktische E-Mail mit Anweisungen zum lösen des Dilemmas an Hila und Iman. Ihre Instruktionen sind die folgenden:

1. 1.
   ​

   Bereitet ein Qubit im Zustand $\left|+\right\rangle=(\left|0\right\rangle+\left|1\right\rangle)/\sqrt{2}$ vor.

2. 2.
   ​

   Nutzt den Datenbank-Chip im Quantenmodus um die Operation $O_{f}$ auf das Qubit anzuwenden.

3. 3.
   ​

   Wendet das Hadamard-Gatter $H$ auf das Ausgabe-Qubit an und messt anschließend.

4. 4.
   ​

   Wenn das Messergbnis $0$ ist, haben Hila und Iman die gleiche Blutgruppe, ansonsten haben sie unterschiedliche.

Beachte, dass bei dieser Prozedur der Datenbank-Chip nur einmal abgefragt wird, um zu bestimmen, ob sie die gleiche Blutgruppe haben. Hier ist eine Implementierung des Algorithmus in Quirky:

Das Bild zeigt, dass das Ergebnis $1$ ist, also haben Hila und Iman unterschiedliche Blutgruppen.

Aber wieso funktioniert der Algorithmus von Deutsch? Lass uns den Algorithmus Schritt für Schritt analsysieren. Das erste Hadamard-Gatter erstellt den Zustand $\left|+\right\rangle=H\left|0\right\rangle$. Anschließend wenden wir das Phasen-Orakel $O_{f}$ an, was zum folgenden Zustand führt

Nach dem anwenden des zweiten Hadamard-Gatters, erhalten wir den Zustand:

Beachte, dass die beiden Vorzeichen $(-1)^{f(0)}$ und $(-1)^{f(1)}$ in der ersten Amplitude addiert, in der zweiten aber subtrahiert werden. Je nach den Werten von $f(0)$ und $f(1)$ sehen wir für jede Amplitude entweder konstruktive oder destruktive Interferenz (siehe Abschnitt 2.6.1). Tatsächlich bestimmt sich nur daran, ob $f(0)$ und $f(1)$ gleich sind oder nicht, welche Amplitude übrig bleibt:

Es ist eine gute Übung, dies explizit zu verifizieren:

Gl. 5.8 zeigt, dass die abschließende Messung nur dann das Ergebnis 0 ergibt, wenn $f(0)=f(1)$ gilt. Also bestimmt der Algorithmus ob $f(0)=f(1)$. Dabei evaluiert der Algorithmus die Funktion $f:\{0,1\}\to\{0,1\}$ nur ein einziges Mal mit dem Phasen-Orakel. Im Gegensatz dazu hatten wir gesehen, dass ein klassischer Algorithmus notwendigerweise beide Funktionswerte $f(0)$ und $f(1)$ getrennt auswerten muss.

Eine weitere Interpretation des Algorithmus von Deutsch ist, dass er die Summe der beiden Bits $f(0)$ und $f(1)$ modulo zwei berechnet. Das liegt daran, dass $f(0)\oplus f(1)=0$ nur genau dann gilt, wenn $f(0)=f(1)$. Aus Gl. 3.21 erinnern wir uns an die Definition von Addition modulo zwei:

Aus diesem Grund ist die Summe modulo zwei auch als XOR (engl. Abkürzung für “exklusives Oder”) der beiden Bits, da sie $1$ genau dann ergibt, wenn nur eines der beiden Bits gesetzt ist.