5.1.3 Phasen-Orakel

Da das Bit-Orakel UfU_{f} eine Quantenoperation ist, können wir sie nicht nur auf Basiszustände |x1,…,xn,y⟩\left|x_{1},\dots,x_{n},y\right\rangle,sondern auch auf allgemeinere Quantenzustände anwenden. Aber warum würden wir das tun wollen? Nun, wenn wir dem Orakel nur ‘klassische’ Fragen stellen, werden wir wahrscheinlich keine Quanten-Verbesserung erreichen! Deswegen wollen wir einmal untersuchen, wie sich das Bit-Orakel UfU_{f} für eine beliebige Funktion f:{0,1}n→{0,1}f:\{0,1\}^{n}\to\{0,1\} verhält, wenn wir das letzte Register auf |−⟩=(|0⟩−|1⟩)/2\left|-\right\rangle=(\left|0\right\rangle-\left|1\right\rangle)/\sqrt{2} setzen. Zuerst bemerken wir den folgenden interessanten Fakt:

NOT⁢|−⟩=12⁢(NOT⁢|0⟩−NOT⁢|1⟩)=12⁢(|1⟩−|0⟩)=−|−⟩.\displaystyle\mathrm{NOT}\left|-\right\rangle=\frac{1}{\sqrt{2}}\left\lparen% \mathrm{NOT}\left|0\right\rangle-\mathrm{NOT}\left|1\right\rangle\right\rparen% =\frac{1}{\sqrt{2}}\left\lparen\left|1\right\rangle-\left|0\right\rangle\right% \rparen=-\left|-\right\rangle.

Soll bedeuten, wenn wir ein Qubit im Zustand |−⟩\left|-\right\rangle invertieren erhalten wir ein Vorzeichen. Genauso können wir auch berechnen, wie sich das Bit-Orakel auf einen Zustand der Form |x1,…,xn⟩⊗|−⟩\left|x_{1},\dots,x_{n}\right\rangle\otimes\left|-\right\rangle auswirkt. Durch Linearität gibt uns Gl. 5.5, dass

Uf⁢(|x1,…,xn⟩⊗|−⟩)\displaystyle\quad U_{f}\left(\left|x_{1},\dots,x_{n}\right\rangle\otimes\left% |-\right\rangle\right)
=Uf⁢(12⁢|x1,…,xn⁢,0⟩−12⁢|x1,…,xn⁢,1⟩)\displaystyle=U_{f}\bigl{(}\frac{1}{\sqrt{2}}\left|x_{1},\dots,x_{n},0\right% \rangle-\frac{1}{\sqrt{2}}\left|x_{1},\dots,x_{n},1\right\rangle\bigr{)}
=12⁢|x1,…,xn,f⁢(x1,…,xn)⟩−12⁢|x1,…,xn,f⁢(x1,…,xn)⊕1⟩\displaystyle=\frac{1}{\sqrt{2}}\left|x_{1},\dots,x_{n},f(x_{1},\dots,x_{n})% \right\rangle-\frac{1}{\sqrt{2}}\left|x_{1},\dots,x_{n},f(x_{1},\dots,x_{n})% \oplus 1\right\rangle
=|x1,…,xn⟩⊗12⁢(|f⁢(x1,…,xn)⟩−|f⁢(x1,…,xn)⊕1⟩)\displaystyle=\left|x_{1},\dots,x_{n}\right\rangle\otimes\frac{1}{\sqrt{2}}% \bigl{(}\left|f(x_{1},\dots,x_{n})\right\rangle-\left|f(x_{1},\dots,x_{n})% \oplus 1\right\rangle\bigr{)}
=(−1)f⁢(x1,…,xn)⁢|x1,…,xn⟩⊗|−⟩.\displaystyle=(-1)^{f(x_{1},\dots,x_{n})}\left|x_{1},\dots,x_{n}\right\rangle% \otimes\left|-\right\rangle.

