Deutsch-Jozsa-Algorithmus

Der Algorithmus von Deutsch ist ein Quantenalgorithmus für Quantencomputer, mit dem man bestimmen kann, ob eine auf einem Bit operierende Funktion konstant oder balanciert ist. Diese Aufgabenstellung ist unter dem Namen Problem von Deutsch bekannt. Der Algorithmus von Deutsch ist zwar kaum von praktischem Nutzen, er war jedoch historisch der erste Quantenalgorithmus, der eine Aufgabenstellung nachweisbar schneller löst als ein klassischer Algorithmus und damit die theoretischen Möglichkeiten von Quantencomputern aufzeigt.

Eine Verallgemeinerung ist der Deutsch-Jozsa-Algorithmus. Dabei wird das Problem von Deutsch auf mehrere Bits übertragen.

Die Algorithmen wurden nach ihren Urhebern David Deutsch und Richard Jozsa benannt.

Geschichte

In einer Arbeit von 1985 beschäftigte sich David Deutsch mit dem Spezialfall des Problems (Problem von Deutsch, Anzahl der Eingabebits: 1).^[1]

1992 wurde die Idee durch David Deutsch und Richard Jozsa verallgemeinert (Problem von Deutsch-Jozsa, beliebig viele Eingabebits).^[2]

Der von Deutsch ursprünglich vorgeschlagene Algorithmus war de facto nicht deterministisch. Er war mit einer Wahrscheinlichkeit von 0,5 erfolgreich. Der originale Deutsch-Jozsa-Algorithmus war zwar deterministisch, benötigte jedoch im Gegensatz zum Algorithmus von Deutsch zwei Funktionsauswertungen statt nur einer.

Durch R. Cleve, A. Ekert, C. Macchiavello und M. Mosca wurden 1998 weitere Verbesserungen vorgenommen, so dass jetzt nur noch eine Funktionsauswertung benötigt wird und der Algorithmus dennoch deterministisch bleibt.^[3]

Der Deutsch-Jozsa-Algorithmus diente als Inspiration für den Shor-Algorithmus und den Grover-Algorithmus, zwei der revolutionärsten Quantenalgorithmen.^[4]^[5]

Das Problem von Deutsch

Problemformulierung

Gegeben sei eine Funktion $f:\lbrace 0,1\rbrace \to \lbrace 0,1\rbrace$ . Es gilt nun herauszufinden, ob die gegebene Funktion konstant ist ( $f(0)=f(1)$ ) oder balanciert/gleichgewichtet ( $f(0)\neq f(1)$ ). Dabei ist zu beachten, dass $f$ nur als Black Box gegeben ist, die genaue Definition also unbekannt ist – es steht lediglich ein Bauteil zur Verfügung, welches zu einem Bit $b$ den Wert $f(b)$ berechnet. Um die Bedeutung des Algorithmus von Deutsch zu unterstreichen, sollte davon ausgegangen werden, dass die Benutzung dieses Bauteils teuer ist.

Zur Veranschaulichung kann man sich vorstellen, dass man entscheiden soll, ob eine gegebene Münze fair (Kopf auf der einen Seite, Zahl auf der anderen) oder unfair (Kopf oder Zahl auf beiden Seiten der Münze) ist.

Klassische Lösung

Auf klassischem Wege bleibt nichts weiter übrig als die Funktion sowohl für $f(0)$ als auch $f(1)$ auszuwerten und zu vergleichen. Das entspricht dem Betrachten einer Münze auf beiden Seiten. Die Black Box (oder auch Orakel) wird also zweimal benötigt. Im Folgenden wird gezeigt, dass der Quantenalgorithmus von Deutsch mit nur einem Aufruf auskommt. Dies bringt einen Vorteil, wenn man bedenkt, dass nach der Annahme ein Aufruf sehr teuer ist (jedoch sind die Kosten asymptotisch gleich).

Der Quantenalgorithmus

Quantenschaltung, die den Algorithmus von Deutsch implementiert

Der Quantenalgorithmus wendet die gegebene Funktion auf eine Superposition der beiden möglichen Eingaben an. Durch geschickte Auswertung erhält er somit mit nur einmaliger Anwendung des Orakels ausreichend Information über $f(0)$ und $f(1)$ .

