5.2.4 Het Bernstein-Vazirani algoritme

Hierboven hebben we besproken hoe we de Hadamard-transformatie kunnen gebruiken om een interessant probleem op te lossen. Gegeven een functie f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} en de belofte dat ff constant of gebalanceerd is, was het Deutsch-Jozsa algoritme in staat om te bepalen welke van deze twee mogelijkheden het geval was.

In deze paragraaf bespreken we een ander interessant probleem dat we met een variant van dezelfde procedure kunnen oplossen. Net als voorheen beginnen we met een belofte over de onbekende functie ff waarmee we te maken hebben. Deze keer zullen we, in plaats van aan te nemen dat deze constant of gebalanceerd is, aannemen dat deze functie de volgende speciale vorm heeft:

f⁢(x1,…,xn)=x1⁢a1⊕…⊕xn⁢an,\displaystyle f(x_{1},\dots,x_{n})=x_{1}a_{1}\oplus\ldots\oplus x_{n}a_{n}, (5.14)

waarbij a1,…,an∈{0,1}a_{1},\dots,a_{n}\in\{0,1\} een vaste bitstring is die de functie definieert.

Als n=1n=1, zijn er maar twee van zulke functies:

  • •
    ​

    f⁢(x1)=0f(x_{1})=0, in het geval dat a1=0a_{1}=0, en

  • •
    ​

    f⁢(x1)=x1f(x_{1})=x_{1}, wat overeenkomt met a1=1a_{1}=1.

Als n=2n=2 zijn er al vier van zulke functies:

  • •
    ​

    f⁢(x1,x2)=0f(x_{1},x_{2})=0, als [a1,a2]=[0,0][a_{1},a_{2}]=[0,0],

  • •
    ​

    f⁢(x1,x2)=x2f(x_{1},x_{2})=x_{2}, als [a1,a2]=[0,1][a_{1},a_{2}]=[0,1],

  • •
    ​

    f⁢(x1,x2)=x1f(x_{1},x_{2})=x_{1}, als [a1,a2]=[1,0][a_{1},a_{2}]=[1,0], en

  • •
    ​

    f⁢(x1,x2)=x1⊕x2f(x_{1},x_{2})=x_{1}\oplus x_{2}, als [a1,a2]=[1,1][a_{1},a_{2}]=[1,1].

Merk op dat elk van deze functies de som modulo twee van een deelverzameling van de variabelen xix_{i} berekent. Welke deelverzameling? Als ai=1a_{i}=1, is de bijbehorende variabele xix_{i} onderdeel van de deelverzameling.

In het algemeen zijn er 2n2^{n} keuzes van de bitring a1,…,ana_{1},\dotsc,a_{n} en dus 2n2^{n} functies ff met de speciale vorm (5.14). In feite kunnen we Vgl. 5.14 zien als een manier om de bitstring

[a1,…,an][a_{1},\dots,a_{n}]

te verbergen in de functie ff. Hoeveel evaluaties van de functie hebben we nodig om deze string te achterhalen? Aangezien

a1\displaystyle a_{1} =f⁢(1,0,…⁢,0,0),\displaystyle=f(1,0,\dots,0,0),
a2\displaystyle a_{2} =f⁢(0,1,…⁢,0,0),\displaystyle=f(0,1,\dots,0,0),
⋮\displaystyle\qquad\qquad\vdots
an\displaystyle a_{n} =f⁢(0,0,…⁢,0,1),\displaystyle=f(0,0,\dots,0,1),

kunnen we concluderen dat nn evaluaties van de functie ff zeker genoeg zijn. Voor elk klassiek algoritme is dit ook optimaal: elke keer dat je de functie evalueert achterhaal je maar één bit. Aangezien de onbekende bits a1,…,ana_{1},\dots,a_{n} volledig arbitrair zijn en er nn van zijn, moet je de functie minstens nn keer evalueren om ze allemaal te achterhalen.

We zullen nu zien dat we dit met een quantumalgoritme veel beter kunnen doen. Laten we om te beginnen bepalen hoe het fase-orakel voor de functie in Vgl. 5.14 werkt op de basistoestanden:

