Boeken

Thursday, May 13, 2010

Rekenen aan de gedroomde kwantumcomputer


Fundamenteel onderzoek naar de grondslagen van de kwantummechanica levert onverwacht praktisch inzicht in de bouweisen van een toekomstige kwantumcomputer.

Een van de ultieme dromen van natuurkundigen en informatici is het bouwen van een kwantumcomputer. Zo’n kwantumcomputer zou sommige rekenproblemen veel sneller kunnen oplossen dan willekeurig welke klassieke computer ooit voor elkaar kan krijgen. Een gewone computer rekent met een bit als eenheid van informatie: een 0 of een 1.

Een kwantumcomputer is een fundamenteel nieuw type computer, die rekent volgens de wetten van de kwantummechanica. Het equivalent van een bit in de kwantumwereld is een kwantumbit. Een kwantumbit is niet 0 of 1, maar kan tegelijk 0 en 1 zijn. Preciezer gezegd: een kwantumbit kan zich in een superpositie van 0 en 1 bevinden. Als er een kans p is dat het kwantumbit bij de meting 0 is, dan is er een kans (1-p) dat het kwantumbit bij meting een 1 is.

Deze kwantumeigenschap biedt ongekende rekenmogelijkheden. Met twee klassieke bits kun je vier combinaties vormen: 00, 01, 10 en 11, maar nooit tegelijk. Twee kwantumbits kunnen zich echter tegelijk in een superpositie van die vier toestanden bevinden. Dus waar N klassieke bits 2^N toestanden kunnen maken, maar niet tegelijk, kunnen N kwantumbits 2^N toestanden tegelijk maken.

Verstrengeling
Wat ook nieuw is aan een kwantumcomputer ten opzichte van een klassieke computer, is het fenomeen verstrengeling. Bij twee klassieke bits heeft de waarde van het ene bit geen invloed op de waarde van het andere. Kwantumbits kunnen daarentegen verstrengeld zijn. Stel, je genereert twee kwantumbits die zich in een superpositie van de twee toestanden 00 en 11 bevinden. Dat paar heet een EPR-paar.

Vervolgens verwijder je de twee kwantumbits van elkaar, waarna je ze allebei tegelijk gaat meten. Als het eerste kwantumbit dan een 1 is, moet volgens de kwantummechanica het andere kwantumbit ook een 1 zijn. En als het eerste een 0 is, dan is het tweede dat ook. De meting van het ene kwantumbit verandert onmiddellijk de toestand van het andere kwantumbit, hoe ver de twee ook van elkaar verwijderd zijn.

“Verstrengeling en superpositie zijn zo contra-intuïtief”, vertelt hoogleraar Harry Buhrman van het Centrum Wiskunde & Informatica, “dat natuurkundigen nog steeds worstelen met de vraag waarom de kwantummechanica zo in elkaar zit als ze zit. Nu onderzoek ik zelf problemen die een toekomstige kwantumcomputer veel sneller kan oplossen dan een klassieke computer. Het interessante is dat mijn werk automatisch raakt aan de vraag naar de fundamentele aard van de kwantummechanica.”

Een van de problemen die een kwantumcomputer veel sneller kan oplossen dan een klassieke computer, is het agendaprobleem. Stel, Alice woont in Amsterdam en Bob in New York. Ze proberen een afspraak te maken door hun agenda’s te raadplegen. Als de agenda N bits bevat, dan moeten ze in het algemeen al die N bits uitwisselen om een geschikte dag voor een afspraak te vinden. Maar als ze gebruik zouden maken van de EPR-paren uit de kwantumwereld, hoeven ze maar √N bits uit te wisselen. “Door gebruik te maken van verstrengeling”, zegt Buhrman, “kun je sommige communicatieproblemen met de uitwisseling van veel minder bits oplossen.”

Super-kwantumwereld
Om de kwantummechanica op een nieuwe manier te testen, verzonnen Clauser, Horne, Shimony en Holt in 1969 het theoretische CHSH-spel. Het spel kent twee spelers: Alice en Bob. Zij hebben van tevoren een strategie met elkaar afgesproken, maar mogen tijdens het spel niet met elkaar communiceren. Zij krijgen ieder één bit als invoer, zeg x en y. Vervolgens moeten ze één bit als uitvoer genereren, zeg a en b. Zij winnen het spel als ze erin slagen dat ‘x × y= a XOR b’ (a XOR b = 0 als a en b allebei 0 of allebei 1 zijn, anders is de uitkomst 1). In de klassieke wereld kunnen Alice en Bob dit spel met een kans van 75 procent winnen en in de kwantumwereld – met gebruik van een epr-paar – met een kans van iets meer dan 85 procent.

