5.3 Suchen mit Grover

Nachdem Hila und Iman wieder sicher auf der Erde gelandet sind, wurden sie gute Freunde von Alice und Bob. Die vier entscheiden sich, Silvester zusammen zu verbringen. Zufällig ist am selben Tag auch die Ziehung des jährlichen Quanten-Lottos! Sie wissen, dass nur eine Person der vier den großen Gewinn absahnen kann, aber wer wird es sein? Wenn wir unsere vier Hauptfiguren mit Bitstrings benennen, zum Beispiel so,

x1x_{1} x2x_{2}
Alice 0 0
Bob 0 1
Hila 1 0
Iman 1 1

dann können wir die Lotterie durch eine Funktion f:{0,1}2→{0,1}f\colon\{0,1\}^{2}\to\{0,1\} modellieren, die nur für die gewinnende Person 1 ergibt. Wenn zum Beispiel f⁢(1,0)=1f(1,0)=1 ist, dann hat Hila dieses Jahr gewonnen.

Wie können unsere Freunde herausfinden, wer gewonnen hat? Mit einem klassischen Algorithmus müssen sie die Funktion bis zu drei mal ausführen um herauszufinden, wer ausgelost wurde. Angenommen, sie wüssten, dass f⁢(0,1)=0f(0,1)=0 und f⁢(1,0)=0f(1,0)=0 – dann ist immer noch nicht klar ob Alice oder Iman gewonnen haben! Aus längst vergessenen Gründen besagen die Regeln der Lotterie aber, dass die Funktion nur einmal ausgewertet werden darf.

Die vier setzen sich zusammen und fangen an zu überlegen. Nach einer Weile wird Bob ungeduldig und schlägt vor: “Lasst uns doch einfach den ersten Schritten des Deutsch-Jozsa- und Bernstein-Vazirani-Algorithmus folgen – bestimmt klappt der selbe Trick nochmal…” Da die anderen keine bessere Idee haben, bereiten sie den folgenden Zustand vor

(H⊗H)⁢(|0⟩⊗|0⟩)=|+⟩⊗|+⟩=12⁢(|00⟩+|01⟩+|10⟩+|11⟩).\displaystyle(H\otimes H)(\left|0\right\rangle\otimes\left|0\right\rangle)=% \left|+\right\rangle\otimes\left|+\right\rangle=\frac{1}{2}\bigl{(}\left|00% \right\rangle+\left|01\right\rangle+\left|10\right\rangle+\left|11\right% \rangle\bigr{)}.

Anschließend geben sie diesen Zustand der Quanten-Lotterie, welche das Phasen-Orakel OfO_{f} anwendet und den Zustand zurück gibt. Seien aa und bb die beiden Bits, die die gewinnende Person festlegen, also f⁢(a,b)=1f(a,b)=1 und alle anderen Funktionswerte sind Null. Dann erhalten sie von der Quanten-Lotterie den folgenden Zwei-Qubit-Zustand:

12⁢(|00⟩+|01⟩+|10⟩+|11⟩−2⁢|a,b⟩)\displaystyle\quad\frac{1}{2}\bigl{(}\left|00\right\rangle+\left|01\right% \rangle+\left|10\right\rangle+\left|11\right\rangle-2\left|a,b\right\rangle% \bigr{)}
=12⁢(|00⟩+|01⟩+|10⟩+|11⟩)−|a,b⟩\displaystyle=\frac{1}{2}\bigl{(}\left|00\right\rangle+\left|01\right\rangle+% \left|10\right\rangle+\left|11\right\rangle\bigr{)}-\left|a,b\right\rangle
=|+⟩⊗|+⟩−|a⟩⊗|b⟩,\displaystyle=\left|+\right\rangle\otimes\left|+\right\rangle-\left|a\right% \rangle\otimes\left|b\right\rangle,

wobei die −2⁢|a,b⟩-2\left|a,b\right\rangle in der ersten Zeile eins der Plus-Zeichen durch ein Minus ersetzt. Nach dem anwenden einer Hadamard-Transformation erhalten sie den folgenden Zustand:

|0⟩⊗|0⟩−H⁢|a⟩⊗H⁢|b⟩\displaystyle\quad\left|0\right\rangle\otimes\left|0\right\rangle-H\left|a% \right\rangle\otimes H\left|b\right\rangle
=|00⟩−12⁢(|0⟩+(−1)a⁢|1⟩)⊗(|0⟩+(−1)b⁢|1⟩)\displaystyle=\left|00\right\rangle-\frac{1}{2}\Bigl{(}\left|0\right\rangle+(-% 1)^{a}\left|1\right\rangle\Bigr{)}\otimes\Bigl{(}\left|0\right\rangle+(-1)^{b}% \left|1\right\rangle\Bigr{)}
=−12⁢(−|00⟩+(−1)a⁢|10⟩+(−1)b⁢|01⟩+(−1)a+b⁢|11⟩)\displaystyle=-\frac{1}{2}\Bigl{(}-\left|00\right\rangle+(-1)^{a}\left|10% \right\rangle+(-1)^{b}\left|01\right\rangle+(-1)^{a+b}\left|11\right\rangle% \Bigr{)}

Jetzt sind sie verwirrt und wissen nicht ganz weiter. Hila hat eine Idee: “Mich stört das Minuszeichen vor |00⟩\left|00\right\rangle. Warum wenden wir nicht eine Quantenoperation an, die so funktioniert?”

|00⟩\displaystyle\left|00\right\rangle ↦−|00⟩\displaystyle\mapsto-\left|00\right\rangle (5.16)
|01⟩\displaystyle\left|01\right\rangle ↦|01⟩\displaystyle\mapsto\left|01\right\rangle
|10⟩\displaystyle\left|10\right\rangle ↦|10⟩\displaystyle\mapsto\left|10\right\rangle
|11⟩\displaystyle\left|11\right\rangle ↦|11⟩\displaystyle\mapsto\left|11\right\rangle