Of⁢|x1,…,xn⟩\displaystyle O_{f}\left|x_{1},\dots,x_{n}\right\rangle =(−1)x1⁢a1⊕…⊕xn⁢an⁢|x1,…,xn⟩\displaystyle=(-1)^{x_{1}a_{1}\oplus\ldots\oplus x_{n}a_{n}}\left|x_{1},\dots,% x_{n}\right\rangle
=(−1)x1⁢a1+…+xn⁢an⁢|x1,…,xn⟩.\displaystyle=(-1)^{x_{1}a_{1}+\ldots+x_{n}a_{n}}\left|x_{1},\dots,x_{n}\right\rangle. (5.15)

In de tweede stap hebben we gebruikt dat (−1)a(-1)^{a} alleen afhangt van aa modulo twee (dus of aa even of oneven is), dus het maakt niet uit of we optelling modulo 2 (‘⊕\oplus’) of de gewone optelling gebruiken. Hoe kan dit fase-orakel gerealiseerd worden? Voor ons maakt dat niet zoveel uit, omdat ons algoritme het orakel als een black box zal behandelen. Maar omdat het een leuke oefening is, kun je proberen dit uit te zoeken in de volgende opgave.

Oefenopgave 5.5 (Het fase-orakel realiseren (optioneel)).

In deze opgave ga je het fase-orakel implementeren voor functies van de vorm (5.14).

  1. 1.
    ​

    Als n=2n=2 zijn er vier van zulke functies, zoals we hierboven al besproken hebben. Kan je voor elk van deze functies een Quirky-circuit vinden dat het fase-orakel implementeert?

  2. 2.
    ​

    Leg in woorden of met een plaatje uit hoe je het fase-orakel in het algemene geval kunt implementeren (d.w.z. wanneer n≥1n\geq 1 en de bits a1,…,an∈{0,1}a_{1},\dots,a_{n}\in\{0,1\} arbitrair zijn).

Solution.
  1. 1.
    ​

    Hier zijn de vier functies en hun fase-orakels:

    • •
      ​

      Voor [a1,a2]=[0,0][a_{1},a_{2}]=[0,0], Of⁢|x1,x2⟩=|x1,x2⟩O_{f}\left|x_{1},x_{2}\right\rangle=\left|x_{1},x_{2}\right\rangle, dus het fase-orakel doet niks.

    • •
      ​

      Voor [a1,a2]=[0,1][a_{1},a_{2}]=[0,1], Of⁢|x1,x2⟩=(−1)x2⁢|x1,x2⟩O_{f}\left|x_{1},x_{2}\right\rangle=(-1)^{x_{2}}\left|x_{1},x_{2}\right\rangle, wat hetzelfde is als I⊗ZI\otimes Z.

    • •
      ​

      Voor [a1,a2]=[1,0][a_{1},a_{2}]=[1,0], Of⁢|x1,x2⟩=(−1)x1⁢|x1,x2⟩O_{f}\left|x_{1},x_{2}\right\rangle=(-1)^{x_{1}}\left|x_{1},x_{2}\right\rangle, wat hetzelfde is als Z⊗IZ\otimes I.

    • •
      ​

      Voor [a1,a2]=[1,1][a_{1},a_{2}]=[1,1], Of⁢|x1,x2⟩=(−1)x1+x2⁢|x1,x2⟩=(−1)x1⁢(−1)x2⁢|x1,x2⟩O_{f}\left|x_{1},x_{2}\right\rangle=(-1)^{x_{1}+x_{2}}\left|x_{1},x_{2}\right% \rangle=(-1)^{x_{1}}(-1)^{x_{2}}\left|x_{1},x_{2}\right\rangle, wat hetzelfde is als Z⊗ZZ\otimes Z.

    Het is dus duidelijk hoe deze vier bewerkingen eruit zien in Quirky.

  2. 2.
    ​

    Het algemene patroon is vrij duidelijk. Voor een arbitraire functie in de vorm van (5.14) geldt dus:

    Of⁢|x1,…,xn⟩=(−1)x1⁢a1+…+xn⁢an⁢|x1,…,xn⟩=(Za1⊗⋯⊗Zan)⁢|x1,…,xn⟩,\displaystyle O_{f}\left|x_{1},\dots,x_{n}\right\rangle=(-1)^{x_{1}a_{1}+% \ldots+x_{n}a_{n}}\left|x_{1},\dots,x_{n}\right\rangle=(Z^{a_{1}}\otimes\dotsb% \otimes Z^{a_{n}})\left|x_{1},\dots,x_{n}\right\rangle,

    waar we stellen dat Z1=ZZ^{1}=Z en Z0=IZ^{0}=I. In andere woorden, we passen een Z-gate toe op het jj-de qubit als en alleen als aj=1a_{j}=1.

