Een korte geschiedenis van quantum computing bij het CWI

Ter gelegenheid van CWI’s 76e verjaardag op 11 februari 2022 vertellen we de korte geschiedenis van quantumcomputing bij het CWI.

Publication date: 11-02-2022

“Alles wat we deden was raak”

In maart 1996 publiceerde Harry Buhrman als eerste CWI-wetenschapper een onderzoeksresultaat op het terrein van het toen piepjonge veld van quantum computing. Inmiddels is quantum computing een volwassen, internationaal onderzoeksveld waarbij ook het bedrijfsleven wil aanhaken. De droom om met een quantumcomputer praktisch relevante problemen op te lossen, komt steeds dichterbij. Ter gelegenheid van CWI’s 76e verjaardag vandaag (11 februari 2022) vertellen we de korte geschiedenis van quantumcomputing bij het CWI.

 

Fase 0: Hoe het begon

In november 1994 ging Paul Vitanyi, toenmalig leider van de CWI-onderzoeksgroep Algoritmen en Complexiteit, naar het IEEE Symposium on Foundations of Computer Science, gehouden in Santa Fe, New Mexico (VS). Daar hield de Amerikaanse onderzoeker Peter Shor een voordracht over een baanbrekend algoritme dat hij had ontwikkeld. 

Met dat algoritme zou een quantumcomputer, een machine waarover men toen alleen nog maar kon dromen, grote getallen snel kunnen ontbinden in zijn priemfactoren. Als dat zou lukken, dan zou deze machine wereldwijd gebruikte digitale beveiligingen kunnen kraken. Welke problemen zou een quantumcomputer nog meer veel sneller kunnen oplossen dan een klassieke computer? vroegen de toehoorders van Shor zich af. De belangstelling voor het onderwerp quantum computing kreeg ineens een grote impuls.

“Ik hoorde de voordracht van Shor en vond het heel interessant”, vertelt Vitanyi meer dan een kwart eeuw later. “Voordat ik terugvloog naar Nederland, ging ik in Canada langs bij mijn collega Ming Li, met wie ik een jaar eerder ons boek An introduction to Kolmogorov complexity and its applications had gepubliceerd. Geïnspireerd door Shors algoritme vroegen we ons af of we een soortgelijk probleem zouden kunnen oplossen: kan een quantumcomputer efficiënt bepalen of twee ongelabelde grafen die verschillend gerepresenteerd zijn dezelfde graad zijn? Helaas kwamen we nergens op uit, maar de interesse bleef.”

De eerste promovendi

Na zijn bezoek aan de conferentie en aan zijn Canadese collega, keerde Vitanyi terug naar het CWI. Toenmalig directeur Gerard van Oortmerssen wilde het instituut meer praktisch onderzoek laten doen. “Die omslag heette ‘de kanteling’”, vertelt Vitanyi. “Om daarin mee te gaan, bedacht ik dat we de groep Algoritmen en Complexiteit zouden kunnen omdopen tot ‘Quantum Computing en Advanced Systems Research’. Ik trok Andre Berthiaume als postdoc aan. Hij was als eerste in de wereld gepromoveerd op het nieuwe terrein van quantum computing. Berthiaume kwam bij Gilles Brassard aan de Universiteit van Montreal vandaan, een pionier die samen met Charles Bennett van IBM de quantumcryptografie heeft uitgevonden.” 

                                  Paul Vitanyi 

Niet veel later trok Vitanyi eerst Harry Buhrman aan als postdoc, en daarna Barbara Terhal en Wim van Dam als promovendi. Vitanyi: “De hoop was dat we op het CWI op een nog onontgonnen terrein relatief snel het laaghangende fruit konden plukken.” Vitanyi zelf schreef in 1995 in het overzichtsartikel 'Physics and the new computation' over nieuwe mogelijkheden die aan de horizon van quantum computing gloorden.

Fase 1: “Alles wat we deden was raak”

Promovenda Barbara Terhal kwam uit de theoretische natuurkunde, met name de quantum-theorie. In haar promotieonderzoek bestudeerde ze aan het CWI de relatie tussen het quantummechanische begrip verstrengeling en quantumalgoritmen. Terhal werd in 1999 de eerste in Nederland die promoveerde in quantum computing, en nog cum laude ook.

Wim van Dam onderzocht tijdens zijn promotietijd hoe je dankzij een quantumcomputer met minder bits kunt communiceren dan met een klassieke computer. Hij promoveerde in 2000 in de natuurkunde aan de Universiteit van Oxford en in 2002 aan de Universiteit van Amsterdam (UvA) in de informatica op het onderzoek dat hij aan het CWI deed samen met Harry Buhrman. Tegenwoordig staat Van Dam aan het hoofd van Quantum Algorithms bij het bedrijf QC Ware in de VS.

