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\colon\{0,1\}^{n}\to\{0,1\}$ en de belofte dat $f$ 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 $f$ 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:

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

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

• •
  ​

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

• •
  ​

  $f(x_{1})=x_{1}$, wat overeenkomt met $a_{1}=1$.

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

• •
  ​

  $f(x_{1},x_{2})=0$, als $[a_{1},a_{2}]=[0,0]$,

• •
  ​

  $f(x_{1},x_{2})=x_{2}$, als $[a_{1},a_{2}]=[0,1]$,

• •
  ​

  $f(x_{1},x_{2})=x_{1}$, als $[a_{1},a_{2}]=[1,0]$, en $f(x_{1},x_{2})=x_{1}$, wenn $[a_{1},a_{2}]=[1,0]$, und

• •
  ​

  $f(x_{1},x_{2})=x_{1}\oplus x_{2}$, als $[a_{1},a_{2}]=[1,1]$. $f(x_{1},x_{2})=x_{1}\oplus x_{2}$, wenn $[a_{1},a_{2}]=[1,1]$.

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

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

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

kunnen we concluderen dat $n$ evaluaties van de functie $f$ 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 $a_{1},\dots,a_{n}$ volledig arbitrair zijn en er $n$ van zijn, moet je de functie minstens $n$ 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:

In de tweede stap hebben we gebruikt dat $(-1)^{a}$ alleen afhangt van $a$ modulo twee (dus of $a$ 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.

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

1. 1.
   ​

   Start met $\left|0\dots 0\right\rangle$.

2. 2.
   ​

   Pas de Hadamard-transformatie $H\otimes\dotsb\otimes H$ toe.

3. 3.
   ​

   Pas het fase-orakel $O_{f}$ dat hoort bij de functie $f$ toe.

4. 4.
   ​

   Pas weer de Hadamard-transformatie $H\otimes\dotsb\otimes H$ toe.

5. 5.
   ​

   Meet als laatste alle qubits. De meetuitkomst is exact de bitstring $[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.