We introduceren nu het Bernstein-Vazirani algoritme, dat de verborgen bitstring [a1,…,an][a_{1},\dots,a_{n}] ontrafelt met behulp van een enkele evaluatie van het fase-orakel van  ff:

  1. 1.
    ​

    Start met |0⁢…⁢0⟩\left|0\dots 0\right\rangle.

  2. 2.
    ​

    Pas de Hadamard-transformatie H⊗⋯⊗HH\otimes\dotsb\otimes H toe.

  3. 3.
    ​

    Pas het fase-orakel OfO_{f} dat hoort bij de functie ff toe.

  4. 4.
    ​

    Pas weer de Hadamard-transformatie H⊗⋯⊗HH\otimes\dotsb\otimes H toe.

  5. 5.
    ​

    Meet als laatste alle qubits. De meetuitkomst is exact de bitstring [a1,…,an][a_{1},\dots,a_{n}].

Dit algoritme is identiek aan het Deutsch-Jozsa algoritme van Paragraaf 5.2.3 op de laatste stap na, die in dit geval nog simpeler is.

Huiswerkopdracht 5.3 (Bernstein-Vazirani uitvoeren).

Het oranje vakje Oracle in Quirky implementeert het fase-orakel voor een functie van de vorm (5.14) met n=4n=4. Implementeer het Bernstein-Vazirani algoritme in Quirky en gebruik dit om de verborgen bitstring [a1,a2,a3,a4][a_{1},a_{2},a_{3},a_{4}] te bepalen.

Hack.

Quirky geeft het volgende resultaat:

[Uncaptioned image]

Dus de verborgen bitstring is [a1,a2,a3,a4]=[1,1,0,1][a_{1},a_{2},a_{3},a_{4}]=[1,1,0,1] (houd je muis over het groene ’100%’ vakje om te zien welke uitkomst erbij hoort).

Waarom werkt dit algoritme? Nu is het jouw beurt om de analyse te doen!

Oefenopgave 5.6 (Bernstein-Vazirani nagaan).

De functie f⁢(x1,x2)=x2f(x_{1},x_{2})=x_{2} komt overeen met de bitstring [a1,a2]=[0,1][a_{1},a_{2}]=[0,1], zoals we al eerder hebben gezien.

Laat zien dat wanneer je het Bernstein-Vazirani algoritme voor deze functie uitvoert, de meetuitkomst inderdaad altijd [a1,a2]=[0,1][a_{1},a_{2}]=[0,1] is. Controleer dit niet alleen met Quirky, maar schrijf zelf de toestand na elke stap op.

Solution. In stap 1 beginnen we met:
|00⟩\displaystyle\left|00\right\rangle
In stap 2 passen we H⊗HH\otimes H toe en krijgen we:
12⁢(|0⟩+|1⟩)⊗12⁢(|0⟩+|1⟩)\displaystyle\frac{1}{\sqrt{2}}\left(\left|0\right\rangle+\left|1\right\rangle% \right)\otimes\frac{1}{\sqrt{2}}\left(\left|0\right\rangle+\left|1\right% \rangle\right)
=\displaystyle= 12⁢(|00⟩+|01⟩+|10⟩+|11⟩)\displaystyle\frac{1}{2}\left(\left|00\right\rangle+\left|01\right\rangle+% \left|10\right\rangle+\left|11\right\rangle\right)
In stap 3 passen we het fase-orakel OfO_{f} van f⁢(x1,x2)=x2f(x_{1},x_{2})=x_{2} toe:
12⁢(|00⟩−|01⟩+|10⟩−|11⟩)\displaystyle\frac{1}{2}\left(\left|00\right\rangle-\left|01\right\rangle+% \left|10\right\rangle-\left|11\right\rangle\right)
In stap 4 passen we weer H⊗HH\otimes H toe, met als resultaat:
12⁢((H⊗H)⁢|00⟩−(H⊗H)⁢|01⟩+(H⊗H)⁢|10⟩−(H⊗H)⁢|11⟩)\displaystyle\frac{1}{2}\Bigl{(}(H\otimes H)\left|00\right\rangle-(H\otimes H)% \left|01\right\rangle+(H\otimes H)\left|10\right\rangle-(H\otimes H)\left|11% \right\rangle\Bigr{)}
=\displaystyle= 14((|00⟩+|01⟩+|10⟩+|11⟩)−(|00⟩−|01⟩+|10⟩−|11⟩)\displaystyle\frac{1}{4}\Bigl{(}\left(\left|00\right\rangle+\left|01\right% \rangle+\left|10\right\rangle+\left|11\right\rangle\right)-\left(\left|00% \right\rangle-\left|01\right\rangle+\left|10\right\rangle-\left|11\right% \rangle\right)
+(|00⟩+|01⟩−|10⟩−|11⟩)−(|00⟩−|01⟩−|10⟩+|11⟩))\displaystyle+\left(\left|00\right\rangle+\left|01\right\rangle-\left|10\right% \rangle-\left|11\right\rangle\right)-\left(\left|00\right\rangle-\left|01% \right\rangle-\left|10\right\rangle+\left|11\right\rangle\right)\Bigr{)}
=\displaystyle= |01⟩.\displaystyle\left|01\right\rangle.
In stap 5 meten we beide qubits en krijgen we altijd het meetresultaat [0,1][0,1].