Iman fällt ein: “Ich glaube ich weiß wie wir diese Operation mit einer kontrollierten-Z-Operation und ein paar NOT-Operationen bauen könnenn…” Nach kurzer Zeit erhält die Gruppe also den folgenden Zustand:

−12⁢(|00⟩+(−1)a⁢|10⟩+(−1)b⁢|01⟩+(−1)a+b⁢|11⟩)\displaystyle-\frac{1}{2}\Bigl{(}\left|00\right\rangle+(-1)^{a}\left|10\right% \rangle+(-1)^{b}\left|01\right\rangle+(-1)^{a+b}\left|11\right\rangle\Bigr{)}

Nach einem kurzen Moment bemerkt Alice: “Den Zwei-Qubit-Zustand können wir als Tensorprodukt schreiben!”

−12⁢(|0⟩+(−1)a⁢|1⟩)⊗(|0⟩+(−1)b⁢|1⟩)=−(H⊗H)⁢|a,b⟩.\displaystyle-\frac{1}{2}\Bigl{(}\left|0\right\rangle+(-1)^{a}\left|1\right% \rangle\Bigr{)}\otimes\Bigl{(}\left|0\right\rangle+(-1)^{b}\left|1\right% \rangle\Bigr{)}=-(H\otimes H)\left|a,b\right\rangle.

Bob freut sich riesig: “Aha! Wir müssen nur noch eine weitere Hadamard-Transformation anwenden und können dann beide Qubits messen…” Kannst du herausfinden, wer die diesjährige Quanten-Lotterie gewinnen wird?

Hausaufgabe 5.5 (Quanten-Lotterie).
  1. 1.
    ​

    Schreibe die Quantenoperation aus Gl. 5.16 mit einer kontrollierten-Z-Operation und ein paar NOT-Operationen.

    Hinweis: Erinnere dich, dass die kontrollierte-Z-Operation C⁢Z1→2CZ_{1\to 2} auf einem Basiszustand |x,y⟩\left|x,y\right\rangle sich wie folgt verhält: Wenn x=0x=0 tut sie nichts. Wenn x=1x=1, verhält sie sich wie ZZ auf dem zweiten Qubit. Letzte Woche hast du gelernt, sie in Quirky zu bauen.

  2. 2.
    ​

    Baue den Quantenalgorithmus, den Alice, Bob, Hila und Iman sich ausgedacht haben in Quirky und finde heraus, wer dieses Jahr die Quanten-Lotterie gewinnt.

Hack.
  1. 1.
    ​

    Wir können die Quantenoperation aus Gl. 5.16 schreiben als

    (NOT⊗NOT)⁢C⁢Z1→2⁢(NOT⊗NOT).\displaystyle(\mathrm{NOT}\otimes\mathrm{NOT})CZ_{1\to 2}(\mathrm{NOT}\otimes% \mathrm{NOT}).

    Das funktioniert, weil C⁢Z1→2CZ_{1\to 2} wie folgt funktioniert (aufgrund der Funktion von ZZ sowie des Hinweises)

    |00⟩\displaystyle\left|00\right\rangle ↦|00⟩\displaystyle\mapsto\left|00\right\rangle
    |01⟩\displaystyle\left|01\right\rangle ↦|01⟩\displaystyle\mapsto\left|01\right\rangle
    |10⟩\displaystyle\left|10\right\rangle ↦|10⟩\displaystyle\mapsto\left|10\right\rangle
    |11⟩\displaystyle\left|11\right\rangle ↦−|11⟩\displaystyle\mapsto-\left|11\right\rangle

    Das entspricht fast dem, was wir wollen, wenn wir nur die Rollen von 0 und 11 in allen Ein- und Ausgabebits tauschen könnten. Aber das ist genau was NOT\mathrm{NOT} tut! Also wenden wir NOT\mathrm{NOT} auf alle Bits vor und nach dem C⁢Z1→2CZ_{1\to 2} an.

  2. 2.
    ​

    In Quirky sieht der Schaltkreis dann so aus:

    [Uncaptioned image]

    Das bedeutet, dass Iman die diesjährige Quanten-Lotterie gewinnt!

Der Quantenalgorithmus, den die Gruppe entdeckt haben ist ein Spezialfall von Grovers Algorithmus. Grovers Algorithmus löst das folgende Problem: Gegeben eines Orakels für die Funktion f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} findet er x1,…,xn∈{0,1}x_{1},\dots,x_{n}\in\{0,1\}, sodass f⁢(x1,…,xn)=1f(x_{1},\dots,x_{n})=1. Wir können uns das Problem vorstellen wie das finden einer gewinnenden Person aus 2n2^{n} Teilnehmenden, oder anders gesagt, ein Element, welches eine bestimmte Eigenschaft besitzt aus einer ungeordneten Datenbank (womit wir meinen, dass die Elemente in der Datenbank nicht sortiert sind) zu finden . Mit dem selben Argument wie zuvor, muss jeder klassische Algorithmus schlimmstenfalls alle bis auf einen der 2n2^{n} Einträge anschauen, bevor er fertig ist (durchschnittlich muss die Hälfte der Einträge angeschaut werden). Im Gegensatz dazu braucht Grovers Algorithmus nur proportional zu 2n\sqrt{2^{n}} viele Abfragen, was langsamer wächst in nn! Grovers Algorithmus ist ein sehr vielseitiges Werkzeug, welches ein Quadratwurzel-Speedup für viele Berechnungsprobleme liefert.