‘De kwantumcomputer zal de wereld veranderen’

In de jaren dertig braken geleerden zich het hoofd over hoe ze een computer – die nog alleen op papier bestond – een rekensom konden laten maken. Anno nu onderzoekt Ronald de Wolf de (on)mogelijkheden van de kwantumcomputer. “Bankverkeer of Amazon.com – je kunt het straks allemaal kraken.”

Kwantumcomputers spreken tot de verbeelding van velen. Dat is niet vreemd. Als de mysterieuze axiomata van de kwantummechanica kunnen worden toegepast in chips, verwerven computers immers welhaast toverachtige rekenkracht – zo is althans het idee. Waar een schakeling in uw Pentium 0 of 1 representeert, kunnen de schakelingen in een kwantumcomputer – de zogenaamde qubits – allerlei waarden tegelijk opslaan. Op die manier goochel je met een handjevol qubits al met heel grote getallen.

Wel is dit alles in hoge mate theorie. Om te beginnen hebben de geleerden (onder andere in Delft, zie Computable 3 november 2006) al hun handen vol aan de beheersing van één enkele qubit. Minstens even belangrijk is de ontwikkeling van de software. Omdat qubits zich volstrekt anders gedragen dan bits, moeten de algoritmen (software-eenheden) van de kwantumcomputer van de grond af aan opnieuw worden bedacht. Dat is geen sinecure.

Nobelprijswinnaar Richard Feynman legde in 1982 de conceptuele basis voor de kwantumcomputer in zijn artikel ‘Simulating physics with computers’. De natuurkundige David Deutsch uit Oxford werkte dit idee in 1985 verder uit. Pas in 1994 ontwikkelde de Amerikaan Peter Shor het eerste, althans in theorie, bruikbare algoritme.

Vóór Shor was quantum computing een piepklein vakgebied, maar zijn algoritme had een enorme impact. Het ontbindt getallen namelijk in hun priemfactoren. Theoretisch-informatici hebben bewezen dat dit programma de meeste encryptiemethoden – van banken bijvoorbeeld – kinderlijk eenvoudig kan kraken. Het wachten is alleen nog op de hardware. Op 13 februari kondigde het Canadees bedrijf D-Wave aan binnenkort de eerste commerciële kwantumcomputers te leveren.

Werkend systeem?

Ronald de Wolf, verbonden aan het CWI (Centrum voor Wiskunde en Informatica) te Amsterdam, doet onderzoek naar kwantumcomputers. Hij legt de mogelijkheden en problemen uit. D-Wave pretendeert een werkende kwantumcomputer met zestien qubits te hebben gebouwd.

“Dat geeft meteen reden tot scepsis, temeer omdat ze niet zeggen wát ze doen. Het verhaal van D-Wave lijkt mij grotendeels een hype. Trouwens: áls ze al zo’n computer hebben – wat ik niet geloof – dan heb je nog altijd duizenden qubits nodig om het kwantumalgoritme van Shor te kunnen gebruiken, geen zestien.”

Wat is er zo geweldig aan het algoritme van Shor?

“Het algoritme van Peter Shor factoriseert grote getallen in hun priemfactoren. Dat klinkt als een esoterisch probleem, maar het is ontzettend belangrijk. De cryptografie is gebaseerd op de gedachte dat dat een heel moeilijk probleem is – en dus nauwelijks uit te voeren met een standaardcomputer. Met een kwantumcomputer is dat echter een heel gemakkelijk probleem.”

Gelukkig voor het bankwezen is niemand tot nu toe in staat gebleken een bruikbare kwantumcomputer te bouwen. Waarin schuilt de moeilijkheid?

“Een gewone computer gebruikt schakelaartjes die aan of uit staan, we drukken dit uit als 0 en 1. Die schakelaars zijn klein, maar nog altijd van een omvang dat we ze goed kunnen bouwen en manipuleren. Een kwantumcomputer maakt gebruik van de wetten van de kwantummechanica, en die openbaren zich meestal pas op het niveau van deeltjes: atomen, fotonen, ionen, noem maar op. Om een kwantumbit te modelleren wil je dus één deeltje gebruiken. Als je honderd kwantumbits wilt gebruiken, dan heb je honderd deeltjes naast elkaar. Die moeten bestuurd worden, net zoals een gewone computer operaties doet op zijn bits. Het grootste probleem daarvan is dat er heel veel ruis is. Die deeltjes zijn ontzettend klein, en dus ook zeer gevoelig. Als er buiten een tram voorbijrijdt, gebeuren er al rare dingen met die deeltjes. Je moet ze enerzijds goed afschermen van de omgeving om die ruis te voorkomen. Anderzijds moet je er toch operaties op kunnen doen. Die twee dingen bijten elkaar.”

