5.2.1 Het algoritme van Deutsch

Het is laat op zondagavond. Alice en Bob zijn net klaar met hun huiswerkopdrachten voor hun vak quantumcomputing en staan op het punt om een 3D-film te gaan kijken. Wanneer ze hun holografische televisie aanzetten, ontdekken ze dat de filmvoorstelling is uitgesteld vanwege onverwachte dramatische nieuwsberichten van het International Transgalactic Station. Er is een verschrikkelijk ongeluk gebeurd en een module met twee bemanningsleden, Hila en Iman, is losgekomen van het moederschip. Het laatste bericht dat we van de module ontvingen was dat Iman gewond is en hevig bloedt – hij heeft dringend bloed nodig. Wat de situatie ingewikkeld maakt, is dat Hila en Iman enigszins in shock zijn en hun eigen bloedgroep vergeten zijn – ze kunnen zich alleen herinneren dat ze allebei bloedgroep A of B hebben. De nieuwspresentator doet een beroep op het publiek om te helpen en een manier te bedenken waarop Hila en Iman kunnen bepalen of ze dezelfde bloedgroep hebben, want als dat het geval is, kan Hila haar bloed aan Iman geven om zijn leven te redden. De medische kit in de module van Hila en Iman bevat namelijk een lymfo-transcoder die een van de twee bloedgroepen kan omzetten in de tegenovergestelde. Dus zelfs als blijkt dat hun bloedgroepen niet bij elkaar passen, kan Hila die van haar met de lymfotranscoder omzetten in de tegenovergestelde bloedgroep.

Bij het horen van dit nieuws laten Alice en Bob hun plan om een film te gaan kijken meteen varen en gaan ze nadenken over wat er gedaan kan worden om Hila en Iman te helpen. Het nieuws gaat verder met wat extra informatie. Gelukkig blijkt dat de module die betrokken was bij het ongeluk een databasechip bevat die de bloedgroep van Hila en Iman opslaat. We kunnen dit modelleren met een functie $f\colon\{0,1\}\to\{0,1\}$, waarbij

Wat bepaald moet worden is of $f(0)=f(1)$ of niet!

De oplossing lijkt simpel: Hila en Iman hoeven alleen maar twee keer de database te bevragen om hun bloedgroepen, $f(0)$ en $f(1)$, uit te lezen en dan de twee waarden te vergelijken om te zien of ze hetzelfde zijn. Helaas heeft het ongeluk de besturingslogica van de databasechip gedeeltelijk doorgebrand en de nieuwslezer meldt dat de databasechip na de eerste zoekopdracht waarschijnlijk volledig zal doorbranden.

Onze twee hoofdrolspelers zijn vastgelopen. Het is duidelijk dat elk klassiek algoritme $f$ twee keer moet evalueren om te bepalen of $f(0)=f(1)$. Als je alleen de waarde van $f(0)$ kent, hangt het nog steeds af van de waarde van $f(1)$ of $f(0)=f(1)$ en, tenzij je ook $f(1)$ berekent, zou je niet kunnen zeggen of $f(0)=f(1)$. Op dezelfde manier, als je alleen $f(1)$ kent, kun je het niet vergelijken met $f(0)$ tenzij je ook weet wat de waarde van $f(0)$ is. Welke strategie je ook gebruikt, je moet zowel $f(0)$ als $f(1)$ kennen om te bepalen of $f(0)=f(1)$. Is hier echt geen ontkomen aan?

Na het doorbladeren van wat handleidingen ontdekt Bob dat de databasechip in quantummode kan worden gezet. Wanneer dit is ingeschakeld, evalueert de databasechip de functie niet meer op de klassieke manier, maar maakt in plaats daarvan gebruik van het fase-orakel $O_{f}$. Zou dit op de een of andere manier gebruikt kunnen worden om het probleem op te lossen? Alice denkt er even over na en realiseert zich plotseling dat dit precies is waar het algoritme van Deutsch voor bedoeld is! Alice en Bob nemen snel wat berekeningen door om te bevestigen dat het werkt en gaan zitten om een intergalactische e-mail te schrijven met instructies aan Hila en Iman over hoe ze het probleem kunnen oplossen. Hun instructies zijn als volgt:

1. 1.
   ​

   Maak een qubit aan in de toestand $\left|+\right\rangle=(\left|0\right\rangle+\left|1\right\rangle)/\sqrt{2}$.

2. 2.
   ​

   Gebruik de databasechip in quantummode om de bewerking $O_{f}$ toe te passen.

3. 3.
   ​

   Pas de Hadamard-gate $H$ toe op de uitvoerqubit en meet deze.

4. 4.
   ​

   Als de uitkomst $0$ is dan hebben Hila en Iman dezelfde bloedgroep en anders hebben ze verschillende bloedgroepen.

Merk op dat Hila en Iman in deze procedure de databasechip maar één keer hoeven te bevragen om te bepalen of ze dezelfde bloedgroep hebben. Hier is een implementatie van het algoritme in Quirky:

De afbeelding laat zien dat de uitkomst $1$ is, dus Hila en Iman hebben verschillende bloedgroepen.

Maar waarom werkt het algoritme van Deutsch? Laten we het stap voor stap analyseren. De eerste Hadamard-gate maakt de toestand $\left|+\right\rangle=H\left|0\right\rangle$. Vervolgens passen we het fase-orakel $O_{f}$ toe, wat leidt tot de toestand

Na het toepassen van de tweede Hadamard krijgen we de volgende toestand:

Merk op dat de twee tekens $(-1)^{f(0)}$ en $(-1)^{f(1)}$ worden opgeteld in de eerste amplitude, maar afgetrokken in de tweede amplitude. Afhankelijk van de waardes van $f(0)$ en $f(1)$ zullen we voor elke amplitude of constructieve of destructieve interferentie waarnemen (zie Paragraaf 2.6.1). In feite wordt welke van de twee amplitudes overblijft alleen bepaald door of $f(0)$ en $f(1)$ gelijk zijn of niet:

Het is een goede oefening om dit expliciet na te gaan:

аVgl. 5.8 laat zien dat de eindmeting uitkomst 0 oplevert als en alleen als $f(0)=f(1)$. Het algoritme van Deutsch bepaalt dus correct of $f(0)=f(1)$. Belangrijk is dat het de functie $f:\{0,1\}\to\{0,1\}$ slechts eenmaal uitvoert door het fase-orakel te gebruiken. Daarentegen hebben we hierboven besproken dat elk klassiek algoritme noodzakelijkerwijs beide functiewaarden $f(0)$ en $f(1)$ afzonderlijk moet evalueren.

Een andere manier om het algoritme van Deutsch te interpreteren is dat het de som van de twee bits $f(0)$ en $f(1)$ modulo twee berekent. Dit komt omdat $f(0)\oplus f(1)=0$ als en slechts als $f(0)=f(1)$. Uit Vgl. 3.21 blijkt namelijk dat optellen modulo twee als volgt werkt:

Dit is ook de reden waarom de som modulo twee bekend staat als de XOR (afkorting voor ‘exclusive OR’) van de twee bits, omdat het één is als precies één van de twee bits is.