5.2.2 Die Hadamard-Transformation und Interferenz

Der Algorithmus von Deutsch ist zwar sehr überraschend, erreicht aber nur eine geringe Verbesserung gegenüber klassischen Algorithmen, nämlich 1 anstelle von 2 Ausführungen von ff. Das könnte natürlich nützlich sein, wenn das Evaluieren von ff sehr lange dauert, beispielsweise ein Jahr. Aber wenn es sich nur um Millisekunden handelt, macht es für die meisten keinen Unterschied eine Millisekunde länger zu warten (dafür aber viel weniger zu zahlen, da man keinen Quantencomputer bräuchte)! Um den Nutzen von Quantencomputern zu zeigen, würden wir gerne eine Berechnung um mehr als nur den Faktor 2 beschleunigen.

Wenn wir uns nur Funktionen mit einem Bit anschauen, können wir eine stärkere Beschleunigungen vergessen, da diese mit nur zwei Auswertungen voll bestimmt werden können: f⁢(0)f(0) und f⁢(1)f(1). Daher schauen wir uns allgemeinere Funktionen f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} mit nn Eingabe-Bits an, da es davon viel mehr gibt (tatsächlich gibt es 22n2^{2^{n}} viele). Bedenke, unser Ziel ist es nicht, die Funktion auszuwerten (das erreichen wir schon mit nur einer Evaluation des Orakels) sondern eine interessante Eigenschaft der Funktion zu bestimmen, die Funktionswerte auf verschiedenen Eingaben zueinander in Relation stellt. Gibt es Eigenschaften von nn-Bit Funktionen, die wir effizient mit cleveren Quantenalgorithmen in Erfahrung bringen können?

Um den Algorithmus von Deutsch zu verallgemeinern, bemerken wir, dass es ein Schlüsselbestandteil war, ein Hadamard-Gatter vor und nach dem Phasen-Orakel einzufügen. In diesem Fall ist das Phasen-Orakel OfO_{f} eine Quantenoperation auf nn Qubit, also könnten wir auf all diesen Qubits ein Hadamard-Gatter vor und nach dem Orakel einfügen. Die Quantenoperation, die parallel auf allen nn Qubits eine Hadamard-Operation anwedet nennt sich Hadamard-Transformation. Erinnere dich aus Abschnitt 3.2.3, dass wir sie so schreiben können:

H⊗⋯⊗H.\displaystyle H\otimes\dotsb\otimes H.

Lass uns zunächst herausfinden, wenn wir die Hadamard-Transformation auf einen Basiszustand anwenden. Auf |0⁢…⁢0⟩\left|0\dots 0\right\rangle ergibt sich einfach die gleichverteilte superposition über alle Basiszustände:

(H⊗⋯⊗H)⁢|0⁢…⁢0⟩\displaystyle(H\otimes\dotsb\otimes H)\left|0\dots 0\right\rangle =H⁢|0⟩⊗⋯⊗H⁢|0⟩\displaystyle=H\left|0\right\rangle\otimes\dotsb\otimes H\left|0\right\rangle
=12⁢(|0⟩+|1⟩)⊗⋯⊗12⁢(|0⟩+|1⟩)\displaystyle=\frac{1}{\sqrt{2}}\left(\left|0\right\rangle+\left|1\right% \rangle\right)\otimes\dotsb\otimes\frac{1}{\sqrt{2}}\left(\left|0\right\rangle% +\left|1\right\rangle\right)
=12n⁢(|0⁢…⁢00⟩+|0⁢…⁢01⟩+…+|1⁢…⁢11⟩).\displaystyle=\frac{1}{\sqrt{2^{n}}}\left(\left|0\dots 00\right\rangle+\left|0% \dots 01\right\rangle+\ldots+\left|1\dots 11\right\rangle\right).

Dieser Zustand ist eine superposition von 2n2^{n} Basiszuständen. Kompakter könnte man auch schreiben:

(H⊗⋯⊗H)⁢|0⁢…⁢0⟩=12n⁢∑y1,…,yn∈{0,1}|y1,…,yn⟩\displaystyle(H\otimes\dotsb\otimes H)\left|0\dots 0\right\rangle=\frac{1}{% \sqrt{2^{n}}}\sum_{y_{1},\dots,y_{n}\in\{0,1\}}\left|y_{1},\dots,y_{n}\right\rangle (5.10)

Die Notation ∑y1,…,yn∈{0,1}\sum_{y_{1},\dots,y_{n}\in\{0,1\}} bedeutet, dass die Summe von |y1,…,yn⟩\left|y_{1},\dots,y_{n}\right\rangle über alle möglichen Kombinationen von den Bits y1,…,yny_{1},\dots,y_{n} gebildet wird.

