5.3 Op zoek met Grover

Na een veilige terugkeer op aarde zijn Hila en Iman goede vrienden geworden met Alice en Bob. Ze besluiten met z’n vieren nieuwjaarsavond samen door te brengen. Deze dag valt toevallig ook samen met de trekking van de jaarlijkse quantumloterij! Ze weten dat maar één van de vier de hoofdprijs kan winnen, maar wie zal dat zijn? Als we onze vier hoofdpersonen labelen met bitstrings, bijvoorbeeld als

dan kunnen we de loterij beschrijven met een functie $f\colon\{0,1\}^{2}\to\{0,1\}$ die de waarde 1 geeft voor de bitstring die overeenkomt met de winnaar. Als bijvoorbeeld $f(1,0)=1$, dan is Hila de winnaar van de loterij van dit jaar.

Hoe kunnen onze vrienden de winnaar bepalen? Met een klassiek algoritme moeten ze de functie tot drie keer evalueren om de winnaar te bepalen. Stel bijvoorbeeld dat ze te weten komen dat $f(0,1)=0$ en $f(1,0)=0$ – dan weten ze nog steeds niet of Alice of Iman de winnaar is! Door ouderwetse redenen die al lang vergeten zijn, staat in de regels van de loterij dat de functie maar één keer geëvalueerd mag worden. Maar de loterij vindth het ook prima als we het fase-orakel $O_{f}$ uitvoeren – het is tenslotte een quantumloterij!

Alice en haar vrienden komen bij elkaar en beginnen na te denken. Na een tijdje wordt Bob ongeduldig en hij stelt voor: "Laten we gewoon de eerste stappen van Deutsch-Jozsa en Bernstein-Vazirani volgen – dezelfde truc zal vast nog wel een keer werken…"missing De anderen weten niet echt een beter alternatief, dus ze gaan aan de slag en bereiden de volgende toestand voor:

Vervolgens geven ze de toestand door aan de quantumloterij, die het fase-orakel $O_{f}$ toepast en de toestand teruggeeft. Laat $a$ en $b$ de twee bits zijn die de winnaar aanduiden, d.w.z. $f(a,b)=1$ en alle andere functiewaarden zijn nul. De loterij stuurt dan de volgende twee-qubit-toestand terug:

waarbij de $-2\left|a,b\right\rangle$ in de eerste regel een van de plustekens vervangt door een minteken. Na het toepassen van een Hadamard-transformatie krijgen ze de volgende toestand:

Nu zijn onze vrienden in de war en weten ze niet goed wat ze moeten doen. Hila heeft een idee: "Ik vind het minteken voor de $\left|00\right\rangle$ maar niks. Waarom passen we geen quantumbewerking toe die er als volgt uitziet?"missing

Iman voegt toe: "Ik denk dat ik weet hoe ik dit kan maken met behulp van een controlled-Z-bewerking en een handvol NOTs…” In een mum van tijd, komen onze vrienden tot de volgende toestand:

Na een klein poosje realiseert Alice zich: "Deze twee-qubit-toestand kan worden geschreven als een tensorproduct!"missing

Bob zegt enthousiast: "Aha! We hoeven alleen nog maar een Hadamard-transformatie toe te passen en beide qubits te meten. Kan je er ook achter komen wie de winnaar van de quantumloterij van dit jaar wordt?

Het quantumalgoritme dat onze vrienden net ontdekt hebben is een speciaal geval van het algoritme van Grover. Grovers algoritme lost het volgende probleem op: Gegeven een orakel voor een functie $f\colon\{0,1\}^{n}\to\{0,1\}$, vindt het de $x_{1},\dots,x_{n}\in\{0,1\}$ waarvoor geldt dat $f(x_{1},\dots,x_{n})=1$. We kunnen dit probleem zien als het vinden van een loterijwinnaar tussen $2^{n}$ deelnemers of, wat eenvoudiger gezegd, het vinden van een item dat voldoet aan een bepaalde interessante eigenschap in een ongestructureerde database (waarmee we bedoelen dat de items in de database niet gesorteerd of vergelijkbaar zijn). Met hetzelfde argument dat we eerder gaven, zal elk klassiek algoritme in het slechtste geval naar alle $2^{n}$ items moeten kijken voordat het klaar is (gemiddeld zal je nog steeds naar ongeveer de helft van de items moeten kijken). Grovers algoritme daarentegen hoeft het orakel maar een paar keer te gebruiken en dat aantal is evenredig met $\sqrt{2^{n}}$ - een hoeveelheid die veel langzamener groeit dan de ‘klassieke’ $2^{n}$. Het algoritme van Grover is een veelzijdig hulpmiddel dat een kwadratische versnelling geeft voor veel rekenproblemen.