5.2.3 Der Deutsch-Jozsa-Algorithmus

Sind die obigen Beobachtungen für irgendwas nützlich? Ja, sind sie! Sei $f\colon\{0,1\}^{n}\to\{0,1\}$ eine unbekannte Funktion, die entweder konstant oder balanced ist. Dann gibt es einen einfachen Quantenalgorithmus, welcher feststellen kann, welcher der beiden Fälle zutrifft, der $f$ nur ein einziges mal auswertet (also einmal $O_{f}$ anwendet).

Dieser Algorithmus heißt Deutsch-Jozsa-Algorithmus und funktioniert in fünf einfachen Schritten:

1. 1.
   ​

   Starte mit $\left|0\dots 0\right\rangle$.

2. 2.
   ​

   Wende die Hadamard-Transformation $H\otimes\dotsb\otimes H$ an.

3. 3.
   ​

   Wende das Phasen-Orakel $O_{f}$ der entsprechenden Funktion $f$ an.

4. 4.
   ​

   Wende wieder die Hadamard-Transformation $H\otimes\dotsb\otimes H$ an.

5. 5.
   ​

   Messe alle Qubits. Wenn alle Ergebnisse Null sind, ist die Funktion $f$ konstant. Ansonsten muss sie balanced sein.

Diesen Algorithmus können wir mit klassischen Algorithmen vergleichen, wobei wir bemerken müssen, dass jeder klassische Algorithmus $f$ im schlimmsten Fall mindestens $\frac{2^{n}}{2}+1$ mal evaluieren muss. Angenommen, wir kennen die Funktion auf der Hälfte ihrer Eingabe-Bitstrings (also $2^{n}/2$ Eingaben) und erhalten in jedem Fall die gleiche Ausgabe. Dann können wir immer noch keine Aussage darüber treffen, ob die Funktion konstant ist, da die Funktion auf der anderen Hälfte der Eingabe-Bitstrings immer das andere Ergebnis ausgibt und somit balanced ist. Das würde also dem Worst-Case (engl. für “schlimmsten Fall”) entsprechen. In diesem Szenario hätten wir $2^{n}/2$ Fragen verschwendet, ohne dabei etwas sinnvolles herauszufinden. Um sicher zu gehen, ob $f$ konstant oder balanced ist, müssen wir die Funktion auf einer weiteren Eingabe evaluieren. Das ergibt insgesamt $\frac{2^{n}}{2}+1$ Auswertungen von $f$ im Vergleich zu $1$ Auswertung im Quantenalgorithmus. Bemerke, dass der Unterschied auch für recht kleine Werte wie $n=100$ schon so dramatisch ist, dass man $f$ nicht mit einem vertretbaren Zeitaufwand so häufig auswerten könnte (tatsächlich würde vorher die Sonne vollständig ausbrennen und wir müssten in ein neues Sonnensystem gezogen sein).

Zusammengefasst: Wenn $f\colon\{0,1\}^{n}\to\{0,1\}$ eine Funktion ist, die entweder konstant oder balanced ist, dann kann der Deutsch-Jozsa-Algorithmus mit nur einer Auswertung von $f$ feststellen, welche der beiden Eigenschaften zutrifft. Das ist exponentiell schneller als jeder klassische Algorithmus, welcher im schlimmsten Fall die Funktion auf $\frac{2^{n}}{2}+1$ Eingaben auswerten müsste.