5.1.1 Omkeerbare berekeningen

Voordat we ons laten meeslepen in het vinden van spannende nieuwe quantumalgoritmes, moeten we er eerst zeker van zijn dat we op een quantumcomputer nog steeds alles kunnen berekenen wat we op een gewone computer ook kunnen. Met andere woorden, laten we er eerst voor zorgen dat quantumcomputers eigenlijk niet minder krachtig zijn dan gewone (klassieke) computers! Dit is niet helemaal voor de hand liggend, omdat de manier waarop quantumcomputers werken totaal anders is. Zo zijn alle bewerkingen op een quantumcomputer omkeerbaar of inverteerbaar, zoals we al eerder hebben gezien in Paragraaf 2.4.2 en Paragraaf 4.1.3, maar dit is normaal gesproken niet het geval op een gewone computer. Wie heeft er nog nooit per ongeluk een bestand gewist of vergeten de wijzigingen in hun document op te slaan en zo al hun werk verloren? Als alle bewerkingen omkeerbaar zouden zijn, zou je je nooit zorgen hoeven te maken over zulke onbenullige zaken.

Dit roept de volgende vraag op: hoe kunnen we er zeker van zijn dat quantumcomputers alles kunnen berekenen wat gewone computers kunnen berekenen? Een manier om dit aan te pakken is door te laten zien dat omkeerbaarheid in feite geen beperking is voor wat een gewone computer kan berekenen, en dus ook geen beperking voor quantumcomputers. Met andere woorden, we zullen laten zien dat elke berekening omkeerbaar gemaakt kan worden en dus uitgevoerd kan worden op een quantumcomputer.

Om een idee te krijgen van hoe dit gedaan kan worden, nemen we het eenvoudige voorbeeld van het berekenen van de logische AND-functie op twee bits. Als beide bits 1 zijn, geeft AND een waarde van 1, anders een waarde van 0. We kunnen dus de AND-functie weergeven met de volgende waarheidstabel:

Als we de notatie uit Paragraaf 3.1 gebruiken, kunnen we dit wiskundig opschrijven als de volgende bewerking op twee bits:

Het is duidelijk dat deze bewerking niet omkeerbaar is, omdat ze niet hetzelfde aantal uitvoerbits als invoerbits heeft. Als je alleen weet dat de AND van twee bits $0$ is, kun je de precieze toestand van de twee bits niet afleiden – zoals de waarheidstabel laat zien, zijn er drie mogelijke opties.

Hoe kunnen we dit probleem oplossen? Laten we het eerste bit behouden en een tweede uitgangsbit toevoegen waarin we het antwoord opslaan:

Dit is beter, omdat we nu twee bits op twee bits afbeelden. Maar is het omkeerbaar? Dat wil zeggen, als we de uitvoer krijgen, kunnen we dan altijd de invoer terughalen? Nou, we kunnen zeker het eerste bit van de invoer, $x_{1}$, terugrekenen, omdat we deze ook in de uitvoer hebben zitten. Hoe zit het dan met $x_{2}$? Als $x_{1}=0$ dan is volgens Vgl. 5.1 de uitvoer $[00]$ – ongeacht de waarde van $x_{2}$. Dit betekent dat we ook hier de invoer niet altijd kunnen herleiden en dat deze aanpak dus helaas ook niet werkt.

Dit begint er hopeloos uit te zien. Is het überhaupt mogelijk om de AND-functie op omkeerbare manier uit te voeren? Als je vastloopt, moet je out of the box denken! Wie heeft in dit geval gezegd dat we ons moeten beperken tot twee bits? Als we beide invoerbits behouden en een derde bit introduceren om het antwoord op te slaan, zou dit de bewerking zeker omkeerbaar moeten maken:

Nu is er geen probleem om de bewerking te inverteren – gegeven een willekeurige uitvoerbitstring, kunnen we gewoon vergeten wat het laatste bit is en het vervangen door $[0]$ om de invoerbitstring terug te krijgen. Als de uitvoer bijvoorbeeld $[111]$ is, dan moet de invoer $[110]$ zijn geweest.

Zijn we nu dus klaar? Niet zo snel! Merk op dat Vgl. 5.2 alleen de bewerking gedeeltelijk bepaalt – als de invoer $[111]$ is, of een andere bitstring die eindigt op $1$, dan zegt Vgl. 5.2 niet hoe de bewerking op deze invoer moet werken. Aangezien de vier invoerstrings die eindigen op $0$ worden afgebeeld op vier verschillende uitvoerstrings, is het duidelijk dat we Vgl. 5.2 op een arbitraire manier kunnen uitbreiden naar een omkeerbare operatie van drie bits. Maar is er een systematische manier om dit te doen?

Merk hiervoor op dat Vgl. 5.2 het laatste bit omdraait van $[0]$ naar $[1]$ als $\operatorname{AND}(x_{1},x_{2})=1$. We kunnen dus ook, als het laatste bit toevallig $[1]$ is, onze bewerking zo definiëren dat het de bit terug flipt naar $[0]$ als $\operatorname{AND}(x_{1},x_{2})=1$. Met andere woorden, we kunnen Vgl. 5.2 als volgt uitbreiden naar alle mogelijke invoerstrings:

voor alle $x_{1},x_{2},y\in\{0,1\}$, waarbij ‘$\oplus$’ staat voor optelling modulo 2.

De bewerking in Vgl. 5.3 is nu gedefinieerd op alle mogelijke invoerbits. Maar is het nu eindelijk omkeerbaar? Ja, dat is het! Sterker nog, deze bewerking is zijn eigen inverse! Dat wil zeggen, als we de bewerking twee keer uitvoeren, krijgen we de oorspronkelijke invoer terug:

In de derde stap hebben we gebruikt dat $a\oplus a=0$ voor elke $a\in\{0,1\}$, zie Vgl. 3.21. We hebben dus een succesvolle manier gevonden om de AND-functie op een omkeerbare manier te berekenen.