Quantum computers komen eraan

Razendsnel rekenen op de allerkleinste natuurkundige deeltjes

Quantum computing is een relatief jong onderwerp binnen de computerwetenschap. De eerste onderliggende concepten werden dertig jaar geleden geïntroduceerd door de beroemde natuurkundige Richard Feynman. In de tussenliggende tijd hebben we veel geleerd over het programmeren van quantum computers en inmiddels kunnen we ook verstandige dingen zeggen over de theoretische rekenkracht ervan. Het afgelopen decennium hebben veel universiteiten quantum computing dan ook als vak opgenomen in hun curricula.

Ondanks al die verworvenheden is er een cruciaal onderdeel op dit gebied dat we nog steeds niet onder de knie hebben: het daadwerkelijk bouwen van een quantum computer. De qubits die de hardware-basis moeten vormen onder deze nieuwe systemen zijn nog niet in voldoende aantallen te maken en ook niet lang genoeg houdbaar om er grotere quantum-toepassingen op te draaien. Op dit moment kan ongeveer een handvol bruikbare qubits tegelijkertijd worden gemaakt en overleven ze niet langer dan een paar seconden. Daarmee is inzet van de huidige quantum computers nog beperkt tot hele specifieke toepassingen in bijvoorbeeld de cryptografie.

Bits

Een qubit, kort voor quantum-bit, is als bouwsteen onder de quantum computer vergelijkbaar met de gewone bit die de basis vormt onder al onze huidige computertechnologie. Naast de vele parallellen zijn er tegelijkertijd echter cruciale verschillen.

Gewone bits (binary digits) kunnen alleen de waarde 0 of 1 hebben. Hoe een bit vervolgens in een computer wordt geïmplementeerd is in principe onafhankelijk van de logische waarde ervan. Zo wordt digitale informatie in computerchips overgedragen en bewerkt middels signalen van verschillende spanningsniveau's, bijvoorbeeld 0 en 1,2 Volt. Ook in traditionele geheugens en op verbindingskabels wordt met verschillende voltages gewerkt. Ouderwetse harde schijven daarentegen maken gebruik van magnetische polarisatie om dezelfde digitale informatie op te slaan. Zo zou je net zo goed een computer kunnen bouwen die met waterdruk en kleppen, met mechanische onderdelen, of met knikkers, rolbanen en poortjes werkt. De logische principes van de eerste digitale computers waren ook niet anders dan die van de huidige machines, alleen werden in plaats van transistoren eerst relais (elektromagnetische schakelaars) en later vacuumbuizen (de voorlopers van de transistor) gebruikt.

In de praktijk hebben ontwerpers voor de opslag, overdracht en bewerking van digitale informatie voor elk onderdeel natuurlijk een implementatie gekozen die aansluit bij de toepassing, de benodigde snelheid en capaciteit, en het beschikbare budget. Al die afwegingen zien we bijvoorbeeld terug in de geheugenhiërarchie van een systeem.

Qubits

Qubits zijn fundamenteel anders dan gewone bits. Ze zijn ontwikkeld volgens de quantummechanica, waar rekeneenheden niet alleen de waarde 0 of 1 kunnen aannemen, maar ook een beetje de ene waarde en tegelijkertijd een beetje de andere waarde. Een qubit kan bijvoorbeeld voor de ene helft de waarde 0 hebben en voor de andere helft de waarde 1, of voor tweederde de waarde 0 en voor eenderde de waarde 1.

Wie bekend is met statistische kansverdelingen kan een qubit wel vergelijken met een stochast. Ook daarvan is de waarde zelf niet exact bekend; je weet alleen iets over de kansverdeling ervan. Cruciaal verschil tussen een stochast en een qubit is dat die eerste een probabilistisch (statistisch) concept is en die laatste een quantummechanisch concept. Dat betekent dat de waarde van een stochast weliswaar niet precies bekend is, maar wel voor elke mogelijke waarde vaststaat hoe groot de kans daarop is. Terwijl de waarde van een qubit tegelijkertijd een beetje 0 kan zijn en een beetje 1. Bij quantum computers spreekt men dan ook niet van kansverdelingen maar van superposities.

 

