5.2.2 De Hadamard-transformatie en interferentie

Al is het algoritme van Deutsch erg verbazingwekkend, toch levert het maar een kleine verbetering op ten opzichte van het beste klassieke algoritme, namelijk 1 evaluatie van ff in plaats van 2. Dit kan alsnog handig zijn als het evalueren van ff heel lang duurt, bijvoorbeeld een jaar. Maar als het maar om een milliseconde gaat, dan zouden de meeste mensen het niet erg vinden om twee milliseconden te wachten om het antwoord te krijgen (en er veel minder voor te betalen omdat ze dan geen quantumcomputer hoeven te gebruiken)! Om het nut van quantumcomputers aan te tonen, willen we berekeningen met meer dan een factor 2 versnellen.

We gaan nooit een grotere versnelling bereiken als we alleen kijken naar functies van één bit, omdat die volledig bepaald kunnen worden door twee evaluaties: f⁢(0)f(0) en f⁢(1)f(1). We zullen daarom wat algemener kijken naar functies f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} met nn invoerbits, omdat er veel meer van zulke functies zijn (er zijn er namelijk 22n2^{2^{n}}). Onthoud dat ons doel niet is om een functie te evalueren (dat kunnen we inderdaad doen met een enkele vraag aan het orakel), maar om een interessante eigenschap van de functie te leren die betrekking heeft op de waardes die de functie aanneemt bij verschillende invoerbits. Zijn er eigenschappen van nn-bit-functies die we heel efficiënt kunnen bepalen met slimme quantumalgoritmes?

Om het algoritme van Deutsch te generaliseren, moet je bedenken dat het belangrijkste onderdeel was om een Hadamard-gate HH te introduceren voor en na het fase-orakel. We kunnen iets soortgelijks doen als we een nn-bit-functie hebben. In dit geval is het fase-orakel OfO_{f} een quantumbewerking van nn qubits, dus we kunnen gewoon Hadamard-gates toepassen op alle qubits voor en na het orakel. De quantumbewerking die Hadamards in parallel toepast op elk van de nn qubits wordt de Hadamard-transformatie genoemd. We weten van Paragraaf 3.2.3 dat we deze als volgt kunnen schrijven:

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

Laten we eerst eens kijken wat er gebeurt als we de Hadamard-transformatie toepassen op een basistoestand. Voor |0⁢…⁢0⟩\left|0\dots 0\right\rangle is het resultaat simpelweg de uniforme superpositie over alle basistoestanden:

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

Deze toestand is een superpositie van 2n2^{n} basistoestanden. Er is een compactere manier om dit op te schrijven:

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

De notatie ∑y1,…,yn∈{0,1}\sum_{y_{1},\dots,y_{n}\in\{0,1\}} betekent dat je de som van |y1,…,yn⟩\left|y_{1},\dots,y_{n}\right\rangle berekent voor alle mogelijke combinaties van de bits y1,…,yny_{1},\dots,y_{n}.

De Hadamard-transformatie topassen op een basistoestand leidt altijd tot een superpositie van alle 2n2^{n} basistoestanden. Bovendien zijn alle amplitudes gelijk, op eventuele mintekens na. Het uitzoeken waar die mintekens precies voorkomen is een tikje lastig. Probeer het als opwarmertje eerst voor de gevallen n=1n=1 en n=2n=2.

Oefenopgave 5.4 (Twee Hadamards).

Uit Vgl. 2.34 volgt dat 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}, voor elke x1∈{0,1}x_{1}\in\{0,1\}.

  1. 1.
    ​

    Schrijf de toestand H⁢|x1⟩H\left|x_{1}\right\rangle, voor arbitraire x1∈{0,1}x_{1}\in\{0,1\}, om in de volgende vorm:

    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,

    waarbij ??? een uitdrukking is die bestaat uit x1,y1∈{0,1}x_{1},y_{1}\in\{0,1\}. Bepaal deze uitdrukking.

  2. 2.
    ​

    Schrijf de toestand (H⊗H)⁢|x1,x2⟩(H\otimes H)\left|x_{1},x_{2}\right\rangle, voor willekeurige x1,x2∈{0,1}x_{1},x_{2}\in\{0,1\}, in de vorm

    (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,

    waarbij ??? staat voor een uitdrukking van x1,x2,y1,y2∈{0,1}x_{1},x_{2},y_{1},y_{2}\in\{0,1\}.
    Kan je bepalen wat deze uitdrukking is?

Solution.
  1. 1.
    ​

    Hier staat ??? voor x1⁢y1x_{1}y_{1}.

  2. 2.
    ​

    Voor 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,

    dus ??? staat voor x1⁢y1+x2⁢y2x_{1}y_{1}+x_{2}y_{2}.

Heb je de oplossing gevonden? Goed zo, dan mag je nu verder lezen!

In het algemeen kan je de volgende formule afleiden die het mintekenpatroon beschrijft van de amplitudes die je krijgt als je de Hadamard-transformatie toepast op een arbitraire nn-qubit-basistoestand: Voor elke x1,…,xn∈{0,1}x_{1},\dotsc,x_{n}\in\{0,1\} geldt

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

We kunnen nu het algoritme van Deutsch op een eenvoudige manier generaliseren. Beginnend met de nn-qubit-basistoestand |0⁢…⁢0⟩\left|0\dots 0\right\rangle, passen we eerst de Hadamard-transformatie toe, vervolgens het fase-orakel OfO_{f} voor de functie f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} die we willen onderzoeken, en tenslotte nog een Hadamard-transformatie. Bijvoorbeeld, voor n=3n=3 komt dit overeen met het volgende Quirky-circuit:

