Een miljoen voor computer van de toekomst

De Nederlandse Organisatie voor Wetenschappelijk Onderzoek NWO heeft een VICI-subsidie toegekend aan Harry Buhrman van het Centrum voor Wiskunde en Informatica (CWI) in Amsterdam. Deze subsidie, maximaal 1.250.000 euro, is een van de hoogste Nederlandse onderzoeksbeurzen. Buhrman zal het gebruiken voor zijn onderzoek naar wat mogelijk de computer van de toekomst is: de quantumcomputer.

Publication date: 06-01-2004

De Nederlandse Organisatie voor Wetenschappelijk Onderzoek NWO heeft een VICI-subsidie toegekend aan Harry Buhrman van het Centrum voor Wiskunde en Informatica (CWI) in Amsterdam. Deze subsidie, maximaal 1.250.000 euro, is een van de hoogste Nederlandse onderzoeksbeurzen. Buhrman zal het gebruiken voor zijn onderzoek naar wat mogelijk de computer van de toekomst is: de quantumcomputer.

De werking van de huidige, klassieke computers is gebaseerd op bits, geheugeneenheden die de waarde nul of één kunnen hebben. Alle computerprogramma's, van de eenvoudigste tekstverwerker tot de weersvoorspellingssoftware van het KNMI, werken intern door het manipuleren van deze bits. De quantumcomputer haalt een fundamenteel uitgangspunt van de klassieke computer onderuit: een quantumbit of qubit kan tegelijk nul en één zijn. Dit wordt ook wel superpositie genoemd.

Slim gebruik van superpositie
Mede door de vreemde eigenschappen van de qubits bleef quantum computing heel lang een academische curiositeit; intrigerend maar niet erg bruikbaar. Halverwege de jaren negentig veranderde dit, toen onderzoekers manieren ontdekten om slim gebruik te maken van superpositie. Zo kan een quantumcomputer in korte tijd grote getallen ontbinden in factoren. De huidige beveiligingstechnieken van dataverkeer zijn gebaseerd op de aanname dat dit een tijdrovende klus is. Een netwerk van aan elkaar geschakelde klassieke computers doet er momenteel enkele maanden over. Met een quantumcomputer zijn deze codes in een fractie van de tijd te kraken. Aan de andere kant zijn er ook quantumcodes ontwikkeld die onkraakbaar zijn, zelfs voor quantumcomputers.

Nieuwe quantumalgoritmes
Een bruikbare quantumcomputer bestaat nog niet. Natuurkundigen, onder meer van IBM, zoeken naar oplossingen voor problemen als de kwetsbaarheid van quantumdata. Daarnaast doen informatici onderzoek naar limieten van de quantumcomputer en zoeken ze nieuwe, efficiënte quantumalgoritmes. Buhrmans groep aan het CWI was de eerste in Nederland die zich bezighield met dit theoretische onderzoek. Met financiële steun van de Europese Unie heeft Buhrman volgens de VICI-jury ``waardevolle bijdragen geleverd aan de ontwikkeling van quantum computing en algoritmes''. Zijn onderzoek resulteerde onder meer in een ``quantum fingerprinting'' algoritme dat grote bestanden op twee verschillende locaties efficiënt met elkaar kan vergelijken. Deze techniek zou in de toekomst gebruikt kunnen worden voor digitale handtekeningen.

Opvallend onderzoek
De toekenning van de VICI-subsidie laat zien dat er veel belang wordt gehecht aan onderzoek naar quantum computing. Het juryrapport spreekt van een ``zeer opvallend onderzoeksgebied''. Met de 1.250.000 euro kan Buhrman de komende vijf jaar zijn onderzoek naar nieuwe quantumalgoritmes versterken. Daarnaast werkt hij aan foutencorrigerende codes die gebruikt kunnen worden om quantumdata te beschermen en ontwerpt hij algoritmes speciaal voor werkende prototypes van de quantumcomputer.

Achtergrondinformatie over quantum computing is te vinden in de bijlage hieronder.
Meer informatie over Buhrmans onderzoek is te vinden op www.cwi.nl/ins4


6 januari 2004

CWI - Centrum voor Wiskunde en Informatica, Amsterdam

De onzichtbare kracht van quantumcomputers
Achtergronden bij het persbericht Miljoen euro voor computer van de toekomst

Quantumcomputers maken op een slimme manier gebruik van de bizarre eigenschappen van quantummechanica. Onwerkbaar complexe berekeningen kunnen hiermee snel worden uitgevoerd. Hoe werkt de quantumcomputer en wat maakt hem zo bijzonder?

De ontwikkeling van computers verloopt in een hoog tempo. Verbeterde technieken maken het mogelijk om kleinere rekenelementen op chips te plaatsen, waardoor ze steeds sneller worden. Maar er zit een limiet aan deze groei: structuren op een chip kunnen niet kleiner worden dan enkele atomen. Op die kleine schaal gelden bovendien de wetten van de quantummechanica, die veel ingewikkelder zijn dan de ~Qklassieke~R natuurkundige wetten die de werking van de huidige chips beschrijven. Maar deze complicatie heeft ook één voordeel: quantummechanica maakt een nieuwe manier van rekenen mogelijk.

