Rekenen met atomen

Een quantumcomputer doet meer met minder bits. Denkbare oplossingen voor de taaiste problemen overweegt hij niet een voor een, maar allemaal tegelijk. Alles dankzij het golfkarakter van de materie.

Cryptografen zweren bij grote getallen. Ze verstoppen hun geheimen in priemfactoren: getallen die slechts deelbaar zijn door één en door zichzelf. Voorbeelden zijn 7 of 37, maar er zijn er ook van honderd cijfers of meer - een grootste priemgetal is er niet. Door ze met elkaar te vermenigvuldigen 'lossen ze op' in het produkt en waar het bijzondere van 259 met het blote oog nog valt te onderkennen, vergt het al snel een supercomputer en een vracht rekentijd om veelcijferige priemfactoren terug te vinden, en zo de sleutel tot een code te achterhalen. Bij een getal van 129 cijfers hadden 1600 werkstations verspreid over de hele wereld er onlangs acht maanden voor nodig.

Dat komt omdat er geen efficiënte strategie - algoritme zegt de informaticus - bestaat om getallen in hun priemfactoren te ontbinden. Computers mogen steeds krachtiger worden, bij getallen van 250 cijfers kost het kraken zoveel tijd dat de 'public-key'-cryptograaf (of liever: de bankdirecteur) van die algoritmes niet langer wakker ligt. Dat wil zeggen: tot voor ruim een jaar. November 1994 publiceerde Peter W. Shor van het Amerikaanse AT&T Bell laboratorium een baanbrekend algoritme dat wel in staat bleek snel de samenstellende factoren uit een monstergetal te zeven. Er is één maar: Shor's aanpak werkt alleen op een quantumcomputer.

De klassieke computer, in bedrijf sinds de jaren veertig, bestaat uit een rijtje bits - nullen en enen - alsmede de 'machinerie' om van de ene configuratie tot de volgende te komen. Het blijft een natuurkundig apparaat: waar de informaticus spreekt van het binaire getal 1010011 (83 in het tientallig stelsel), ziet de fysicus op een plakje silicium een rijtje condensatoren al dan niet op een spanning van 5 volt staan. Die condensatoren meten nog maar een honderdste van een haardikte, een getal dat door betere lithografische technieken nog zal afnemen.

Maar niet onbeperkt. Bij verdere miniaturisatie met nog eens een factor honderd, wanneer de individuele atomen in beeld beginnen te komen, neemt de quantummechanica het roer over en raakt het klassieke functioneren van IC's verstoord. Al sinds de jaren zestig, toen computers nog in zalen stonden, is hierover door pioniers als Rolf Landauer en Charles Bennett (beiden van IBM) nagedacht. Beroemd is de voordracht van Richard Feynman voor de jaarvergadering van de American Physical Society in 1959. Onder het motto 'There's Plenty of Room at the Bottom' rekende Feynman zijn gehoor voor dat de gezamenlijke inhoud van 's werelds nuttige boekenbezit, dat hij op zo'n 24 miljoen banden schatte, met gemak in een stofdeeltje paste, ervan uitgaande dat iedere bit aan informatie voldoende had aan een kubus van 5x5x5 atomen. 'Don't tell me about microfilm!'

Het zijn schalen waar de natuurkunde van de soldeerbout het af laat weten en bedrijven als Texas Instruments hebben onderzocht hoe quantumfysica de problemen van te dunne draadjes en warmteontwikkeling van geminiaturiseerde klassieke computers kan helpen oplossen. In de jaren tachtig maakten onderzoekers als Paul Benioff en David Deutsch van de nood een deugd door computers te modelleren die de quantumtheorie niet als lapmiddel maar juist als uitgangspunt namen. Waren dat theoretische exercities, sinds enkele jaren is ook het experimentele onderzoek naar quantumcomputers in een stroomversnelling geraakt en zijn de eerste prototypen van onderdelen een feit. Niet toevallig achtten Scientific American, Science èn Physics Today afgelopen oktober de tijd rijp voor een overzichtsartikel.

Ook in Nederland zijn de eerste schuchtere schreden gezet op weg naar een quantumcomputer. In Amsterdam zoekt AIO Barbara Terhal onder begeleiding van theoretisch fysicus Bernard Nienhuis en theoretisch informaticus Paul Vitányi sinds enkele maanden naar quantum-algoritmes voor optimaliseringsproblemen. De eerste Ph.D. in quantumcomputing, Andre Berthiaume, is als postdoc verbonden aan Vitányi's groep op het CWI (Centrum voor Wiskunde en Informatica). En aan de TU Delft is Hans Mooij zich aan het bezinnen op welke manier de onderzoeksschool 'Micro-elektronica' aldaar quantumschakelingen zou kunnen bouwen, en hoe die zouden kunnen functioneren in een computerarchitectuur. In april gaat Mooij met sabbatical en het plan is in Amerika en Japan de relevante onderzoeksgroepen op te zoeken en van de zomer mee te doen aan een workshop over quantumcomputers in Santa Barbara. Bij terugkeer in Nederland verwacht de Delftse hoogleraar met een onderzoeksvoorstel te komen.