[Uncaptioned image]

Voor een algemene nn is de wiskundige formule voor de uiteindelijke nn-qubit-toestand:

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

Kunnen we deze toestand wat meer uitwerken? Net als voorheen kunnen we dit stap voor stap berekenen. Eerst passen we de Hadamard-transformatie toe op de nul-basistoestand. Volgens Vgl. 5.10, krijgen we de uniforme superpositie over alle basistoestanden:

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

Vervolgens passen we het fase-orakel OfO_{f} toe:

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.

Wat levert de laatste Hadamard-transformatie op? Door lineariteit kunnen we Hadamard-transformatie toepassen op elke basisvector, zodat we de volgende uitdrukking krijgen voor de toestand in Vgl. 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)

waarbij we bij de laatste stap de twee sommen omgewisseld hebben. Voor n=1n=1 is dit precies hetzelfde als Vgl. 5.7. Maar in het algemeen ziet deze uitdrukking er nogal omslachtig en moeilijk te interpreteren uit – het lijkt alsof het circuit een superpositie van basistoestanden berekent, waarbij de amplitude een rare som is van plus- en mintekens!

Laten we proberen wat intuïtie te krijgen door te kijken naar de amplitude van |0⁢…⁢0⟩\left|0\dots 0\right\rangle in Vgl. 5.13. Het kwadraat van dit getal is de kans dat, wanneer we de nn qubits meten, alle uitkomsten nul zijn. Aangezien deze amplitude overeenkomt met y1=…=yn=0y_{1}=\ldots=y_{n}=0, wordt deze simpelweg gegeven door

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

Wat betekent dit? Stel dat er NfN_{f} invoerbitstrings zijn waarvoor ff evalueert naar nul en 2n−Nf2^{n}-N_{f} bitstrings waarvoor ff evalueert naar één. Dan geldt het volgende,

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

Er zijn twee interessante uiterste gevallen:1515 15 Voor n=1n=1 is elke functie of constant of gebalanceerd. Voor n>1n>1 is dit niet waar (bijvoorbeeld, de AND-functie is niet constant of gebalanceerd).

  • •
    ​

    Als ff een constante functie is, dan is of Nf=0N_{f}=0 (voor de alles-nul-functie) of Nf=2nN_{f}=2^{n} (voor de alles-één-functie). In beide gevallen is de amplitude ±2n/2n=±1\pm 2^{n}/2^{n}=\pm 1. Omdat de kwadraten van alle amplituden moeten optellen tot  1, concluderen we dat alle andere amplituden in Vgl. 5.13 0 moeten zijn. Met andere woorden, als ff constant is, is de toestand in Vgl. 5.13 gewoon ±|0⁢…⁢0⟩\pm\left|0\dots 0\right\rangle. Als we alle nn qubits van deze toestand meten dan zullen alle uitkomsten nul zijn.

  • •
    ​

    Als ff een gebalanceerde functie is, wat betekent dat er evenveel nullen als enen zijn, dan is Nf=2n/2N_{f}=2^{n}/2 en dus is de amplitude 0. Dit betekent dat als we de toestand in Vgl. 5.13 meten, we nooit kunnen krijgen dat alle uitkomsten gelijk zijn aan nul. Voor een gebalanceerde functie zal dus altijd ten minste één van de meetuitkomsten één zijn.

Merk op hoe deze twee gevallen overeenkomen met heel verschillende interferentiepatronen (zie Paragraaf 2.6.1). In het eerste geval wordt de amplitude van |0⁢…⁢0⟩\left|0\dots 0\right\rangle versterkt tot ±1\pm 1 door een zeer gerichte constructieve interferentie, terwijl tegelijkertijd alle andere amplitudes verdwijnen door een zeer ver verspreide destructieve interferentie. In het tweede geval ervaart |0⁢…⁢0⟩\left|0\dots 0\right\rangle een destructieve interferentie, waardoor op andere plaatsen amplitudes groter dan nul opduiken. De Hadamard-transformatie laat het fundamentele belang van interferentie in quantum computing zien. In de volgende twee secties zullen we gebruik maken van deze interferentie om quantumalgoritmes te ontwerpen voor een groot aantal qubits.