Superposities

De kracht van die superposities wordt duidelijker als we meerdere qubits bundelen tot een serie, op vergelijkbare wijze waarop in de traditionele deterministische wereld bits worden samengepakt tot bytes. Kijken we bijvoorbeeld naar een rijtje van drie gewone bits, dan kan dat één van acht verschillende waarden aannemen: 000, 001, 010, 011, 100, 101, 110, 111.

Maar drie gebundelde qubits hebben tegelijkertijd een beetje van elk van deze acht waarden. Hoewel de echte quantum-computeraars dit slordig zouden vinden, noteren we de fracties voor de acht verschillende waarden bijvoorbeeld als volgt: (1/4, 0, 0, 1/4, 0, 1/2, 0, 0). Dat betekent dat de drie qubits voor een kwart de waarde 000 hebben, voor een kwart de waarde 011 en voor de helft de waarde 101.

Zoals in de uitweiding over golffuncties hieronder uitgelegd is, zijn stochasten en qubits wiskundig gezien echter niet gelijkwaardig. In een superpositie kunnen de fracties namelijk ook negatief zijn. Juist die operaties maken berekeningen (interferentie) mogelijk die (zeer waarschijnlijk) niet met een klassieke machine uitgevoerd kunnen worden.

Exponentiële rekenkracht

Superposities maken het mogelijk om met een heleboel waarden tegelijkertijd te kunnen rekenen. Voor één qubit zijn dat twee waarden (2¹; 0 en 1), voor drie qubits zijn dat acht verschillende waarden (2³) en voor tien qubits zijn dat al 1024 verschillende waarden (2¹⁰). In wiskundige termen gesproken: het aantal verschillende waarden dat een superpositie tegelijkertijd kan bevatten is exponentieel ten opzichte van het aantal qubits. En dat is precies waar de extra rekenkracht van de quantum computer zijn oorsprong vindt.

Het antwoord van een quantum-berekening kan echter meestal niet direct uitgelezen worden. Zodra je een superpositie bekijkt, stort deze immers ineen tot een van de concrete waarden binnen die superpositie. Op dat moment wordt de overgang van de quantummechanische naar de statistische wereld gemaakt. Welke specifieke waarde die ineenstorting oplevert, kun je op voorhand niet weten. Wel is het zo dat elke bitwaarde een kans heeft om op te treden die overeenkomt met de grootte van zijn gekwadrateerde absolute amplitude (wat we hierboven de fractie noemden).

Kansverdelingen

Dat betekent dat je een quantum-berekening meerdere malen moet uitvoeren, waarna je de quantummechanische waarde van de laatste superpositie terug kunt afleiden uit de onderlinge verhoudingen van alle verschillende concrete antwoorden die je hebt gemeten. Deze komen immers overeen met de kansverdeling van die superpositie. Een goed quantum-algoritme leidt dus tot een superpositie waarin het antwoord verborgen zit in de kansverdeling. Dat kan bijvoorbeeld betekenen dat op een bepaald qubit in eenderde van de gevallen de waarde 0 gemeten wordt en in tweederde van de gevallen de waarde 1. De kans dat je zo inderdaad het juiste antwoord vindt is eenvoudig te vergroten door de quantum-berekening vaker uit te voeren.

Quantumtheoretici hebben inmiddels slimme algoritmen ontwikkeld waarbij alleen de juiste berekeningen en eenduidige antwoorden overblijven. Daarbij maken ze onder andere gebruik van interferentie. Op die manier hoeft een berekening nog maar één keer uitgevoerd te worden om direct het goede antwoord te geven.

Quantum-berekeningen

Bewerkingen op qubits verlopen ook heel anders dan de operaties die we kennen uit de deterministische wereld. Gewone bits worden steeds op logische wijze met elkaar vergeleken: hebben twee bits allebei de waarde 1 (AND)? heeft minstens één van de bits de waarde 1 (OR)? hebben alle bits de waarde 0 (NOR)? enzovoort. Die logische operaties worden uitgevoerd op elektrische signalen door transistors die in silicium-chips zijn vastgelegd en in een bepaald patroon met elkaar zijn verbonden. Zo worden logische poorten gecombineerd tot registers, reken-units, state machines en alle andere digitale onderdelen die tesamen bijvoorbeeld een processor vormen.

