5.2.4 Bernstein-Vazirani-Algorithmus

In den vorigen Abschnitten haben wir mithilfe der Hadamard-Transformation interessante Probleme gelöst. Gegeben einer Funktion $f\colon\{0,1\}^{n}\to\{0,1\}$ und dem Versprechen, dass $f$ entweder konstant oder balanced ist, kann der Deutsch-Jozsa-Algorithmus herausfinden, welche der beiden Fälle zutrifft.

In diesem Abschnitt werden wir ein anderes interessantes Problem besprechen, welches mit einer kleinen Veränderung des selben Algorithmus gelöst werden kann. Wie auch zuvor starten wir mit einem Versprechen über eine unbekannte Funktion $f$. In diesem Fall werden wir aber nicht annehmen, dass die Funktion entweder konstant oder balanced ist, stattdessen nehmen wir, an dass sie die folgende spezielle Form hat:

wobei $a_{1},\dots,a_{n}\in\{0,1\}$ ein fester Bitstring ist, der die Funktion definiert.

Wenn $n=1$, gibt es nur zwei solche Funktionen:

• •
  ​

  $f(x_{1})=0$ wenn $a_{1}=0$ sowie

• •
  ​

  $f(x_{1})=x_{1}$ wenn $a_{1}=1$.

Wenn $n=2$, dann gibt es schon vier verschiedene solcher Funktionen:

• •
  ​

  $f(x_{1},x_{2})=0$, wenn $[a_{1},a_{2}]=[0,0]$,

• •
  ​

  $f(x_{1},x_{2})=x_{2}$, wenn $[a_{1},a_{2}]=[0,1]$,

• •
• •

Beachte, dass jede dieser Funktionen eine Summe modulo Zwei über eine Teilmenge der Variablen $x_{i}$ berechnet. Welche Teilmenge? Wenn $a_{i}=1$ gilt, dann ist die Variable $x_{i}$ in der Teilmenge enthalten.

Im Allgemeinen gibt es $2^{n}$ mögliche Bitstrings $a_{1},\dotsc,a_{n}$ und somit $2^{n}$ Funktionen $f$ der speziellen Form (5.14). Tatsächlich können wir uns Gl. 5.14 als Methode zum Verstecken des Bitstrings in der Funktion $f$ vorstellen. Wie oft muss man die Funktion auswerten um den Bitstring offenzulegen? Da

können wir schlussfolgern, dass $n$ auswertungen von $f$ auf jeden Fall ausreichen. Für jeden klassischen Algorithmus entspricht das auch dem Optimum: für jede Auswertung lernt man ein Bit an Information. Da die unbekannten Bits $a_{1},\dots,a_{n}$ komplett unabhängig und beliebig sind und es genau $n$ gibt, muss man die Funktion mindestens $n$-mal auswerten um alle Bits zu lernen.

Gleich werden wir sehen, dass das Problem mit einem Quantenalgorithmus viel besser gelöst werden kann. Zu Beginn berechnen wir erst einmal, wie sich das Phasen-Orakel für die Funktion aus Gl. 5.14 auf Basiszustände auswirkt:

Im zweiten Schritt haben wir ausgenutzt, dass $(-1)^{a}$ nur von $a$ modulo Zwei (also ob $a$ gerade oder ungerade ist) abhängt, weswegen es keinen Unterschied macht, ob wir die Addition modulo 2 (‘$\oplus$’) oder die normale Addition benutzen. Wie können wir dieses Phasen-Orakel implementiert werden? Eigentlich interessiert uns das nicht, da der Algorithmus das Orakel wie eine Black-Box benutzen wird. Aber da es eine schöne Übung ist, kannst du das in der folgenden Übungsaufgabe herausfinden.

Nun stellen wir den Bernstein-Vazirani-Algorithmus vor, welcher den versteckten Bitstring $[a_{1},\dots,a_{n}]$ mit nur eines Aufrufs des Phasen-Orakels für $f$ aufdecken kann:

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 Funktion $f$ an.

4. 4.
   ​

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

5. 5.
   ​

   Messe zum Schluss alle Qubits. Das Messergbnis entspricht genau dem Bitstring $[a_{1},\dots,a_{n}]$.

Der Algorithmus ist identisch zu dem Deutsch-Jozsa-Algorithmus aus Abschnitt 5.2.3, bis auf den letzten Schritt, welcher noch einfacher ist.