Gezond verstand
Quantummechanica ontstond in de eerste helft van de twintigste eeuw toen natuurkundigen bij het bestuderen van atomen verschijnselen ontdekten die ze met de tot dan toe bekende klassieke natuurkunde niet konden verklaren. Ondanks het grote succes van de theorie is het altijd een moeilijk onderwerp gebleven. Quantummechanica lijkt vaak direct in te gaan tegen de normale intuïtie. Neem bijvoorbeeld een lichtdeeltje (foton) dat via een scherm met twee dunne spleten op een gevoelige fotografische plaat wordt geschoten. Het gezond verstand zegt dat het foton of door de ene spleet gaat of door de ander. De quantummechanica beweert echter dat het foton door allebei de spleten tegelijk reist, onzichtbaar voor de waarnemer. Dit wordt superpositie genoemd. De beide routes kunnen elkaar bovendien beïnvloeden. Uit het experiment met de dubbele spleet blijkt bijvoorbeeld dat er bepaalde zones zijn op de fotografische plaat waar fotonen nooit terecht komen. Op die plekken dooft het foton zichzelf als het ware uit. Dit verschijnsel heet interferentie.

Sneller rekenen
Bij klassieke computers hebben de geheugenelementen (bits) de waarde nul of één. In een quantumcomputer werken de bits volgens de wetten van de quantummechanica. Een quantumbit of qubit is in superpositie: hij is nul en één tegelijk. Rekenen met één qubit is hierdoor gelijk aan rekenen met twee getallen tegelijk. Bovendien neemt het aantal getallen waarmee tegelijk kan worden gewerkt snel toe met iedere extra qubit. Met dertig bits zijn al meer dan een miljard combinaties van nullen en enen te vormen (om precies te zijn twee tot de dertigste). Dertig qubits zijn daarmee een superpositie van al deze ``getallen''. Een enkele rekenoperatie op dertig qubits bewerkt dus in één keer meer dan een miljard getallen. Ter vergelijking: een operatie op dertig klassieke bits bewerkt maar één getal van die miljard. Quantumcomputers zijn hierdoor in theorie veel sneller dan de klassieke machines.

Uitdoven van uitkomsten
Probleem is dat de enorme hoeveelheid informatie in de qubits onzichtbaar is, net als de routes van het foton. Om ze uit het geheugen te halen, gebruiken quantumcomputers interferentie. Het is de kunst om de rekenprocessen zo in te richten dat van alle uitkomsten die tegelijk bestaan in het geheugen de verkeerde zichzelf uitdoven en alleen de goede overblijven. Dit is helaas niet altijd mogelijk. Quantumcomputers zijn om die reden geschikt voor specifieke taken. Zo is er bijvoorbeeld een quantumalgoritme ontwikkeld dat veel sneller databases kan doorzoeken dan de huidige programma's. Een ander quantumalgoritme kan in korte tijd grote getallen ontbinden in factoren. Een klassieke computer doet daar momenteel honderden eeuwen over. Het is om die reden dat het ontbinden van getallen de basis vormt voor veel databeveiligingstechnieken. Een quantumcomputer kraakt deze codes in een paar minuten.

Verlies van informatie
Zo groot als de mogelijkheden van quantumcomputers zijn, zo groot zijn de problemen bij hun ontwikkeling. Als qubits worden losse atomen gebruikt. De toestand van een qubit kan echter onder invloed van de omgeving worden verstoord, waardoor informatie verloren gaat. Om dit verlies tegen te gaan, zijn foutcorrigerende codes ontwikkeld. Bij deze techniek wordt de informatie verspreid over meerdere qubits waardoor de kwetsbaarheid vermindert. Daarnaast is het ``lezen en schrijven'' van informatie op atomen momenteel nog erg moeilijk. Een aantal onderzoeksgroepen is er in geslaagd om een kleine quantumcomputer te bouwen, maar deze machines hebben een beperkte rekenkracht en kunnen nog alleen functioneren in een laboratorium.

Gerenommeerde onderzoeksinstellingen en bedrijven
Hoewel een bruikbare machine nog ver weg lijkt, wordt er veel geïnvesteerd in het onderzoek naar quantum computing. Gerenommeerde onderzoeksinstellingen als NASA, MIT en de universiteit van Oxford en bedrijven als IBM, Lucent en Microsoft hebben quantum computing groepen. Ook Nederland draagt bij aan de ontwikkeling van het vakgebied. Onderzoekers van het Centrum voor Wiskunde en Informatica (CWI) in Amsterdam deden als eersten in Nederland onderzoek naar quantumcomputers. Deze groep onder leiding van Harry Buhrman houdt zich bezig met de ontwikkeling van nieuwe efficiënte quantumalgoritmes. Ze ontwierpen onder meer een algoritme om efficiënt grote databestanden te vergelijken. Deze techniek zou in de toekomst gebruikt kunnen worden voor digitale handtekeningen. Daarnaast ontwikkelde de groep ook een methode om beperkingen van quantumcomputers te bewijzen.