Allgemeiner gesagt ist die Ausgabe auf einem beliebigen Basiszustand immer eine superposition von allen 2n2^{n} Basiszuständen mit gleichen Amplituden, bis auf Vorzeichen. Diese Vorzeichen genauer zu bestimmen kann manchmal schwierig sein.

Übungsaufgabe 5.4 (Zwei Hadamards).

In Gl. 2.34 hatten wir gesehen, dass H⁢|x1⟩=(|0⟩+(−1)x1⁢|1⟩)/2H\left|x_{1}\right\rangle=\left\lparen\left|0\right\rangle+(-1)^{x_{1}}\left|1% \right\rangle\right\rparen/\sqrt{2} für alle x1∈{0,1}x_{1}\in\{0,1\} gilt.

  1. 1.
    ​

    Schreibe den Zustand H⁢|x1⟩H\left|x_{1}\right\rangle für beliebige x1∈{0,1}x_{1}\in\{0,1\} wie folgt:

    H⁢|x1⟩=12⁢∑y1∈{0,1}(−1)???⁢|y1⟩,H\left|x_{1}\right\rangle=\frac{1}{\sqrt{2}}\sum_{y_{1}\in\{0,1\}}(-1)^{% \framebox{???}}\left|y_{1}\right\rangle,

    wobei ??? ein Ausdruck ist, der x1,y1∈{0,1}x_{1},y_{1}\in\{0,1\} enthält. Finde diesen Ausdruck.

  2. 2.
    ​

    Schreibe den Zustand (H⊗H)⁢|x1,x2⟩(H\otimes H)\left|x_{1},x_{2}\right\rangle für beliebige x1,x2∈{0,1}x_{1},x_{2}\in\{0,1\} wie folgt:

    (H⊗H)⁢|x1,x2⟩=12⁢∑y1,y2∈{0,1}(−1)???⁢|y1,y2⟩,(H\otimes H)\left|x_{1},x_{2}\right\rangle=\frac{1}{2}\sum_{y_{1},y_{2}\in\{0,% 1\}}(-1)^{\framebox{???}}\left|y_{1},y_{2}\right\rangle,

    wobei ??? ein Ausdruck ist, der x1,x2,y1,y2∈{0,1}x_{1},x_{2},y_{1},y_{2}\in\{0,1\} enthält.
    Findest du auch diesen Ausdruck?

Lösung.
  1. 1.
    ​

    Hier steht ??? für x1⁢y1x_{1}y_{1}.

  2. 2.
    ​

    Für n=2n=2,

    (H⊗H)⁢|x1,x2⟩\displaystyle(H\otimes H)\left|x_{1},x_{2}\right\rangle =(H⁢|x1⟩)⊗(H⁢|x2⟩)\displaystyle=(H\left|x_{1}\right\rangle)\otimes(H\left|x_{2}\right\rangle)
    =(12⁢∑y1∈{0,1}(−1)x1⁢y1⁢|y1⟩)⊗(12⁢∑y2∈{0,1}(−1)x2⁢y2⁢|y2⟩)\displaystyle=\left\lparen\frac{1}{\sqrt{2}}\sum_{y_{1}\in\{0,1\}}(-1)^{x_{1}y% _{1}}\left|y_{1}\right\rangle\right\rparen\otimes\left\lparen\frac{1}{\sqrt{2}% }\sum_{y_{2}\in\{0,1\}}(-1)^{x_{2}y_{2}}\left|y_{2}\right\rangle\right\rparen
    =12⁢∑y1,y2∈{0,1}(−1)x1⁢y1⁢(−1)x2⁢y2⁢|y1⟩⊗|y2⟩\displaystyle=\frac{1}{2}\sum_{y_{1},y_{2}\in\{0,1\}}(-1)^{x_{1}y_{1}}(-1)^{x_% {2}y_{2}}\left|y_{1}\right\rangle\otimes\left|y_{2}\right\rangle
    =12⁢∑y1,y2∈{0,1}(−1)x1⁢y1+x2⁢y2⁢|y1,y2⟩,\displaystyle=\frac{1}{2}\sum_{y_{1},y_{2}\in\{0,1\}}(-1)^{x_{1}y_{1}+x_{2}y_{% 2}}\left|y_{1},y_{2}\right\rangle,

    also steht ??? für x1⁢y1+x2⁢y2x_{1}y_{1}+x_{2}y_{2}.

Hast du die Lösung gefunden? Gut, dann darfst du weiter lesen!

Im Allgemeinen kann man sich die folgende Formel herleiten, die die Vorzeichen der Amplituden beschreibt, die man erhält, wenn man die Hadamard-Transformation auf einen beliebigen nn-Qubit-Basiszustand anwendet: Für alle x1,…,xn∈{0,1}x_{1},\dotsc,x_{n}\in\{0,1\},