Berekeningen door een quantum computer worden altijd binnen dezelfde groep van qubits uitgevoerd (een superpositie kan niet worden gecopieerd; of beter gezegd: bij het copiëren gaat het origineel verloren). Een bewerking verandert dus de bestaande superpositie. Net zoals voor klassieke digitale systemen zijn er ook voor quantum computers basisoperaties waarmee alle berekeningen uitgevoerd kunnen worden.

Modellering

Er zijn diverse manieren om die quantum-bewerkingen te modelleren. De analytisch-wiskundige theorie is gebaseerd op de hierboven beschreven golffuncies: lineaire combinaties van basiswaarden (notatie: |0> en |1>) met complexe coëfficiënten (de amplitudes). De bol van Bloch vormt dan een meetkundige representatie van een enkel qubit. Aan de bovenkant en de onderkant zijn respectievelijk de waarden |0> en |1> weergegeven. Een superpositie is ergens een punt op het oppervlak van de bol, waarbij de hoogte (de breedtecirkel) de verhouding van de amplitudes (en dus de kansen) van de twee basiswaarden bepaalt. Dat het superpositie-punt persé ergens op het oppervlak van de bol rond de z-as moet liggen (met een vaste afstand tot de oorsprong) is het gevolg van de randvoorwaarde dat de som van de kansen altijd 1 moet zijn. In deze modellering bestaan (eenvoudige) quantum-bewerkingen uit meetkundige rotaties: verplaatsingen van het superpositie-punt over het boloppervak.

Maar voor techneuten is het natuurlijk veel handiger om over quantum-bewerkingen te praten in de bekende termen van poorten en circuits. Barenco heeft symbolen ontwikkeld die gebruikt kunnen worden om bewerkingen vast te leggen in diagrammen. Hiernaast zie je bijvoorbeeld een 'Controlled NOT' poort (CNOT): de negatie-operatie (|0> wordt |1>, en andersom) op de onderste qubit wordt alleen uitgevoerd als de bovenste qubit de waarde |1> heeft.

Hoewel naarstig gezocht wordt naar verschillende (natuurkundige) implementatievormen om deze quantum-operaties daadwerkelijk uit te kunnen voeren, is de ondersteuning van de volledige set niet noodzakelijk. Net zoals je in de traditionele informatica aan bijvoorbeeld een AND-poort en een NOT-poort genoeg hebt om alle schakelingen te kunnen bouwen, zijn voor een quantum computer drie poorten voldoende.

Berekenbaarheid

Naar aanleiding van de honderste geboortedag van Alan Turing publiceerden we vorig jaar al een uitgebreid verhaal over Turing-machines en de theorie van berekenbaarheid en complexiteit van problemen en algoritmen. Om op vergelijkbare manier over de rekenkracht van quantum computers te kunnen praten, heeft de natuurkundige David Deutsch de Quantum Turing Machine (QTM) bedacht. En op vergelijkbare wijze is er een klasse van problemen gedefinieerd die met een quantum computer in redelijke tijd op te lossen zijn — dat wil zeggen in polynomiale tijd ten opzichte van de lengte van de input.

Nevenstaand figuur laat zien hoe deze klasse BQP (Bounded Error Quantum Polynomial Time) zich verhoudt tot de traditionele complexiteitsklassen. Althans, voor zover we dat nu denken te weten. Hoewel dat nog niet bewezen is — zoals dat overigens voor de meeste relaties tussen de verschillende complexiteitsklassen geldt — lijkt het er op dat quantum computers inderdaad problemen op kunnen oplossen die we met de huidige deterministische computers (klasse P) niet aankunnen. Sterker nog, inmiddels zijn er al diverse quantum-algoritmen bekend voor problemen waarvoor nog niemand een deterministisch algoritme heeft kunnen bedenken. Aan de andere kant heeft nog niemand een quantum-algoritme gevonden waarmee ook de moeilijkste problemen (in de klasse NP Compleet) in redelijke tijd oplosbaar worden. Het vermoeden is op dit moment dan ook dat quantum computers fundamenteel krachtiger zijn dan gewone computers, maar ook weer niet zo krachtig dat ze de moeilijkste problemen voor ons oplossen.