Mit anderen Worten erhalten wir wieder den Zustand |−⟩\left|-\right\rangle, allerdings mit einem negativen Vorzeichen wenn f⁢(x1,…,xn)=1f(x_{1},\dots,x_{n})=1. Somit haben wir also folgende Quantenoperation auf den ersten nn Qubit gebaut:

Of⁢|x1,…,xn⟩=(−1)f⁢(x1,…,xn)⁢|x1,…,xn⟩,O_{f}\left|x_{1},\dots,x_{n}\right\rangle=(-1)^{f(x_{1},\dots,x_{n})}\left|x_{% 1},\dots,x_{n}\right\rangle, (5.6)

für alle Bitstrings x1,…,xn∈{0,1}x_{1},\dots,x_{n}\in\{0,1\}. Wir nennen OfO_{f} das Phasen-Orakel für ff.

Interessanterweise arbeitet das Phasen-Orakel OfO_{f} für eine Funktion f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} auf nn Qubits, da das Ergebnis in der Amplitude gespeichert wird. Das ist ein Unterschied zum Bit-Orakel UfU_{f}, welches für die Ausgabe ein zusätzliches Qubit benötigt und deswegen auf n+1n+1 arbeitet.

Auf den ersten Blick scheint das Phasen-Orakel nicht viel zu machen, da es bei Anwendung auf einem Basiszustand nur ein allgemeines Vorzeichen einfügt, wobei wir aus 2.7 wissen, dass dieses nicht gemessen werden kann. Wenn wir es aber auf einen Zustand in superposition anwenden, kann das Phasen-Orakel ein relatives Vorzeichen einfügen, was zu interessanten Ergebnissen führen kann. Wenden wir beispielsweise für n=2n=2 Qubits das Phasen-Orakel auf einen allgemeinen Zwei-Qubit-Zustand

|ψ⟩=ψ00⁢|00⟩+ψ01⁢|01⟩+ψ10⁢|10⟩+ψ11⁢|11⟩\displaystyle\left|\psi\right\rangle=\psi_{00}\left|00\right\rangle+\psi_{01}% \left|01\right\rangle+\psi_{10}\left|10\right\rangle+\psi_{11}\left|11\right\rangle

an, erhalten wir

Of⁢|ψ⟩=(−1)f⁢(0,0)⁢ψ00⁢|00⟩+(−1)f⁢(0,1)⁢ψ01⁢|01⟩+(−1)f⁢(1,0)⁢ψ10⁢|10⟩+(−1)f⁢(1,1)⁢ψ11⁢|11⟩.\displaystyle O_{f}\left|\psi\right\rangle=(-1)^{f(0,0)}\psi_{00}\left|00% \right\rangle+(-1)^{f(0,1)}\psi_{01}\left|01\right\rangle+(-1)^{f(1,0)}\psi_{1% 0}\left|10\right\rangle+(-1)^{f(1,1)}\psi_{11}\left|11\right\rangle.

Es stellt sich heraus, dass das Phasen-Orakel OfO_{f} nützlicher und meist einfacher in Quantenalgorithmen anzuwenden ist als das Bit-Orakel UfU_{f}, weswegen wir das Bit-Orakel nicht mehr weiter benutzen.

Übungsaufgabe 5.2 (Phasen-Orakel für eine Ein-Qubit-Funktion).

Erinnere dich an 5.1, wo die vier Funktionen f:{0,1}→{0,1}f:\{0,1\}\to\{0,1\} mit einem Eingabe- und Ausgabe-Bit vorgestellt wurden. Kannst du das Phasen-Orakel OfO_{f} für jede davon in Quirky implementieren?