Idiootste dingen

Quantumtheorie is paradoxaal - absurd zeggen sommigen - en experimenten hebben het keer op keer bewezen. 'Wie zich erin verdiept zonder dat het hem duizelt, heeft de essentie totaal gemist', zei de Deense quantumvader Niels Bohr. Wij mensen, toegerust om ons in de wereld van het alledaagse staande te houden, hebben te aanvaarden dat op atomaire schaal intuïtief de idiootste dingen gebeuren. Neem de materie: atomen zijn deeltjes èn golven, zegt de quantumtheorie, twee zielen in een borst. Materiegolven zijn er de oorzaak van dat atomen (kernen met wolken elektronen er omheen) alleen bepaalde energieën aannemen. Het laagste niveau heet de grondtoestand en door absorptie van een foton (lichtdeeltje) met de juiste energie raakt het atoom in een aangeslagen toestand. Bij terugkeer naar de grondtoestand komt een foton van die energie weer vrij.

Zoals twee stemvorken een samengestelde toon voortbrengen, zo kunnen ook quantumgolven horend bij verschillende energieniveaus worden 'opgeteld'. De quantumgolf van een deeltje zegt iets over de kans om dat deeltje in de loop van de tijd op een bepaalde plaats aan te treffen: 'God dobbelt'. In een samenstelling of superpositie van meerdere quantumtoestanden bivakkeert het elektron als het ware in diverse banen tegelijk: 'quantumidiotie' in optima forma. Pas als de superpositie wordt verstoord door interactie met de omgeving, bijvoorbeeld een botsing met een passerend foton, blijkt waar het elektron 'echt' zit. Bij geïsoleerde systemen laat zo'n onthulling soms lang op zich wachten en in de tussentijd slaat de quantumcomputer zijn slag.

Superpositie betekent hier dat het systeem - een serie bits - in vele toestanden tegelijk zit die parallel aan elkaar evolueren. Als elk van die evoluties een berekening voorstelt, is de quantumcomputer dus bezig het geheel aan uitkomsten uit te rekenen. Net zoals geluid en anti-geluid elkaar opheffen, zullen de parallele rekenpaden met elkaar interfereren. Het is nu de kunst de golven met de juiste uitkomst elkaar te laten versterken (positieve interferentie), terwijl de rest elkaar uitdooft. Waar een gewone computer voor iedere parallelle taak een aparte microprocessor nodig heeft, volstaat de quantumcomputer met één.

Qubits

Als we de grondtoestand met een 0 associëren, en een aangeslagen toestand met een 1, is een rijtje waterstofatomen net zo goed in staat een binaire code te representeren als een serie condensatoren. Zodra een techniek beschikbaar is om informatie van de quantumbits (qubits) te lezen en, nadat ermee is gerekend, er weer op weg te schrijven, én de samengestelde toestand blijft in tact, komt de quantumcomputer binnen de horizon. Het grote verschil met de klassieke variant is dat daar een toestand halverwege 0 en 1 een condensator van 2,5 volt oplevert die in de praktijk alleen maar ellende geeft, terwijl de 'gemengde' toestand voor het functioneren van de quantumcomputer essentieel is.

Tot nu toe heeft het onderzoek zich geconcentreerd op optische ontwerpen. Het was de Amerikaanse fysicus Isidor Rabi die liet zien hoe informatie op een quantumsysteem kan worden weggeschreven. Stel we hebben een atoom in de grondtoestand. Als we een 0 willen wegschrijven doen we niets, bij een 1 sturen we laserlicht op het atoom af van precies de frequentie om het atoom de sprong naar een aangeslagen toestand te laten maken. Met andere woorden: de bit klapt om.

Lezen kan een laser ook. Kies de foton-energie zo, dat atomen die al in een aangeslagen toestand zitten, naar een nog hoger energieniveau springen. Binnen de kortste keren vallen ze weer terug en het foton dat daarbij wordt uitgezonden verraadt dat het om een 1 ging. Zat het atoom in de grondtoestand, dan doet het laserlicht niets en weten we dat we met een 0 te maken hebben.