Algoritme van Shor

Een van de meest interessante quantum-algoritmen die we nu kennen is het algoritme van Shor, gebaseerd op quantum Fourier-transformaties. Daarmee kunnen de priemfactoren van een integer worden berekend. Deze factorisatie kan worden ingezet om een groot deel van de asymetrische (public key) cryptografie die we nu op internet gebruiken te kraken. Meest in het oog springend is de TLS/SSL beveiliging die voor de toegang tot websites (HTTPS, "het sleuteltje") en het transport van mail-berichten (STARTTLS) wordt gebruikt. Hetzelfde geldt voor SSH (Secure Shell) en alle protocollen die via deze versleutelde verbindingen worden getunneld. Elektronische handtekeningen onder digitale documenten zijn een goede derde.

Zodra de eerste, echt bruikbare quantum computer het licht ziet, zijn al deze beveiligingen in een klap waardeloos. De huidige public key technologie is namelijk gebaseerd op de moeilijkheid om het product (de vermenigvuldiging) van twee grote priemgetallen weer in zijn factoren te ontleden.

Ondanks dat die quantum computer nog niet bestaat, is het dus van cruciaal belang om nu al te werken aan de wiskundige theorie voor deze machines. Bijvoorbeeld om quantum-proof algoritmen te vinden voor een nieuwe vorm van public key cryptografie die wel bestand is tegen quantum-krakers.

Verstrengeling

Was je al verbijsterd over superposities die tegelijkertijd een beetje de ene waarde en tegelijkertijd een beetje de andere waarde aannemen, dan doet verstrengeling (entanglement) daar nog een schepje bovenop. De qubits hoeven zelfs helemaal niet meer bij elkaar in de buurt te zijn als ze eenmaal verstrengeld zijn om zich toch als één superpositie te blijven gedragen. Veranderingen aan het ene qubit hebben dus direct consequenties voor het andere qubit. Sterker nog: een meting aan de een bepaalt bij de ineenstorting zelfs veel sneller dan het licht de waarde van de ander. Dat in tegenstelling tot bijvoorbeeld de elektromagnetische en zwaartekrachtvelden in de klassieke mechanica die zich met de snelheid van het licht uitbreiden.

Quantum Key Distribution (QKD)

Zo maken quantum computers ook hele nieuwe beveiligde communicatiemethoden mogelijk. Quantummechanische verstrengeling kan bijvoorbeeld gebruikt worden om absoluut veilige communicatiekanalen op te zetten. Informatie kan onderweg niet worden afgeluisterd door een zogenaamde man-in-the-middle zonder dat dit aan de uiteinden van de verbinding te zien is.

Hiertoe wordt eerst een serie (paarsgewijs) verstrengelde qubits over de twee partijen verdeeld, om die vervolgens te laten ineenstorten tot hun definitieve waarde. Beide partijen hebben nu dezelfde (of nauwkeuriger gezegd: de tegenovergestelde) sleutel. Ze kunnen dat controleren door een deel van de zo verkregen bits met elkaar te vergelijken. Komen die bits inderdaad met elkaar overeen, dan weten de partijen zeker dat niemand anders die sleutel heeft. Een man-in-the-middle kan de waarde van een verstrengeld qubit onderweg immers niet achterhalen zonder deze te laten ineenstorten. Op deze manier wordt het distributieprobleem voor symmetrische sleutels opgelost. En dat is weer waarvoor asymetrische cryptografie vaak wordt ingezet: het veilig uitwisselen van een symmetrische sessie-sleutel.

Belangrijke kanttekening hierbij is dat dergelijke quantum-systemen wel kunnen worden gebruikt om sleutels uit te wisselen maar niet om sneller dan het licht te communiceren. De ineenstorting aan twee zijden gebeurt inderdaad sneller dan het licht, maar omdat de concrete uitkomst door het toeval wordt bepaald, kan daarbij geen informatie worden overgedragen.