Lösung. Es gibt vier Funktionen: die ‘Identitäts’-Funktion f⁢(x)=xf(x)=x, die NOT-Funktion, die Alles-Null-Funktion und die Alles-Eins-Funktion.
  • •
    ​

    Für die Identitäts-Funktion f⁢(x)=xf(x)=x kann Gl. 5.6 gelesen werden als

    Of⁢|x⟩=(−1)x⁢|x⟩,\displaystyle O_{f}\left|x\right\rangle=(-1)^{x}\left|x\right\rangle,

    also ist das genau das Z-Gatter:

    [Uncaptioned image]

  • •
    ​

    Für die NOT-Funktion f⁢(x)=NOT⁢(x)f(x)=\mathrm{NOT}(x) soll gelten, dass

    Of⁢|x⟩=(−1)NOT⁢(x)⁢|x⟩=NOT⁢Z⁢NOT⁢|x⟩,\displaystyle O_{f}\left|x\right\rangle=(-1)^{\mathrm{NOT}(x)}\left|x\right% \rangle=\mathrm{NOT}\,Z\,\mathrm{NOT}\left|x\right\rangle,

    was folgender Reihe an Operationen entspricht:

    [Uncaptioned image]

  • •
    ​

    Für die Alles-Null-Funktion f⁢(0)=f⁢(1)=0f(0)=f(1)=0 gilt:

    Of⁢|x⟩=|x⟩,\displaystyle O_{f}\left|x\right\rangle=\left|x\right\rangle,

    daher müssen wir nichts tun:

    [Uncaptioned image]

  • •
    ​

    Für die Alles-Eins-Funktion f⁢(0)=f⁢(1)=1f(0)=f(1)=1 gilt:

    Of⁢|x⟩=−|x⟩,\displaystyle O_{f}\left|x\right\rangle=-\left|x\right\rangle,

    was wir erreichen, indem wir die ersten beiden Orakel nacheinander schalten:

    [Uncaptioned image]

    Tatsächlich fügt das erste Orakel ein Minuszeichen hinzu, wenn x=1x=1 ist, während das zweite Orakel ein Minuszeichen hinzuzufügt, wenn x=0x=0 ist, also erhalten wir immer eines:

    NOT⁢Z⁢NOT⁢Z⁢|0⟩\displaystyle\mathrm{NOT}\,Z\,\mathrm{NOT}\,Z\left|0\right\rangle =NOT⁢Z⁢NOT⁢|0⟩=−|0⟩,\displaystyle=\mathrm{NOT}\,Z\,\mathrm{NOT}\left|0\right\rangle=-\left|0\right\rangle,
    NOT⁢Z⁢NOT⁢Z⁢|1⟩\displaystyle\mathrm{NOT}\,Z\,\mathrm{NOT}\,Z\left|1\right\rangle =NOT⁢Z⁢NOT⁢(−|1⟩)=−NOT⁢Z⁢NOT⁢|1⟩=−|1⟩.\displaystyle=\mathrm{NOT}\,Z\,\mathrm{NOT}(-\left|1\right\rangle)=-\mathrm{% NOT}\,Z\,\mathrm{NOT}\left|1\right\rangle=-\left|1\right\rangle.

    Im vorletzten Schritt haben wir dabei die Linearität ausgenutzt, um das Minuszeichen nach vorne zu bringen.

Hausaufgabe 5.1 (Bestimme die Funktion anhand ihres Phasen-Orakels).

Betrachte den folgenden Zwei-Qubit-Schaltkreis (wie üblich ist der untere Draht das erste Qubit):

[Uncaptioned image]

Für welche Funktion f:{0,1}2→{0,1}f\colon\{0,1\}^{2}\to\{0,1\} stellt der Schaltkreis das Phasen-Orakel dar?

Hinweis: Benutze, dass H⁢NOT⁢H=ZH\,\mathrm{NOT}\,H=Z, was aus 4.5 folgt.

Hack.

Der Schaltkreis entspricht der folgenden Zwei-Qubit-Operation:

U=(I⊗H)⁢CNOT1→2⁢(I⊗H)\displaystyle U=(I\otimes H)\mathrm{CNOT}_{1\to 2}(I\otimes H)

Wie wirkt sich diese Operation auf einen Zwei-Qubit-Basiszustand aus?

