5.1 Spreken met orakels

In deze quest zullen we verschillende quantumalgoritmes bekijken en zien hoe ze zich verhouden tot klassieke algoritmes die hetzelfde probleem oplossen. Omdat het over het algemeen erg moeilijk is om te begrijpen hoeveel elementaire bewerkingen nodig zijn om een bepaalde berekening uit te voeren, zullen we in deze quest kijken naar een simpelere maat voor algoritmecomplexiteit (dit is ook wat computerwetenschappers doen als ze hun eigen werk wat simpeler willen maken).

Wanneer een computer een programma uitvoert, moet de computer verschillende soorten bewerkingen uitvoeren. De meest langzame bewerkingen zijn die waarbij toegang tot data nodig is. Denk bijvoorbeeld aan het lezen van gegevens uit het geheugen, de harde schijf of - in het ergste geval - een andere computer die bereikbaar is via het internet. Als de relevante data eenmaal gelezen is, kan de verwerking hiervan relatief snel gaan. Daarom kunnen we een ruw idee krijgen van hoe lang een bepaald algoritme zal duren door alleen de instructies mee te tellen die toegang nodig hebben tot je gegevens.

Je kent dit misschien wel bij het openen van een ingewikkelde webpagina of een groot document. Het kan een tijdje duren voordat deze geladen is, maar als het eenmaal geladen is, werkt het scrollen door het document en het invoegen van een nieuwe regel meestal vrij snel.

Een andere manier om hierover na te denken, die we in deze quest zullen gebruiken, is dat de informatie die je probeert te openen in feite wordt verkregen door een ander algoritme of een subroutine binnen je algoritme. Bovendien is deze subroutine vaak erg traag. Deze subroutine leest de informatie bijvoorbeeld van de harde schijf of haalt het op via het internet. Of misschien is het antwoord niet eens direct beschikbaar en moet het zelf geproduceerd worden door een ingewikkelde berekening uit te voeren. Hoe dan ook, deze subroutine doet er altijd erg lang over om het antwoord te geven, dus je wilt hem zo min mogelijk aanroepen. We noemen zo’n subroutine een orakel, omdat het erg slim is en alle antwoorden weet, maar ook een beetje traag is en dus een tijdje moet nadenken om het antwoord te geven.

Formeler gezegd is een klassiek orakel een functie $f\colon\{0,1\}^{n}\to\{0,1\}$, waarbij $\{0,1\}^{n}$ staat voor de verzameling van alle $n$-bit binaire strings.¹⁴¹⁴ 14 Om een voorbeeld te geven: $\{0,1\}^{2}$ is de verzameling van bitstrings van lengte 2, oftewel: $\{00,01,10,11\}$. En de klassieke $\mathrm{NOT}$-operatie werkt als $\mathrm{NOT}\colon\{0,1\}^{1}\to\{0,1\}$, omdat het een enkele bit als invoer verwacht, en een enkele bit als uitvoer. Je kunt de invoer $x\in\{0,1\}^{n}$ van deze functie zien als een vraag en de uitvoer, de bit $f(x)$, als het antwoord. Elke keer dat je de functie $f$ uitvoert op een bepaalde invoer, stel je een vraag die hoort bij die specifieke invoer en krijg je een ja/nee antwoord dat hoort bij de functiewaarde.

Je kunt bijvoorbeeld de toegang tot een harde schijf of geheugen modelleren met een orakel. Stel dat je 4 bits aan geheugen hebt, dan kun je deze modelleren als een functie $f:\{0,1\}^{2}\to\{0,1\}$ die, gegeven een binair adres, de bijbehorende bit teruggeeft. Als je bijvoorbeeld alle vier de bits wilt weten, moet je $f$ vier keer berekenen om de vier waardes $f(00),f(01),f(10),f(11)$ te krijgen.

Wat belangrijk is om op te merken, is dat in onze situatie de berekeningen die we willen oplossen niet gaan over het vinden van de waarde van $f$ bij een specifieke invoer. Zulke problemen zijn triviaal omdat ze opgelost kunnen worden door het orakel maar één keer te raadplegen, want dit is precies wat het orakel doet – het vertelt je de waarde van de functie op elke gewenste invoer. Het soort problemen waarin we geïnteresseerd zijn, zijn wat subtieler. We willen een bepaalde eigenschap van de functie $f$ bepalen door deze zo weinig mogelijk aan te roepen.

Stel bijvoorbeeld dat we willen weten of $f(x)=0$ voor alle $x\in\{0,1\}^{n}$. In dit geval kunnen we het orakel vragen naar willekeurige waarden van $x$ totdat we er een vinden waarbij $f(x)=1$. We zullen zo andere voorbeelden van zulke problemen zien.