“Nu kun je ook een soort super-kwantumwereld definiëren”, vertelt Buhrman, “waarin je het spel altijd wint, dus met een kans van 100 procent. Het bijzondere van deze super-kwantumwereld is dat je daarin sommige moeilijke communicatieproblemen met de uitwisseling van slechts één bit kunt oplossen. En in deze super-kwantumwereld geldt nog steeds de regel dat je informatie niet sneller dan het licht kunt versturen, zoals dat in de echte kwantumwereld ook niet kan.”

Buhrman heeft met zijn collega’s het regime onderzocht waarin Alice en Bob het CHSH-spel kunnen winnen met een kans die tussen de 85 procent van de echte kwantummechanica en de 100 procent van de super-kwantummechanica in ligt. Zij bewezen dat als je de kans om het spel te winnen verlaagt van honderd naar 90 procent, het oplossen van sommige moeilijke communicatieproblemen nog steeds met een enkel bit kan, zoals in de ideale super-kwantumwereld.

Buhrman: “Bij een winstkans van 85 procent, zoals in de echte kwantumwereld, heb je veel communicatie nodig om sommige van die moeilijke problemen op te lossen. Maar bij een winstkans van 90 procent volstaat altijd slechts dat ene bit. Dit resultaat laat zien dat er een scherpe overgang is van een wereld waarin sommige communicatieproblemen moeilijk zijn op te lossen en een wereld waarin ze juist triviaal zijn.”

Het bewijs dat tot dit resultaat heeft geleid lijkt in eerste instantie alleen van fundamenteel belang voor een beter begrip van de kwantumwereld. Toch blijkt het onverwachte toepassingen te hebben. Buhrman en zijn collega’s hebben het gebruikt om een beter inzicht te krijgen in de bouweisen van een toekomstige kwantumcomputer (zie kader). Desondanks zijn we echter nog ver weg van de bouw van een echte kwantumcomputer. Voorlopig is het in laboratoria alleen nog maar gelukt om simpele berekeningen met enkele kwantumbits uit te voeren.


[kader] De foutenmarge van de kwantumcomputer

Rekenprocessoren bestaan uit logische poorten en er is altijd een kans dat een poort stuk is. Bij een kwantumcomputer speelt de extra complicatie dat kwantumbits in het kwantumgeheugen hun superpositie kunnen verliezen (decoherentie), bijvoorbeeld als ze onvoldoende van de omgeving zijn afgeschermd.

Om te zorgen dat foute poorten en decoherente kwantumbits geen invloed hebben op de uitkomsten van de computer, wil je weten hoeveel fouten de computer tolereert. De ondergrens voor de fouttolerantie van een kwantumcomputer is ongeveer een tienduizendste. Dat betekent dat een kwantumcomputer die in minder dan 1 op de 10.000 logische poorten een fout bevat nog steeds vrijwel zeker de goede uitkomsten levert.

Nu kun je ook een bovengrens definiëren. Als de foutenmarge boven deze grens uitkomt, worden de uitkomsten van de kwantumcomputer volkomen onbetrouwbaar. Tot voor kort lag die bovengrens bij 55 procent. Buhrman en zijn collega’s hebben met hun theoretische verkenningen van de super-kwantumwereld aangetoond dat de bovengrens verlaagd kan worden naar 40 procent.

De uitdaging is om zo precies mogelijk te achterhalen wat de onder- en bovengrenzen zijn voor de fouttolerantie van een kwantumcomputer. Deze grenzen vertellen een experimentator hoe goed hij kwantumbits moet opslaan en bewerken om een werkende kwantumcomputer te bouwen.

Dit artikel heb ik oorspronkelijk geschreven voor het boek Omringd door informatica. Ik heb aan de populair-wetenschappelijke website Kennislink toestemming gegeven om het over te nemen, vandaar dat ik het ook op mijn eigen site heb gezet.