Van lezen en schrijven is het een kleine stap naar rekenen. Klassieke elektronische schakelingen doen dat door een aantal basishandelingen domweg keer op keer te herhalen - zij het met grote snelheid. Drie bewerkingen - logische poorten zegt de informaticus - volstaan: NOT, COPY en AND. Een NOT-poort (of invertor) klapt een bit om: 0 wordt 1 en omgekeerd. Bij COPY krijgt de ene bit de waarde van de andere. Een AND-poort vergelijkt twee bits en zet bij twee enen een derde bit op 1 (in alle andere gevallen wordt het 0). Alle logische en rekenkundige operaties, zo toonde de Ierse wiskundige George Boole in de 19de eeuw aan, zijn via combinaties van NOT, COPY en AND-poorten uitvoerbaar.

Bij quantumcomputers is het niet anders. In aanmerking komen microholtes gevuld met fotonen of spin (draaibeweging om de eigen as) van zowel atoomkernen als elektronen. Maar ook quantum dots, miniatuur-doosjes met een beperkt aantal elektronen die zich als kunstmatige atomen gedragen, of netwerken van supergeleidende eilandjes. Het zijn deze laatste technieken waarop de Delftse groep van Mooij zijn kaarten heeft gezet.

Optische grapppen

Van optische 'grappen' met energieniveaus in atomaire systemen of 'omslachtig gedoe' met micro-holtes verwacht Mooij voorlopig weinig. 'Ik heb grote twijfels of je daarmee ooit een quantumcomputer zult kunnen bouwen. Er zijn een paar qubits gemaakt, maar niemand is gekomen met een architectuur waarin voldoende componenten op een goed gecontroleerde manier met elkaar praten, waar echt gerekend wordt. Waar iedereen mee worstelt is dat de superpositie van quantumtoestanden, waar het allemaal om begonnen is, absoluut niet verstoord mag worden. Dus dient je systeem geen enkele wisselwerking met de omgeving te vertonen. Voor de experimentator een heidense, welhaast onmogelijke klus.'

In Delft probeert men het met supergeleidende schakelingen van mesoscopische afmetingen: in de orde van een duizendste millimeter. Op die schaal bestaan voorwerpen nog altijd uit veel atomen, maar de quantumtheorie doet al van zich spreken. Mooij: 'We hebben hier ervaring met eilandjes van supergeleidend materiaal, aan elkaar gekoppeld via Josephson-verbindingen. Dat zijn barrières maar door hun golfkarakter zijn de elektronen in staat er toch doorheen te tunnelen. Ook doen we onderzoek naar quantum dots, gebiedjes op het grensvlak van een halfgeleider waaruit de elektronen worden weggedrukt door er een negatief geladen metaal op te leggen. Dat zijn kunstmatige atomen met specifieke energieniveaus die je van buitenaf kunt beïnvloeden. De technieken om die devices te maken beheersen we goed en ook kunnen we er netjes aan rekenen.'

Een Delftse quantumcomputer zou gebruik kunnen maken van enkel-elektron-effecten (één elektron op een eiland erbij maakt wezenlijk uit) in combinatie met een koppeling tussen verschillende eilandjes door quantumtunneling. Elektronen kunnen zich dan op verschillende eilanden tegelijk bevinden: de superpositie die je hebben wil. Maar voor serieproduktie van dit soort bits is het nog te vroeg. Mooij: 'Zoals we nu in Delft quantum dots maken, zijn er geen twee hetzelfde en hun functioneren is erg gevoelig voor verontreinigingen. Maar dat zal met verfijndere lithografie snel verbeteren. De bottleneck bij quantumrekenen is de interactie met de omgeving. De bits moeten elkaar voelen maar hoe dat kan zonder dat die omgeving meedoet is nog onduidelijk.'

Toevalsgenerator

Voorlopig denkt Mooij aan configuraties van acht qubits, eventueel met meerdere in- en uitgangen. Als hij zo'n quantumcomputertje binnen tien jaar aan de praat heeft, is hij dik tevreden. Samen met Dewilde, hoogleraar elektrotechniek en partner in de Delftse onderzoeksschool 'Micro-elektronica', wil Mooij onderzoeken of zijn quantumcomputertjes in een zinvol netwerk zijn onder te brengen. 'Uitgangspunt is dat ze iets moeten kunnen wat een gewone computer niet kan. Alles staat of valt met samengestelde quantumtoestanden die het voldoende lang uitzingen.'

Een bescheiden quantumcomputer kan al heel wat. Zelfs met één qubit kan hij zijn klassieke concurrent de loef afsteken. Immers, als er sprake is van een superpositie van de toestanden 0 en 1, en je stuurt fotonen om de coherentie te verbreken, dan zal het atoom in de helft van de gevallen een foton uitzenden (bit op 1) en in de andere helft gebeurt er niets (bit op 0). Kortom: met zo'n qubit heb je een toevalsgenerator in handen, een kwaliteit waar een gewone computer niet van terug heeft.