Buhrman begon op het CWI in 1994 en kwam net als Vitanyi uit het vakgebied van de computationele complexiteit, dat onderzoekt welke rekenkundige problemen wel en niet efficiënt te berekenen zijn op een computer. “Zelf had ik in 1992 voor het eerst over quantum computing gehoord in een lezing van Gilles Brassard”, vertelt Buhrman. “Toen ik op het CWI kwam werken, sprak ik uitgebreid met Andre Berthiaume en besloot ik om verder de kant van quantum computing op te gaan. De vraag wat je wel en niet efficiënt kunt bereken wordt door de quantumcomputer uitgebreid en dat wilde ik verder onderzoeken.”

                                        Harry Buhrman

De eerste publicaties

“Harry Buhrman is er helemaal ingedoken, en heeft de meest bijzondere dingen gedaan”, zegt Vitanyi over Buhrmans bijdragen. Buhrmans eerste onderzoeksresultaat in quantum computing, en daarmee ook het eerste onderzoeksresultaat van een CWI-onderzoeker in dit nieuwe veld, stamt uit 1996. Titel:'A short note on Shor's factoring algorithm. En kort was het: nog geen twee pagina’s.

                      Eerste pagina van Harry Buhrmans publicatie uit 1996

Twee jaar later, in 1998, publiceerde Buhrman een artikel samen met Richard Cleve en Avi Wigderson: 'Quantum vs. Classical Communication and Computation'. Dat artikel is in de loop van de tijd veel geciteerd. “Het was een tijd van leren en proberen”, vertelt Buhrman, “en zo’n beetje alles wat we deden in die jaren was raak.”

Binnen de onderzoeksgroep van Vitanyi ontstond zo in de tweede helft van de jaren negentig een subgroep die zich specialiseerde in quantum computing en die een internationale reputatie begon te verwerven. In 1997 startte theoretisch informaticus Ronald de Wolf als promovendus in de groep. Met Vitanyi en Buhrman als promotoren promoveerde De Wolf cum laude in 2001 op het onderwerp ‘Quantum Computing and Communication Complexity’. 

In deze begintijd pasten CWI-onderzoekers inzichten uit quantum computing onder andere toe op versnelling van communicatie, quantumversies van Kolmogorov complexiteit en quantum fingerprinting. Ze ontdekten onder andere manieren om bepaalde problemen sneller te berekenen en enkele algemene beperkingen van quantumcomputers, ontdekkingen die later standaard textboekmateriaal werden

Fase 2: Bredere Europese interesse

Rond 1999 ging het onderzoek naar quantum computing aan het CWI een nieuwe fase in, vertelt Buhrman: “Tot dan toe concentreerde het werk zich vooral in Montreal bij Gilles Brassard, in Oxford bij David Deutsch en Artur Ekert, in Bristol bij Richard Jozsa, en bij Charlie Bennett bij IBM en Peter Shor bij AT&T. Maar nu begonnen steeds meer Europese collega’s aan te haken. Er kwam meer internationale erkenning voor het onderzoek naar quantumsoftware.” 

Zo leidde Buhrman tussen het jaar 2000 en 2004 het Europese onderzoeksproject Quantum Algorithms and Information Processing. Ook organiseerde en formeerde hij samen met Ronald de Wolf de 4th Workshop on Quantum Information Processing (QIP) die in 2001 in Amsterdam plaatsvond. Deze conferentie trok 150 deelnemers uit 24 landen, waaronder pioniers zoals Charles Bennett en David DiVincenzo (IBM Yorktown Heights), Gilles Brassard (Montreal) en de Nederlandse Nobelprijswinnaar natuurkunde Gerard ’t Hooft (Utrecht). Deze workshop is nu uitgegroeid tot de belangrijkste in het vakgebied en telt nu meer dan duizend deelnemers.

              4th Workshop on Quantum Information Processing, Amsterdam (2001)

Quantum-grenzen afbakenen

Inhoudelijk lag in deze fase de nadruk op het ontdekken van de ondergrenzen van quantum computing en op de theorie van quantuminformatie. Buhrman: “Welke problemen zijn niet efficiënter op te lossen met een quantumcomputer? We classificeerden allerlei soorten problemen en ontwikkelden instrumenten voor het ontwerpen van quantumalgoritmen.”

Een van de belangrijke resultaten van CWI-onderzoekers uit deze jaren is het 'quantum fingerprinting'-algoritme dat Buhrman, de Wolf en twee collega’s van de Universiteit van Calgary in 2001 publiceerden. Dit algoritme kan grote bestanden uit twee afzonderlijke bronnen exponentieel veel efficiënter met elkaar vergelijken dan mogelijk is op een klassieke computer. 

In 2016 demonstreerden Chinese onderzoekers voor het eerst een natuurkundige implementatie ervan. Met het algoritme vergeleken ze twee gigabyte aan videogegevens via de uitwisseling van slechts 1300 fotonen, ongeveer de helft van wat klassiek nodig zou zijn.

