5.2.3 Het Deutsch-Jozsa algoritme

Zijn de bovenstaande observaties ook nog ergens nuttig voor? Jazeker! Stel dat $f\colon\{0,1\}^{n}\to\{0,1\}$ een onbekende functie is die of constant of gebalanceerd is. Dan is er een eenvoudig quantumalgoritme dat kan bepalen welke van deze twee het geval is, door slechts één enkele evaluatie van $f$ te gebruiken (dus één toepassing van $O_{f}$).

Dit algoritme heet het Deutsch-Jozsa algoritme en werkt in vijf eenvoudige stappen:

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 alle qubits. Als alle uitkomsten nul zijn, moet de functie $f$ constant zijn. Anders moet de functie gebalanceerd zijn.

Om te zien hoe dit zich verhoudt tot klassieke algoritmen, moet je bedenken dat elk klassiek algoritme de functie $f$ in het ergste geval minstens $\frac{2^{n}}{2}+1$ keer moet evalueren. Stel inderdaad dat we de functie op de helft van de invoerbitstrings toepassen (d.w.z. op $2^{n}/2$ invoerbits) en we krijgen elke keer hetzelfde antwoord. Dan kunnen we nog steeds niet concluderen dat de functie constant is, omdat het zo zou kunnen zijn dat de functie op de resterende helft van de bitstrings het tegenovergestelde antwoord geeft en dus toch gebalanceerd is. Dit is dus het slechtste geval. In dit scenario hebben we $2^{n}/2$ vragen verspild en nog steeds niets nuttigs geleerd. Om er zeker van te zijn of $f$ constant of gebalanceerd is, moeten we het evalueren op nog een invoer. In totaal komt dit neer op $\frac{2^{n}}{2}+1$ evaluaties van $f$, vergeleken met $1$ evaluatie in het quantumgeval. Merk op dat zelfs voor bescheiden waardes zoals $n=100$ dit verschil zo dramatisch is dat je niet in staat zou zijn om $f$ zo vaak te evalueren in een redelijke hoeveelheid tijd (tegen die tijd zou de zon zonder brandstof raken en zou je naar een ander zonnestelsel moeten verhuizen).

Samengevat: Als $f\colon\{0,1\}^{n}\to\{0,1\}$ een functie is die ofwel constant ofwel gebalanceerd is, dan kan het Deutsch-Jozsa algoritme met slechts één evaluatie van $f$ bepalen welke van de twee het geval is. Dit is exponentieel beter dan een klassiek algoritme, dat in het slechtste geval de functie moet evalueren op $\frac{2^{n}}{2}+1$ invoerbits.