In de volgende huiswerkopdracht kan je het algemene geval analyseren:

Huiswerkopdracht 5.4 (Bernstein-Vazirani nagaan (uitdagend)).

Laat zien dat als je het Bernstein-Vazirani algoritme uitvoert voor een functie van de vorm  (5.14), de meetuitkomst [a1,…,an][a_{1},\dots,a_{n}] is met 100% waarschijnlijkheid.

Hint: Aangezien de eerste vier stappen van het algoritme identiek zijn aan het Deutsch-Jozsa algoritme, wordt de toestand vlak voor de meting gegeven door Vgl. 5.13.

Hack.

Als we de hint volgen, zien we dat we net voor de meting de volgende toestand hebben:

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

De functie f⁢(x1,…,xn)f(x_{1},\dots,x_{n}) in dit probleem heeft de vorm f⁢(x1,…,xn)=x1⁢a1⊕⋯⊕xn⁢anf(x_{1},\dots,x_{n})=x_{1}a_{1}\oplus\cdots\oplus x_{n}a_{n} (zoals in Vgl. 5.14 is gedefinieerd), dus de toestand is gegeven als

∑y1,…,yn∈{0,1}12n⁢(∑x1,…,xn∈{0,1}(−1)x1⁢y1+…+xn⁢yn⁢(−1)x1⁢a1+…+xn⁢an)⁢|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)^{x_{1}a_{1}+% \ldots+x_{n}a_{n}}\right)\left|y_{1},\dots,y_{n}\right\rangle.

Om de waarschijnlijkheid van de meetuitkomst [a1,…,an][a_{1},\dots,a_{n}] te begrijpen, moeten we de amplitude van de toestand |a1,…,an⟩\left|a_{1},\dots,a_{n}\right\rangle in de bovenstaande uitdrukking analyseren. Aangezien dit overeenkomt met y1=a1y_{1}=a_{1}, …, yn=any_{n}=a_{n}, is de amplitude gegeven door

12n⁢(∑x1,…,xn∈{0,1}(−1)x1⁢y1+…+xn⁢yn⁢(−1)x1⁢a1+…+xn⁢an)\displaystyle\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)^{x_{1}a_{1}+\ldots+x_{n}a_{n}}\right)
=\displaystyle= 12n⁢(∑x1,…,xn∈{0,1}(−1)x1⁢a1+…+xn⁢an⁢(−1)x1⁢a1+…+xn⁢an)\displaystyle\frac{1}{2^{n}}\left(\sum_{x_{1},\dots,x_{n}\in\{0,1\}}(-1)^{x_{1% }a_{1}+\ldots+x_{n}a_{n}}(-1)^{x_{1}a_{1}+\ldots+x_{n}a_{n}}\right)
=\displaystyle= 12n⁢(∑x1,…,xn∈{0,1}1)=2n2n=1.\displaystyle\frac{1}{2^{n}}\left(\sum_{x_{1},\dots,x_{n}\in\{0,1\}}1\right)=% \frac{2^{n}}{2^{n}}=1.

In de eerste stap hebben we gebruikt dat y1=a1y_{1}=a_{1}, …, yn=any_{n}=a_{n}. In de tweede stap hebben we gebruikt dat (−1)⁢(−1)=(+1)⁢(+1)=1(-1)(-1)=(+1)(+1)=1.

De amplitude van |a1,…,an⟩\left|a_{1},\dots,a_{n}\right\rangle is 1, dus we kunnen concluderen dat we de uitkomst [a1,…,an][a_{1},\dots,a_{n}] met een 100% kans krijgen.