U⁢|a,b⟩=(I⊗H)⁢CNOT1→2⁢(I⊗H)⁢|a,b⟩=(I⊗H)⁢CNOT1→2⁢(|a⟩⊗H⁢|b⟩).\displaystyle U\left|a,b\right\rangle=(I\otimes H)\mathrm{CNOT}_{1\to 2}(I% \otimes H)\left|a,b\right\rangle=(I\otimes H)\mathrm{CNOT}_{1\to 2}(\left|a% \right\rangle\otimes H\left|b\right\rangle).

Wenn a=0a=0 ist, invertiert die kontrollierte-NOT-Funktion das zweite Qubit nicht, also:

U⁢|0,b⟩\displaystyle U\left|0,b\right\rangle =(I⊗H)⁢CNOT1→2⁢(|0⟩⊗H⁢|b⟩)\displaystyle=(I\otimes H)\mathrm{CNOT}_{1\to 2}(\left|0\right\rangle\otimes H% \left|b\right\rangle)
=(I⊗H)⁢(|0⟩⊗H⁢|b⟩)\displaystyle=(I\otimes H)(\left|0\right\rangle\otimes H\left|b\right\rangle)
=|0⟩⊗H⁢H⁢|b⟩\displaystyle=\left|0\right\rangle\otimes H\,H\left|b\right\rangle
=|0,b⟩,\displaystyle=\left|0,b\right\rangle,

da H⁢H=IHH=I. Aber wenn a=1a=1 ist, dann wird das zweite Qubit durch die kontrollierte-NOT-Operation invertiert, also gilt:

U⁢|1,b⟩\displaystyle U\left|1,b\right\rangle =(I⊗H)⁢CNOT1→2⁢(|1⟩⊗H⁢|b⟩)\displaystyle=(I\otimes H)\mathrm{CNOT}_{1\to 2}(\left|1\right\rangle\otimes H% \left|b\right\rangle)
=(I⊗H)⁢(|1⟩⊗NOT⁢H⁢|b⟩)\displaystyle=(I\otimes H)(\left|1\right\rangle\otimes\mathrm{NOT}\,H\left|b% \right\rangle)
=|1⟩⊗H⁢NOT⁢H⁢|b⟩\displaystyle=\left|1\right\rangle\otimes H\,\mathrm{NOT}\,H\left|b\right\rangle
=|1⟩⊗Z⁢|b⟩\displaystyle=\left|1\right\rangle\otimes Z\left|b\right\rangle
=(−1)b⁢|1,b⟩\displaystyle=(-1)^{b}\left|1,b\right\rangle

(im vorletzten Schritt haben wir den Hinweis genutzt). Also:

U⁢|00⟩\displaystyle U\left|00\right\rangle =|00⟩\displaystyle=\left|00\right\rangle
U⁢|01⟩\displaystyle U\left|01\right\rangle =|01⟩\displaystyle=\left|01\right\rangle
U⁢|10⟩\displaystyle U\left|10\right\rangle =|10⟩\displaystyle=\left|10\right\rangle
U⁢|11⟩\displaystyle U\left|11\right\rangle =−|11⟩,\displaystyle=-\left|11\right\rangle,

und so stellen wir fest, dass UU genau das Phasen-Orakel für die AND\operatorname{AND}-Funktion implementiert.

Lass uns kurz zusammenfassen, was wir bisher erreicht haben: Mit Bit-Orakeln können wir Quantencomputer eine Funktion f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} genau so auswerten lassen, wie mit einem klassischen Computern, der umkehrbar agiert (vergleiche Gl. 5.4 und 5.5). Das ist wichtig, da wir also nicht Äpfel mit Birnen vergleichen wenn wir zählen, wie viele Fragen man das Bit-Orakel UfU_{f} fragen muss, um eine Eigenschaft über ff zu lernen, im Vergleich zu wie oft man ff auf einem klassischen Computer auswerten muss, um die gleiche Eigenschaft zu lernen. Und da wir gerade gezeigt haben, dass man das Phasen-Orakel OfO_{f} immer mit einem Bit-Orakel UfU_{f} bauen kann, macht es keinen Unterschied wenn wir stattdessen das Phasen-Orakel OfO_{f} fragen