Bij meerdere bits en een parallelle architectuur is de quantumcomputer pas echt in zijn element. Een quantumsysteem op een gewone computer simuleren vergt een hoeveelheid stappen die exponentieel toeneemt met de omvang van het systeem en met de tijdsduur waarover het wordt gevolgd. Een parallelle quantumcomputer van 100 qubits, zo zag Richard Feynman in 1985 in, komt dankzij het verschijnsel superpositie in pakweg 100 stappen minstens zover als een klassieke computer van miljarden bits in jaren. Het is deze gedachte die informatici, zeker nadat Shor zijn algoritme voor het vinden van priemfactoren wereldkundig maakte, tot grote opwinding brengt.

Wie wil onderzoeken wat de quantumcomputer te bieden heeft, zal een brug moeten slaan tussen quantummechanica en informatica. 'Ik zal me complexiteitstheorie eigen moeten maken,' zegt theoretisch fysicus Bernard Nienhuis. Zijn (en Vitányi's) promovendus Barbara Terhal onderzoekt in hoeverre de quantummechanica een complex systeem kan helpen om bij afkoeling zijn laagste energietoestand te vinden. 'Parallel geschakelde qubits in een samengestelde toestand volgen niet één geschiedenis', licht Nienhuis toe, 'ze volgen vele geschiedenissen tegelijk. Pas een meting aan het eind van de rit dwingt het systeem als het ware een dobbelsteen op te gooien om zo zijn toestand te bepalen. Het is de kunst de elementen zo te schakelen dat de meest waarschijnlijke eindtoestand je de gezochte informatie geeft.'

Graaf-isomorfie

Als voorbeelden van de problemen die hij met een quantumcomputer zou willen oplossen noemt Nienhuis optimaliseringsproblemen. Het gaat dan om relaties tussen quantumberekeningen en klassiek moeilijke problemen, zoals het nagaan of twee netwerken eigenlijk hetzelfde zijn (graaf-isomorfie). Dat het ontwerpen van optimale bedradingsschema's voor chips, en - hoe kan het anders - het handelsreizigerprobleem (zoek de kortste route langs een serie 'steden') met een quantumcomputer efficiënt zijn op te lossen gelooft, zo zegt Vitányi, niemand. In de informatica hebben deze klassiekers de naam NP compleet te zijn: alle bestaande algoritmes zijn qua rekentijd exponentieel in het aantal steden of componenten. Dat loopt al snel uit de hand.

Het klassieke ontbinden van getallen in priemfactoren is, alhoewel niet een NP compleet-probleem, exponentieel in het aantal rekenstappen om tot de oplossing te komen. Nienhuis: 'Het revolutionaire van het algoritme van Shor is dat het kwadratisch is in de hoeveelheid bits van het te ontbinden getal.' Ter verklaring van Shor's algoritme trekt de Amsterdamse hoogleraar een parallel met muziek. 'Met getaltheorie reduceert Shor eerst het probleem tot het vinden van de periode van een periodieke functie. Dat is analoog aan het vinden van de grondtoon van een aangeslagen accoord. Bij het beluisteren van muziek is het gemakkelijk de melodie eruit te pikken, gedragen als die wordt door de sopranen of de hoogste instrumenten. Lastiger is het de grondtonen te volgen, en juist die zijn een gemeenschappelijke eigenschap van alle stemmen samen. Precies daarin is een quantumcomputer goed.'

Er is één maar: in de praktijk telt het quantumorkest nog zo armzalig weinig musici dat iedere verwijzing naar symfonieën vooralsnog een gotspe is. Bij de huidige stand van het experimentele onderzoek mogen we blij zijn met hier en daar een duo - laat het een kwartet zijn - dat ultrakorte stukjes ten gehore brengt. Daar is niets mis mee: het geeft aanleiding tot interessante fysica en zelfs de quantumsolist heeft zijn nut als toevalskunstenaar. Maar de partituur van Shor vereist een flinke zit voor honderden orkestleden. Tot in lengte van dagen toekomstmuziek, menen experimentatoren als Hans Mooij.

Paul Vitányi is optimistischer. 'Bij de uitvinding van de quantumcrypografie, vijftien jaar geleden, dachten fysici ook dat zoiets subtiels in de praktijk niet kon', aldus de in Hongarije geboren hoogleraar. 'Maar het werkt. Van een halve meter bij de eerste proefopstelling van IBM een paar jaar geleden, worden in Los Alamos National Laboratories inmiddels via quantumtheorie versleutelde boodschappen over een lengte van 20 kilometer door een tv-kabel verstuurd. Quantumcryptografie is veilig tenzij de huidige quantumfysica onwaar is. Het humoristische feit doet zich voor dat zodra quantumcomputers gerealiseerd worden - en in Oostenrijk is er een van 2 qubits gebouwd - alle huidige standaard cryptografische methoden de vuilnisbak in kunnen, behalve de quantumcryptografie. De bankdirecteur kan nòg rustig gaan slapen.'