Wetenschappelijk onderzoek

De afgelopen jaren zijn her en der bij universiteiten en andere onderzoeksinstellingen de eerste quantumnetwerken gebouwd waarmee verstrengelde communicatiekanalen en teleportatie (van quantum-toestanden) mogelijk worden. Zo lieten onderzoekers uit het Britse Cambridge vorig jaar zien dat het mogelijk is om verstrengelde fotonen via een regulier glasvezelnetwerk te verspreiden.

Hier in Nederland wordt theoretisch onderzoek naar quantum-algoritmen en complexiteit uitgevoerd door het CWI (Centrum Wiskunde en Informatica). Daar draait een groep onder leiding van Harry Buhrman mee met de wereldtop op dit gebied. Andere belangrijke onderzoeksgroepen bevinden zich in Zurich (ETH), Oxford (UK), Cambridge in de UK, Cambridge in de VS (MIT), Berkeley, Canada (Waterloo), Singapore en Beijing.

Majorana-deeltjes

Maar ook wat betreft de onderliggende hardware is Nederland een belangrijke speler. Een jaar geleden verwierf de Delftse onderzoeksgroep van Leo Kouwenhoven wereldfaam met de ontdekking van het Majorana-deeltje. Behalve voor het Standaard Model heeft dit deeltje in het bijzonder waarde voor ontwikkelaars van quantum-systemen. Het zou namelijk wel eens een heel geschikte bouwsteen voor de qubits kunnen zijn.

Maar ook elders in de wereld gebeurt van alles. Tweakers.net brengt natuurlijk regelmatig nieuws over technische en wetenschappelijke doorbraken op dit gebied. In die berichten kunnen we lezen hoe wetenschappers steeds meer en steeds stabieler qubits kunnen creëren, opslaan en transporteren. Bovendien lijkt het Canadese bedrijf D-Wave inmiddels inderdaad de eerste commerciële quantum computer aan te kunnen bieden.

Eén-bits quantum computer

Wie van de lezers nu al zijn eigen quantum computer wil aanschaffen, kan daarvoor betaalbaar terecht bij het Zwitserse bedrijf ID Quantique. Zij verkopen onder andere random nummer generators in de vorm van een kastje met USB-aansluiting of een PCI(e)-insteekkaart. Het enige dat hun Quantis-systeem doet is steeds een qubit in superpositie (1/2, 1/2) brengen om deze vervolgens te laten ineenstorten tot een 0 of een 1. Op die manier wordt met een snelheid van 4 of 16 Mbps een willekeurige stroom van enen en nullen gegenereerd.

En vergis je niet: deze één-bits quantum computer levert daarmee een hele belangrijke functie. Voor traditionele (deterministische!) computers is het genereren van een echte random reeks namelijk een schier onmogelijke opgave. Zo heeft RAND Corporation, een bekend Amerikaans militair onderzoeksinstituut, in de vijftiger jaren een boek uitgegeven (heruitgegeven in 2001) met daarin een miljoen random getallen. Het fungeerde decennia lang als een standaardwerk in met name de cryptografie en de statistiek. Tegenwoordig wordt voor het genereren (en bewaren en gebruiken) van cryptografisch sleutelmateriaal voor serieuze en grootschalige toepassingen — denk aan DNSSEC — meestal speciale hardware ingezet.

Wearables

Hoe lang het nog duurt voordat bruikbare quantum computers daadwerkelijk beschikbaar zijn durven we niet te zeggen. Afhankelijk van wetenschappelijke doorbraken op dit gebied kan dat een paar jaar zijn of nog een paar decennia. Maar dat ze er aan zitten te komen is zeker. Daarmee komt dan een fundamenteel andere computertechnologie beschikbaar.

En als de geschiedenis van de deterministische computers een goede voorspeller is, gaan we daarna een nieuw tijdperk in van steeds snellere en kleinere systemen. Wie weet maakt een quantum-rekeneenheid over twintig jaar standaard deel uit van onze smartphone of anderszins draagbare computer.