Meine Merkliste
my.chemie.de  
Login  

Deutsch-Jozsa-Algorithmus



Der Algorithmus von Deutsch ist ein Algorithmus 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.

Inhaltsverzeichnis

Geschichte

In einer Arbeit von 1985 beschäftigte sich David Deutsch mit dem Speziallfall 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 ein halb 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 man jetzt nur noch eine Funktionsauswertung benötigt und trotzdem deterministisch bleibt.[3].

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

Das Problem von Deutsch

Problemformulierung

Gegeben sei eine Funktion f: \lbrace0,1\rbrace \mapsto \lbrace0,1\rbrace. Es gilt nun herauszufinden, ob die gegebene Funktion konstant ist (f(0) = f(1)) oder balanciert/gleichgewichtig (f(0) \neq f(1)). Dabei ist zu beachten, dass f uns nur als Black Box gegeben ist, wir also dessen genaue Definition nicht kennen. Uns steht mehr ein Bauteil zur Verfügung, welches uns zu einem Bit b den Wert f(b) berrechnet. Um die Bedeutung des Algorithmus von Deutsch zu unterstreichen, sollten wir davon ausgehen, 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 zwei mal benötigt. Im Folgenden wird gezeigt, dass der Quantenalgorithmus von Deutsch mit nur einem Aufruf auskommt. Dies bringt uns einen Vorteil, wenn wir bedenken, dass nach unserer Annahme ein Aufruf sehr teuer ist (jedoch sind die Kosten asymptotisch gleich).

Der Quantenalgorithmus

  Hinweis: Zum Verständnis des nachfolgenden Abschnittes werden Kenntnisse über die prinzipielle Funktionsweise von Quantencomputern benötigt.

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, brauchen wir eine spezielle Variante von f, beschrieben durch die Abbildung

U_f: |x\rangle |y\rangle \mapsto |x\rangle |f(x)\oplus y\rangle