“Het vinden van een middenweg is echt cutting edge experimentele fysica. De natuurkunde is inmiddels zo ver dat ze een paar van die deeltjes redelijk goed kunnen manipuleren. Kwantumcomputertjes met drie of vier qubits zijn inmiddels al realiteit, maar voor het algoritme van Shor zijn er dus minimaal een paar duizend nodig.”

Rekenkracht

Waarin schuilt – in potentie – de rekenkracht van een kwantumcomputer?

“In de populaire pers lees je vaak dat de kracht erin schuilt dat een gewone computer met bits werkt, en een kwantumcomputer met qubits. Een bit vertegenwoordigt óf de ene waarde óf de andere. Qubits vertegenwoordigen ze, op grond van de wetten van de kwantumfysica, allebei. Daarmee groeit het aantal mogelijkheden exponentieel. Metqubits heb je 2n mogelijke rekenresultaten. Dat is al snel heel veel.

“Toch is dit bepaald niet het complete verhaal. Het is namelijk mogelijk om op klassieke computers zogenaamde probabilistische algoritmes – software dus – te draaien. Dat zijn als het ware algoritmes die muntjes opwerpen, en aan de hand van die uitkomst een bepaald pad volgen. Als jemuntjes opwerpt, heb je net zo goed 2n mogelijke mogelijke uitkomsten.”

2n is dus niet de essentie, maar wat dan wel?

Normaal definiëren we een kans tussen 0 en 1. Dit is wat gebeurt in een normale probabilistische computer (=een gewone computer waarop een probabilistisch programma draait). Maar: qubits (waar de kwantumcomputer mee rekent) kunnen twee tegengestelde toestanden in zichzelf verenigen. We rekenen dan met waarden tussen -1 en 1. Die waarden, ook wel amplitudes genoemd, kun je met elkaar laten interfereren.

Hebt u misschien een metafoor?

“Denk aan golven. Die kunnen elkaar versterken of uitdoven – interferentie dus. De uitkomst van een enkele kwantumberekening kun je ook voorstellen als een golf, en de berekening zelf als het opeenstapelen van golven. Al die resulterende golven laat je interfereren. Welnu: als je dat goed doet (en ik laat nu natuurlijk een groot aantal stappen weg) doven de delen van de golf waar je niet op zit te wachten elkaar uit. De relevante delen daarentegen vertonen een scherpe piek. Dáár zit de uitkomst van je berekening.”

En daar zit ook het verschil met een gewone probabilistische computer.

“Juist. Want met waarden tussen 0 en 1 – de waarden van de klassieke kansberekening – kun je geen golffunctie creëreh waarbinnen negatieve interferentie bestaat. Plussen en minnen optellen tot nul – kortom het uitfilteren van ongewenste uitkomsten – gaat niet.

Cryptografie

Laten we de banken dan nu eens bang maken. Hoe kraakt Shors programma de encryptiecodes?

“Stel je hebt een enorm groot getal, en we noemen dat n. Je kunt dat omzetten in een exponentieel lange periodieke serie van waarden in superpositie, dus een serie die zichzelf gaat herhalen. Als je de zogenaamde ‘periode’ vindt, kun jefactoriseren. Shors algoritme berekent de periode van die serie op een efficiënte manier door er een zogeheten Fourier-transformatie op los laten. Deze breekt een complexe golf op in de elementaire onderdelen, net zoals je een trillende snaar kunt herleiden tot de som van elementaire trillingen. Na de transformatie zal deze kwantumtoestand veranderd zijn in iets waar de meeste amplitude zit op punten die gerelateerd zijn aan die periode. Daarmee kun je de periode vinden en dus het getal factoriseren.”

Hoe groot zijn de getallen waarvan men in de hedendaagse cryptografie gebruikmaakt?

“Veel bedrijven zullen nog 512 bits gebruiken, maar dat is al niet veilig meer. Hier op het CWI probeert een groep zo groot mogelijke getallen te factoriseren, met het oog op cryptografie. Als je een paar maanden de tijd hebt, kun je met een gewone computer een getal van 512 bits factoriseren en dus de daarbij behorende code kraken.

