5.1.2 Bit-orakels

Dit idee werkt niet alleen voor de logische $\operatorname{AND}$-functie maar in feite voor elke functie

die $n$ bits als invoer neemt en een enkele bit teruggeeft. Voor zo’n functie $f$ kunnen we een omkeerbare bewerking op $(n+1)$ bits definiëren:

voor alle $x_{1},\dotsc,x_{n},y\in\{0,1\}$. Net als Vgl. 5.3 is deze bewerking zijn eigen inverse, dat wil zeggen dat de bewerking twee keer toepassen gelijk is aan niets doen.

Het is geruststellend dat we elke functie $f:\{0,1\}^{n}\to\{0,1\}$ op een omkeerbare manier kunnen implementeren zoals in Vgl. 5.4. Ten eerste betekent dit dat elke berekening op een klassieke computer op zo’n manier kan worden uitgevoerd dat we de oorspronkelijke invoer terug kunnen krijgen. Ten tweede, als de berekening omkeerbaar is gemaakt, kunnen we deze ook uitvoeren op een quantumcomputer. Dit betekent dat quantumcomputers alles kunnen berekenen wat klassieke computers ook kunnen! Ten derde betekent dit dat we elke functie $f$ kunnen implementeren als een orakel op een quantumcomputer.

Laten we eens kijken hoe dit werkt. De quantumversie van de bewerking in Vgl. 5.4 is als volgt gedefinieerd:

voor alle $x_{1},\dotsc,x_{n},y\in\{0,1\}$. аVgl. 5.5 definieert hoe $U_{f}$ werkt op alle basistoestanden van $n+1$ qubits. Zoals gebruikelijk breiden we deze definitie uit naar een arbitraire toestand van $n+1$ qubits door lineariteit. Omdat $U_{f}$ gewoon de basistoestanden permuteert, kun je nagaan zoals in 4.4 dat dit een geldige quantumbewerking is.

We noemen de quantumbewerking $U_{f}$, zoals gedefinieerd in Vgl. 5.5, het bit-orakel voor $f$ (we zouden de functie in Vgl. 5.4 ook een klassiek bit-orakel kunnen noemen, maar deze naam hebben we niet nodig). De term ’orakel’ betekent dat het toepassen van deze bewerking hetzelfde is als het vragen aan een almachtig orakel om ons de waarde van de functie op een gegeven invoer te vertellen. We weten niet hoe het orakel precies geïmplementeerd is of waar het zijn antwoord vandaan haalt, we zullen gewoon tellen hoeveel vragen we het orakel moeten stellen om een bepaalde eigenschap van de functie $f$ te leren. Veel interessante algoritmische problemen kunnen op deze manier gemodelleerd worden, zoals we in het vervolg van deze quest zullen zien.

Het concept van een orakel lijkt een beetje op het spelletje ’raad mijn getal’. Je vriend (het orakel) bedenkt een getal en jij stelt hem vragen van de vorm “is je getal x”? Je vriend beantwoordt elk van deze vragen met “ja” of “nee”. Met andere woorden, je vriend verbergt een functie die op alle inputs op “nee” uitkomt, behalve op één (het getal dat hij in gedachten heeft). Met elke vraag die je stelt, krijg je meer informatie over welk getal het zou kunnen zijn. Je kunt je afvragen hoeveel vragen je moet stellen om het getal te bepalen. Bovendien, wat als je je vragen kon stellen aan een quantumorakel zoals $U_{f}$ in plaats van aan je vriend? Zou je het antwoord kunnen achterhalen met minder vragen? In de quest van deze week zullen we een aantal interessante voorbeelden zien waarbij dit inderdaad het geval is!

Laten we enkele voorbeelden van bit-orakels bespreken. Stel dat $f$ de AND-functie is. Volgens Vgl. 5.1, kunnen we AND interpreteren als vermenigvuldiging modulo 2, aangezien $AND(x_{1},x_{2})=x_{1}x_{2}$. Het bijbehorende bit-orakel

is niets anders dan de Toffoli-gate uit 4.4. Zelfs voor $n=1$ en de functie $f(x)=x$, die simpelweg zijn invoer teruggeeft, krijgen we een interessant resultaat: voor alle $a,b\in\{0,1\}$ geldt dan

Dit is gewoon de bekende controlled-NOT-gate $CNOT_{1\to 2}$ van Vgl. 3.64 uit Paragraaf 3.2.4! De constructie van het bit-orakel geeft dus verschillende interessante quantumbewerkingen terug die we eerder met de hand gedefinieerd hadden. In de volgende opgave ga je proberen alle andere bit-orakels te implementeren voor functies van één bit.