(H⊗⋯⊗H)⁢|x1,…,xn⟩=12n⁢∑y1,…,yn∈{0,1}(−1)x1⁢y1+…+xn⁢yn⁢|y1,…,yn⟩.(H\otimes\dotsb\otimes H)\left|x_{1},\dots,x_{n}\right\rangle=\frac{1}{\sqrt{2% ^{n}}}\sum_{y_{1},\dots,y_{n}\in\{0,1\}}(-1)^{x_{1}y_{1}+\ldots+x_{n}y_{n}}% \left|y_{1},\dots,y_{n}\right\rangle. (5.11)

Nun können wir den Algorithmus von Deutsch recht einfach verallgemeinern. Wir starten mit einem nn-Qubit-Basiszustand |0⁢…⁢0⟩\left|0\dots 0\right\rangle, wenden zunächst die Hadamard-Transformation an und anschließend das Phasen-Orakel OfO_{f} der Funktion f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\}, die wir untersuchen wollen, und abschließend eine weitere Hadamard-Transformation. Für beispielsweise n=3n=3 ergibt sich der folgende Schaltkreis in Quirky:

[Uncaptioned image]

Für allgemeine nn lässt sich der finale nn-Qubit-Zustand wie folgt beschreiben:

(H⊗⋯⊗H)⁢Of⁢(H⊗⋯⊗H)⁢|0⁢…⁢0⟩.\displaystyle(H\otimes\dotsb\otimes H)O_{f}(H\otimes\dotsb\otimes H)\left|0% \dots 0\right\rangle. (5.12)

Können wir das auch expliziter schreiben? Wie schon zuvor, rechnen wir Schritt für Schritt. Zunächst wenden wir die Hadamard-Transformation auf den Null-Basiszustand an. Nach Gl. 5.10 erhalten wir die uniforme Überlagerung aller Basiszustände:

(H⊗⋯⊗H)⁢|0⁢…⁢0⟩=12n⁢∑x1,…,xn∈{0,1}|x1,…,xn⟩.\displaystyle(H\otimes\dotsb\otimes H)\left|0\dots 0\right\rangle=\frac{1}{% \sqrt{2^{n}}}\sum_{x_{1},\dots,x_{n}\in\{0,1\}}\left|x_{1},\dots,x_{n}\right\rangle.

Anschließend wenden wir das Phasen-Orakel OfO_{f} an:

Of⁢(H⊗⋯⊗H)⁢|0⁢…⁢0⟩\displaystyle O_{f}(H\otimes\dotsb\otimes H)\left|0\dots 0\right\rangle =12n⁢∑x1,…,xn∈{0,1}(−1)f⁢(x1,…,xn)⁢|x1,…,xn⟩.\displaystyle=\frac{1}{\sqrt{2^{n}}}\sum_{x_{1},\dots,x_{n}\in\{0,1\}}(-1)^{f(% x_{1},\dots,x_{n})}\left|x_{1},\dots,x_{n}\right\rangle.

Was erreicht die abschließende Hadamard-Transformation? Durch Linearität können wir Gl. 5.11 auf jeden Basisvektor anwenden, also erhalten wir den folgenden Ausdruck für den Zustand in Gl. 5.12:

(H⊗⋯⊗H)⁢Of⁢(H⊗⋯⊗H)⁢|0⁢…⁢0⟩\displaystyle\quad(H\otimes\dotsb\otimes H)O_{f}(H\otimes\dotsb\otimes H)\left% |0\dots 0\right\rangle
=12n⁢∑x1,…,xn∈{0,1}(−1)f⁢(x1,…,xn)⁢12n⁢∑y1,…,yn∈{0,1}(−1)x1⁢y1+…+xn⁢yn⁢|y1,…,yn⟩\displaystyle=\frac{1}{\sqrt{2^{n}}}\sum_{x_{1},\dots,x_{n}\in\{0,1\}}(-1)^{f(% x_{1},\dots,x_{n})}\frac{1}{\sqrt{2^{n}}}\sum_{y_{1},\dots,y_{n}\in\{0,1\}}(-1% )^{x_{1}y_{1}+\ldots+x_{n}y_{n}}\left|y_{1},\dots,y_{n}\right\rangle
=∑y1,…,yn∈{0,1}12n⁢(∑x1,…,xn∈{0,1}(−1)x1⁢y1+…+xn⁢yn⁢(−1)f⁢(x1,…,xn))⁢|y1,…,yn⟩,\displaystyle=\sum_{y_{1},\dots,y_{n}\in\{0,1\}}\frac{1}{2^{n}}\left(\sum_{x_{% 1},\dots,x_{n}\in\{0,1\}}(-1)^{x_{1}y_{1}+\ldots+x_{n}y_{n}}(-1)^{f(x_{1},% \dots,x_{n})}\right)\left|y_{1},\dots,y_{n}\right\rangle, (5.13)

