5.1.3 Fase-orakels

Omdat het bit-orakel UfU_{f} een quantumbewerking is, kunnen we het niet alleen toepassen op basistoestanden |x1,…,xn,y⟩\left|x_{1},\dotsc,x_{n},y\right\rangle maar ook op algemene quantumtoestanden. Waarom zouden we zoiets willen doen? Wel, als we het orakel alleen ‘klassieke’ vragen stellen dan is er weinig hoop op het bereiken van een quantumversnelling! Laten we, gegeven deze motivering, eens onderzoeken hoe het bit-orakel UfU_{f} voor een arbitraire functie f:{0,1}n→{0,1}f:\{0,1\}^{n}\to\{0,1\} zich gedraagt als het laatste register wordt gezet op |−⟩=(|0⟩−|1⟩)/2\left|-\right\rangle=(\left|0\right\rangle-\left|1\right\rangle)/\sqrt{2}. We merken eerst het volgende interessante gegeven op:

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.

Dat wil zeggen, als we een qubit in de toestand |−⟩\left|-\right\rangle inverteren, dan pikken we een minteken op. We kunnen op dezelfde manier berekenen hoe het bit-orakel werkt op een toestand van de vorm |x1,…,xn⟩⊗|−⟩\left|x_{1},\dotsc,x_{n}\right\rangle\otimes\left|-\right\rangle. Door lineariteit volgt uit Vgl. 5.5 dat

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.

Met andere woorden, de laatste qubit eindigt weer in de toestand |−⟩\left|-\right\rangle, maar we krijgen een minteken als f⁢(x1,…,xn)=1f(x_{1},\dots,x_{n})=1. In feite hebben we de volgende quantumbewerking uitgevoerd op de eerste nn qubits:

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)

voor alle bitstrings x1,…,xn∈{0,1}x_{1},\dots,x_{n}\in\{0,1\}. We noemen OfO_{f} het fase-orakel voor ff.

Opmerkelijk genoeg werkt het fase-orakel OfO_{f} voor een functie f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} op nn qubits, omdat het de uitvoer opslaat in de amplitude. Dit is anders dan het bit-orakel UfU_{f}, dat de uitvoer in een extra qubit opslaat en daarom op n+1n+1 qubits werkt.

Op het eerste gezicht lijkt het fase-orakel niet veel te doen, omdat het alleen een algemeen minteken toevoegt als het werkt op een basistoestand, waarvan we door 2.7 weten dat het niet kan worden gemeten. Maar als we het toepassen op een superpositie kan het fase-orakel relatieve mintekens veroorzaken, waardoor we een interessant resultaat krijgen. Als we bijvoorbeeld voor n=2n=2 qubits een fase-orakel OfO_{f} toepassen op een algemene twee-qubit-toestand

|ψ⟩=ψ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

dan krijgen we

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

Het blijkt dat het fase-orakel OfO_{f} inderdaad handig is en vaak veel gemakkelijker toe te passen is in quantumalgoritmes dan het bit-orakel UfU_{f}, dus vanaf nu zullen we het bit-orakel niet meer gebruiken.

Oefenopgave 5.2 (Fase-orakel voor een één-bitfunctie).

We weten van 5.1 dat er vier functies f:{0,1}→{0,1}f:\{0,1\}\to\{0,1\} met een enkele invoer- en uitvoerbit. Kun je het fase-orakel OfO_{f} voor elk van deze functies implementeren in Quirky?

Solution. Er zijn vier functies: de ’identiteit’-functie f⁢(x)=xf(x)=x, de NOT-functie, de nul-functie en de één-functie.
  • •
    ​

    Voor de identiteit-functie f⁢(x)=xf(x)=x, ziet Vgl. 5.6 eruit als

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

    dus dit is precies de Z-gate:

    [Uncaptioned image]

  • •
    ​

    Voor de NOT-functie f⁢(x)=NOT⁢(x)f(x)=\mathrm{NOT}(x), willen we dat

    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,

    wat neerkomt op de volgende reeks bewerkingen:

    [Uncaptioned image]

  • •
    ​

    Voor de nul-functie met f⁢(0)=f⁢(1)=0f(0)=f(1)=0 geldt:

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

    dus we hoeven helemaal niks te doen:

    [Uncaptioned image]

  • •
    ​

    Voor de één-functie met f⁢(0)=f⁢(1)=1f(0)=f(1)=1 geldt:

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

    wat we kunnen bereiken door de eerste twee orakels achter elkaar uit te voeren:

    [Uncaptioned image]

    Het eerste orakel geeft inderdaad een minteken als x=1x=1, terwijl het tweede orakel een minteken geeft als x=0x=0, dus in beide gevallen krijgen we een minteken:

    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.

    Waar we lineariteit hebben gebruikt om het minteken naar voren te brengen.

Huiswerkopdracht 5.1 (Bepaal de functie vanuit het fase-orakel).

Beschouw het volgende twee-qubitcircuit (zoals gewoonlijk is de onderste draad de eerste qubit):

[Uncaptioned image]

Voor welke functie f:{0,1}2→{0,1}f\colon\{0,1\}^{2}\to\{0,1\} is dit het fase-orakel?

Hint: Gebruik dat H⁢NOT⁢H=ZH\,\mathrm{NOT}\,H=Z, wat volgt uit 4.5.

Hack.

Het circuit komt overeen met de volgende twee-qubitbewerking:

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

Hoe werkt dit op een basistoestand van twee qubits?

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).

Als a=0a=0, wordt het tweede qubit niet geflipt door de controlled-NOT-bewerking, dus:

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,

want H⁢H=IHH=I. Maar als a=1a=1, wordt het tweede qubit wel geflipt door de controlled-NOT-bewerking, dus:

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

(in de een na laatste stap hebben we de hint gebruikt). Dus:

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,

en hieruit kunnen we aflezen dat UU precies het fase-orakel voor de AND\operatorname{AND}-functie implementeert.

Laten we kort samenvatten wat we tot nu toe hebben bereikt: Met behulp van bit-orakels kunnen we een quantumcomputer vragen om een functie f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} te evalueren op precies dezelfde manier als we dat zouden vragen aan een gewone computer die op een inverteerbare manier werkt (vergelijk Vgl. 5.4 en 5.5). Dit is belangrijk, want het betekent dat we geen appels met peren vergelijken als we vragen hoeveel keer we het bit orakel UfU_{f} moeten vragen om iets te weten te komen over ff versus hoeveel keer we ff moeten evalueren op een gewone computer om hetzelfde te weten te komen. En omdat we net hebben laten zien dat het fase-orakel OfO_{f} altijd geïmplementeerd kan worden met behulp van het bit orakel UfU_{f}, maakt het geen verschil als we in plaats daarvan vragen stellen aan het fase-orakel OfO_{f}.