Buhrman werd in het jaar 2000 aangesteld als hoogleraar Quantum Information Processing aan de UvA en in 2002 nam hij officieel het stokje van Vitanyi over en werd leider van de CWI-onderzoeksgroep Algoritmen en Complexiteit. Ronald de Wolf werd in 2011 naast zijn CWI-positie aan de UvA aangesteld als hoogleraar theoretische informatica, een positie die hij van Paul Vitanyi overnam.

Fase 3: Oprichting van QuSoft

Sinds 1994 was het onderzoek naar quantum computing internationaal flink gegroeid. Toch ging de aandacht van de buitenwereld vooral uit naar het bouwen van een quantumcomputer, en daarmee naar de experimentele fysica en de quantumhardware. In 1997 publiceerden MIT-onderzoekers de eerste meetresultaten aan een enkel quantumbit. Daarna kwam er zo’n beetje elk jaar een quantumbit bij. In 2001 werd een rudimentaire quantumcomputer met zeven quantumbits gebouwd die voor het eerst Shors algoritme uitvoerde op het getal 15.

“Veel hardware-mensen zeiden: de software komt vanzelf wel”, vertelt Buhrman. “Maar dat is niet zo. Daarom begonnen wij, als onderzoekers van quantumsoftware, een plaats op het podium te claimen. Wij moesten steeds aangeven: wij zijn er ook nog!” Dat besef begon breder door te dringen en leidde er uiteindelijk toe dat CWI en UvA samen in 2015 het eerste quantumsoftware-onderzoekscentrum in de wereld oprichtten: QuSoft. Naast zijn rol als groepsleider van de CWI-groep Algoritmen en Complexiteit en hoogleraar aan de UvA werd Buhrman nu ook oprichter en mede-directeur van QuSoft, samen met UvA-hoogleraar Kareljan Schoutens. 

                                         QuSoft-lustrum, december 2020

Quantum-ecosysteem in Nederland

Een andere nieuwe stimulans kwam in 2017 toen het Ministerie van Onderwijs, Cultuur en Wetenschap een tienjarige Zwaartekracht-subsidie van 18,8 miljoen euro toekende aan het Quantum Software Consortium, een samenwerking tussen QuSoft, CWI, Universiteit Leiden, QuTech, TU Delft, UvA. 

Binnen dit consortium werken quantumsoftware-onderzoekers in Nederland voor het eerst ook nauw samen met de quantumhardware-onderzoekers. Het idee is dat het Quantum Software Consortium software ontwikkelt voor kleine quantumcomputers en voor een klein quantum-internet. Vervolgens moet die software getest gaan worden op de quantumhardware die aan de TU Delft en de Universiteit Leiden wordt ontwikkeld en op een quantumnetwerk tussen Amsterdam, Delft, Leiden en Den Haag.

Fase 4: Industrie raakt geïnteresseerd

De quantumhardware maakte in de eerste twee decennia van de 21e eeuw grote stappen vooruit. Zo demonstreerden onderzoekers van Google in 2019 een mini-quantumcomputer met 53 qubits die in iets meer dan drie minuten een berekening uitvoerde die volgens het bedrijf tienduizend jaar zou kosten op een klassieke computer. Een quantumcomputer die praktische problemen kan oplossen komt daarmee steeds dichterbij. 

Mede daardoor ging ook het onderzoek naar quantum computing weer een nieuwe fase in, een fase waarin het bedrijfsleven actief betrokken wil zijn bij de ontwikkeling van quantumsoftware. Buhrman: “Bedrijven willen niet achterblijven bij hun concurrenten en ze willen weten wat ze in de toekomst aan quantum computing kunnen hebben. Zo werkt QuSoft inmiddels samen met bedrijven als ABN AMRO, Bosch, Toyota en IBM.”

Wat bedrijven aan quantum computing denken te hebben, ligt grofweg gesproken op drie terreinen. Allereerst het beter begrijpen hoe de natuur op quantummechanisch niveau werkt. Op dit terrein kan de quantumcomputer de ontwikkeling van nieuwe materialen en katalysatoren versnellen. Een tweede terrein is het optimaliseren van bepaalde problemen, zoals het vinden van de snelste route, het optimaliseren van treinverkeer of het zoeken in grote databergen. En een derde terrein is dat van de informatieveiligheid. Er is al quantumversleuteling ontwikkeld die zelfs de quantumcomputer niet kan kraken.

Groeispurt

QuSoft heeft het aanzien dat het CWI al sinds eind jaren 90 had in de wereld van quantum computing uitgebreid. Inmiddels telt het onderzoeksinstituut voor quantumsoftware al ongeveer zeventig junior en senior onderzoekers, waarvan er zo’n twintig op het CWI werken. “We zijn zo hard gegroeid”, besluit Buhrman, “dat we plannen hebben voor een eigen gebouw op de campus van het Amsterdam Science Park. Daar komt ook een deel van het experimentele-fysicaonderzoek van de UvA bij. Met een apart onderzoeksinstituut voor quantum computing zouden we op eigen benen komen te staan, maar de steun van het CWI blijft belangrijk.”

 

Meer informatie