wobei die zwei Summen im letzten Schritt getauscht wurden. Für n=1n=1 entspricht das genau Gl. 5.7. Im Allgemeinen sieht dieser Ausdruck aber kompliziert und schwer zu interpretieren aus – es scheint, der Schaltkreis berechnet eine Superposition der Basiszustände, wobei die Amplitude eine seltsame Summe von Plus- und Minuszeichen ist!

Wir können versuchen ein intuitives Verständnis zu erreichen, indem wir uns die Amplitude von |0⁢…⁢0⟩\left|0\dots 0\right\rangle in Gl. 5.13 anschauen. Das Quadrat dieser Zahl ist die Wahrscheinlichkeit, dass beim messen der nn Qubits alle Ergebnisse Null sind. Da diese Amplitude y1=…=yn=0y_{1}=\ldots=y_{n}=0 entspricht, ist sie gegeben durch

12n⁢∑x1,…,xn∈{0,1}(−1)f⁢(x1,…,xn).\displaystyle\frac{1}{2^{n}}\sum_{x_{1},\dots,x_{n}\in\{0,1\}}(-1)^{f(x_{1},% \dots,x_{n})}.

Aber was bedeutet das? Nehmen wir an, es gibt NfN_{f} Eingabe-Bitstrings für die ff Null ergibt und 2n−Nf2^{n}-N_{f} Bitstrings für die ff Eins ergibt. Dann,

12n⁢∑x1,…,xn∈{0,1}(−1)f⁢(x1,…,xn)=Nf−(2n−Nf)2n=2⁢Nf−2n2n.\displaystyle\frac{1}{2^{n}}\sum_{x_{1},\dots,x_{n}\in\{0,1\}}(-1)^{f(x_{1},% \dots,x_{n})}=\frac{N_{f}-(2^{n}-N_{f})}{2^{n}}=\frac{2N_{f}-2^{n}}{2^{n}}.

Dabei gibt es zwei interessante Extremfälle: 1414 14 Für n=1n=1 ist jede Funktion entweder konstant oder balanced. Für n>1n>1 ist das nicht der Fall (z.B. ist die AND-Funktion weder konstant noch balanced).

  • •
    ​

    Wenn ff eine konstante Funktion ist, gilt entweder Nf=0N_{f}=0 (für die Alles-Null-Funktion) oder Nf=2nN_{f}=2^{n} (für die Alles-Eins-Funktion). In jedem Fall ist die Amplitude ±2n/2n=±1\pm 2^{n}/2^{n}=\pm 1. Da die Summe der Quadrate der Amplituden genau 1 ergeben muss, können wir Schlussfolgern, dass alle anderen Amplituden in Gl. 5.13 genau 0 sein müssen. Mit anderen Worten, wenn ff konstant ist, muss der Zustand in Gl. 5.13 einfach ±|0⁢…⁢0⟩\pm\left|0\dots 0\right\rangle. Wenn wir alle nn Qubits dieses Zustands messen, müssen alle Ergebnisse Null sein.

  • •
    ​

    Wenn ff eine balanced Funktion1515 15 (engl. für “gleichmäßig/balanciert”) ist, also das Ergebnis der Funktion genauso oft Null wie Eins ist, dann ist Nf=2n/2N_{f}=2^{n}/2 und die Amplitude ist 0. Wenn man also den Zustand in Gl. 5.13 misst, werden niemals alle Ergebnisse Null sein. Also wird für eine balanced Funktion immer mindestens ein Messergbnis Eins sein.

Bemerke, dass diese zwei Fälle sehr verschiedenen Interferenzmustern entsprechen (siehe Abschnitt 2.6.1). Im ersten Fall wird die Amplitude von |0⁢…⁢0⟩\left|0\dots 0\right\rangle durch stark fokussierte konstruktive Interferenz zu ±1\pm 1 verstärkt, wobei gleichzeitig alle anderen Amplituden durch verbreitete destruktive Interferenz verschwinden. Im zweiten Fall erfährt |0⁢…⁢0⟩\left|0\dots 0\right\rangle dagegen destruktive Interferenz, wodurch überall sonst Nicht-Null-Amplituden auftauchen. Die Hadamard-Transformation zeigt auf wie wichtig Interferenz für die Quanteninformatik ist. In den nächsten zwei Abschnitten wird sie eine entscheidende Rolle für das Design von Quantenalgorithmen auf vielen Qubits spielen.