“Let wel: de rekentijd die klassieke algoritmes nodig hebben loopt exponentieel op met het aantal bits. Als je 1024 bits gebruikt, kost dat dus niet twee keer zoveel rekentijd, maar astronomisch véél meer rekentijd. 1024 bits wordt dan ook gezien als absoluut veilig. Ténzij… je met kwantumcomputers gaat werken. Bankverkeer of websites als Amazon.com zijn allemaal op dit soort cryptografie gebaseerd. Dat kun je dan dus allemaal kraken. In dit opzicht zal de kwantumcomputer de wereld echt veranderen.”

Databases doorzoeken

Bestaan er kwantumalgoritmen voor andere toepassingen?

“Een ander bekend kwantumalgoritme is het algoritme van Grover. Dit algoritme kan databases efficiënt doorzoeken, bijvoorbeeld een kaartenbak. Stel: je wilt een telefoonnummer van iemand opzoeken in een alfabetische kaartenbak. Je kunt dan één voor één die kaartjes afzoeken totdat je de gewenste persoon tegenkomt. Als jekaartjes hebt, kost je dat ongeveerstappen. Een kwantumcomputer kan dat met het Grover-algoritme in ?n stappen doen. Dat is geen exponentiële verbetering, maar wel een redelijke verbetering.

“Er zijn verder kleine doorbraken. In februari heeft Edward Farhi bijvoorbeeld een algoritme gepubliceerd voor het sneller doorzoeken van spelbomen in schaakpartijen.”

Factorisatie (encryptie) en databases zijn de geijkte voorbeelden. We krijgen de indruk dat het aantal algoritmen – en dus toepassingen – van de kwantumcomputer vooralsnog niet overhoudt.

“Ja, dat is op dit moment een van de zwakke punten van kwantumcomputing.”

Stemt u dat optimistisch of pessimistisch?

“Je kunt hier op een filosofische manier naar kijken. De fundamentele vraag van de informatica is hoe sterk de sterkst mogelijke computer is die de natuur ons toestaat. We weten dat de natuur zich kwantummechanisch gedraagt – althans volgens de huidige stand der natuurkunde. Als je een fundamenteel informaticus bent, zou je dus eigenlijk altijd een kwantumcomputer moeten onderzoeken, want dat zijn in principe de sterkste computers die we kunnen bouwen. De vraag wat een kwantumcomputer in de praktijk anders of beter kan dan een klassieke computer is een tweede. Dat is een meer pragmatische benadering. We hebben in de loop der tijd behoorlijk wat beperkingen van de kwantumcomputer bewezen. Het blijkt dat je voor de meeste problemen aan een kwantumcomputer niets hebt, omdat die in dat geval niet sterker is dan een klassieke computer. Het belangrijkste doel van mijn soort mensen is echter het vinden van problemen die niet efficiënt met een klassieke computer zijn op te lossen, maar wél met een kwantumcomputer. Tot nu toe hebben we daar inderdaad nog niet veel voorbeelden van.”

Robots en KI

Terug naar wat wél kan: het doorzoeken van grote databases. Kan zoiets niet van pas komen in kunstmatige intelligentie? Robots die zich een weg banen door een natuurlijke omgeving moeten alles wat ze zien spiegelen aan een grote database om te begrijpen wát ze zien. Met gewone computers lukt dat nog nauwelijks – hoe krachtig de processoren tegenwoordig ook zijn.

“Robots lossen vaak zoekproblemen op. Met een kwantumcomputer als aansturing kunnen ze in principe sneller grotere databases doorzoeken. Aan de andere kant is een kwantumcomputer ontzettend kwetsbaar.”

Zou het kunnen dat wij als mensen géén moeite hebben met dit soort taken omdat in de hersenen kwantumeffecten een rol spelen?

“Ik denk het niet. Je zou het brein kunnen omschrijven als netwerk van neuronen, en in dat opzicht is het brein een klassieke computer. Een neuron is namelijk vrij groot – zo groot dat omgevingsfactoren ervoor zorgen dat het zich als een klassiek object gedraagt. Ik kan bijvoorbeeld mijn hoofd snel heen en weer schudden zonder dat dat noemenswaardig effect heeft. Dat moet je bij een kwantumcomputer niet proberen.”

Ed Croonenberg & Aschwin Tenfelde, Scientific American