Da in der Quanteninformatik alle Rechenschritte umkehrbar sein müssen, wird hier eine spezielle Variante von $f$ benötigt, unter Verwendung von $\oplus$ (Addition mit anschließendem Modulo 2) beschrieben durch die Abbildung

U_{f}:\left|x\right\rangle \left|y\right\rangle \mapsto \left|x\right\rangle \left|f(x)\oplus y\right\rangle

Der Algorithmus verwendet ein Register von zwei Qubits $\left|x\right\rangle \cdot \left|y\right\rangle$ (mit $\cdot$ dem Tensorprodukt, welches gewöhnlich mit $\otimes$ dargestellt wird) und besteht aus folgenden Schritten:

Initialisiere wie folgt:

${\begin{aligned}\left|x\right\rangle \left|y\right\rangle &=\left|0\right\rangle \left|1\right\rangle \\&=\left|a\right\rangle \end{aligned}}$
Wende die Hadamard-Transformation $H$ auf beide Qubits an:

${\begin{aligned}\left|x\right\rangle \left|y\right\rangle &\rightarrow H\left|x\right\rangle H\left|y\right\rangle \\&={\frac {1}{\sqrt {2}}}{\bigl (}\left|0\right\rangle +\left|1\right\rangle {\bigr )}\cdot {\frac {1}{\sqrt {2}}}{\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}\\&={\frac {1}{2}}{\bigl (}\left|0\right\rangle \left|0\right\rangle -\left|0\right\rangle \left|1\right\rangle +\left|1\right\rangle \left|0\right\rangle -\left|1\right\rangle \left|1\right\rangle {\bigr )}\\&=\left|b\right\rangle \end{aligned}}$
Werte $U_{f}$ aus:

${\begin{aligned}\left|x\right\rangle \left|y\right\rangle &\rightarrow U_{f}\left|x\right\rangle \left|y\right\rangle \\&={\frac {1}{2}}{\Bigl (}\left|0\right\rangle \left|0\oplus f(0)\right\rangle -\left|0\right\rangle \left|1\oplus f(0)\right\rangle +\left|1\right\rangle \left|0\oplus f(1)\right\rangle -\left|1\right\rangle \left|1\oplus f(1)\right\rangle {\Bigr )}\\&={\frac {1}{2}}{\Bigl (}\left|0\right\rangle \cdot {\bigl (}\left|f(0)\right\rangle -\left|1\oplus f(0)\right\rangle {\bigr )}+\left|1\right\rangle \cdot {\bigl (}\left|f(1)\right\rangle -\left|1\oplus f(1)\right\rangle {\bigr )}{\Bigr )}\\&={\frac {1}{2}}{\Bigl (}(-1)^{f(0)}\left|0\right\rangle \cdot {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}+(-1)^{f(1)}\left|1\right\rangle \cdot {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}{\Bigr )}\\&={\frac {1}{2}}{\bigl (}(-1)^{f(0)}\left|0\right\rangle +(-1)^{f(1)}\left|1\right\rangle {\bigr )}\cdot {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}\\&=\left|c\right\rangle \end{aligned}}$

$\left|c\right\rangle$ ist im konstanten Fall ${\frac {1}{2}}{\Bigl (}\pm {\bigl (}\left|0\right\rangle +\left|1\right\rangle {\bigr )}{\Bigr )}\cdot {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}$ und sonst ${\frac {1}{2}}{\Bigl (}\pm {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}{\Bigr )}\cdot {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}$
Wende die Hadamard-Transformation $H$ auf das erste Qubit an:

$\left|x\right\rangle \rightarrow H\left|x\right\rangle$
Miss das erste Qubit:

Hat $\left|x\right\rangle$ den Wert $\left|0\right\rangle$ , so ist $f$ konstant, ansonsten balanciert.

Der Trick besteht also darin, dass wir die Funktionswerte in die Amplitude verlagern.

Realisierung

Über die erste experimentelle Realisierung wurde von S. Gulde in Nature 421, 48 (2003) berichtet. Die dafür benötigten Qubits wurden durch den elektronischen und vibratorischen Freiheitsgrad eines $Ca^{+}$ -Ions in einer Falle implementiert.