Der Algorithmus verwendet ein Register von zwei Qubits |x\rangle|y\rangle und besteht aus folgenden Schritten:

  1. Initialisiere wie folgt:
    \begin{align}|x\rangle|y\rangle &\leftarrow |0\rangle|1\rangle\\& = |a\rangle\end{align}
  2. Wende die Hadamard-Transformation H auf beide Qubits an:
    \begin{align}|x\rangle|y\rangle &\leftarrow H|x\rangle H|y\rangle\\& = \frac{1}{\sqrt{2}}(|0\rangle +|1\rangle)\cdot\frac{1}{\sqrt{2}}(|0\rangle -|1\rangle)\\& = \frac{1}{2}(|0\rangle|0\rangle - |0\rangle|1\rangle + |1\rangle|0\rangle - |1\rangle|1\rangle)\\& = |b\rangle\end{align}
  3. Werte Uf aus:
    \begin{align}|x\rangle|y\rangle &\leftarrow U_f|x\rangle|y\rangle\\&=\frac{1}{2}(|0\rangle|0\oplus f(0)\rangle - |0\rangle|1\oplus f(0)\rangle + |1\rangle|0 \oplus f(1)\rangle - |1\rangle|1 \oplus f(1)\rangle)\\&= \frac{1}{2}(|0\rangle \cdot (|f(0)\rangle - |1 \oplus f(0)\rangle) + |1\rangle \cdot (|f(1)\rangle + |1 \oplus f(1)\rangle))\\&= \frac{1}{2}((-1)^{f(0}|0\rangle\cdot(|0\rangle-|1\rangle)+(-1)^{f(1)}|1\rangle\cdot(|0\rangle-|1\rangle)\\&=\frac{1}{2}((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle)\cdot(|0\rangle - |1\rangle)\\&=|c\rangle\end{align}
    |c\rangle ist im konstanten Fall \frac{1}{2}(\pm(|0\rangle + |1\rangle))\cdot(|0\rangle - |1\rangle) und sonst \frac{1}{2}(\pm(|0\rangle - |1\rangle))\cdot(|0\rangle - |1\rangle)
  4. Wende die Hadamard-Transformation H auf das erste Qubit an:
    |x\rangle \leftarrow H|x\rangle
  5. Messe das erste Qubit:
    Hat |x\rangle den Wert |0\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.

Das Problem von Deutsch-Jozsa

Problemformulierung

Nun verallgemeinern wir die Funktion f auf n Eingabebits: f: \lbrace0,1\rbrace^n \mapsto \lbrace0,1\rbrace Uns wird zugesichert, dass die Funktion entweder konstant (alle Eingaben werden auf ein und denselben Wert abgebildet) oder balanciert (die Hälfte der Eingaben wird auf 0 und die andere Hälfte auf 1 abgebildet) ist. Herauszufinden ist nun, welche der beiden Alternativen zutrifft. Erneut ist zu beachten, dass f nur als Black Box bzw. Orakel gegeben ist.

Klassische Lösung

Ein klassischer Computer müsste die Funktion im schlimmsten Fall für mehr als die Hälfte aller möglichen Eingaben auswerten. So kann es beispielsweise passieren, dass selbst bei noch so geschickter Wahl die ersten 2n − 1 (halb so viel wie insgesamt möglich) getesteten Eingaben zum Wert 0 führen und wir trotzdem noch nicht wissen, welche Alternative gilt. Ergibt die nächste Auswertung auch 0, so ist die Funktion konstant, ergibt sie hingegen 1, dann ist sie balanciert.

Ein klassischer Algorithmus benötigt also im worst case 2n − 1 + 1 Auswertungen von f. Wie im Folgenden gezeigt wird benötigt der Algorithmus von Deutsch-Jozsa nur eine einzige Auswertung. Dies stellt einen exponentiellen Laufzeitgewinn dar, was im Gegensatz zum Problem/Algorithmus von Deutsch eine "echte Verbesserung" ist.

Der Quantenalgorithmus

  Hinweis: Zum Verständnis des nachfolgenden Abschnittes werden Kenntnisse über die prinzipielle Funktionsweise von Quantencomputern benötigt.

Der Quantenalgorithmus wendet die gegebene Funktion auf eine Superposition aller möglichen Eingaben an. Durch geschickte Auswertung erhält er somit mit nur einmaliger Anwendung des Orakels ausreichend Information über alle Funktionswerte.

Auf Grund der zu erhaltenden Umkehrbarkeit benötigen wir wieder eine spezielle Variante von f, beschrieben durch die Abbildung

U_f: |x\rangle |y\rangle \mapsto |x\rangle |f(x)\oplus y\rangle

wobei |x\rangle die Eingabe der Länge n ist.

Der Algorithmus durchläuft folgende Schritte:

  1. Initialisierung: die ersten n Bits auf |0\rangle und das letzte Bit auf |1\rangle setzen:
    \begin{align}|x\rangle|y\rangle &\leftarrow |0\rangle^{\otimes n} |1\rangle\\& = |a\rangle\end{align}
  2. Wende die Hadamard-Transformation Hn + 1 (also H2 auf alle Qubits) an:
    \begin{align}|x\rangle|y\rangle &\leftarrow H_{n+1}|x\rangle|y\rangle\\&=(\frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^n-1} |x\rangle) \cdot \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle )\\&=\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|0\rangle - |1\rangle )\\&=|b\rangle\end{align}
  3. Werte Uf aus:
    \begin{align}|x\rangle|y\rangle &\leftarrow U_f|x\rangle|y\rangle\\&=  \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|f(x)\rangle - |1\oplus f(x)\rangle ) \\&=  \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle (|0\rangle - |1\rangle ) \\&= (\frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle) \cdot \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle ) \\ &= |c\rangle\end{align}
  4. Wende die Hadamard-Transformation auf |x\rangle an:
    \begin{align} |x\rangle|y\rangle &\leftarrow (H_n|x\rangle)|y\rangle\\ &= (\frac{1}{2^n}\sum_{z=0}^{2^n-1}\sum_{x=0}^{2^n-1} (-1)^{x\cdot z +f(x)}|z\rangle)\cdot \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \\ &= |d\rangle \end{align}
  5. Messe das Register |x\rangle:
    Ist es |0\ldots 0\rangle, so ist f konstant, ansonsten balanciert.

Die Interpretation des Messergebnisses ist folgendermaßen einzusehen: Ist f balanciert, so gleichen sich die Vorzeichen für |z\rangle=|0\rangle aus, so dass wir mit einer Wahrscheinlichkeit von 0 den Wert |0\rangle messen. Im anderen Fall, also wenn f konstant ist, sind genau die Amplituden für |z\rangle\neq|0\rangle gleich 0, da sich für soche z die x immer so einteilen lassen, dass die Hälfte skalarmultipliziert mit z einen geraden Wert ergibt, die andere Hälfte aber einen ungeraden.

Einzelnachweise

  1. David Deutsch: The Church-Turing principle and the universal quantum computer. In: Proceedings of the Royal Society of London A. 400, 1985, S. 97
  2. David Deutsch und Richard Jozsa: Rapid solutions of problems by quantum computation. In: Proceedings of the Royal Society of London A. 439, 1992, S. 553
  3. R. Cleve, A. Ekert, C. Macchiavello und M. Mosca: Quantum algorithms revisited. In: Proceedings of the Royal Society of London A. 454, 1998, S. 339-354
  4. Lov K. Grover: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. 1996, S. 212-219
  5. Peter W. Shor: Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In: IEEE Symposium on Foundations of Computer Science. 1994, S. 124-134

Literatur

  • Matthias Homeister: Quantum computing verstehen. Vieweg, Wiesbaden 2005, ISBN 3-528-05921-4, S. 33–37, 62–65
 
Dieser Artikel basiert auf dem Artikel Deutsch-Jozsa-Algorithmus aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation. In der Wikipedia ist eine Liste der Autoren verfügbar.
Ihr Bowser ist nicht aktuell. Microsoft Internet Explorer 6.0 unterstützt einige Funktionen auf ie.DE nicht.