Af en toe lezen we in de pers iets over experimenten met ‘qubits’ en het gebruik van quantummechanica in het uitwisselen van cryptografische sleutels. Deze reeks blogposts heeft tot doel om de achterliggende concepten wat duidelijker te maken en vooral aan te geven wat je nu eigenlijk kan en niet kan met quantummechanica in de IT-wereld.
Quantum wat?
Om een aantal zaken wat in context te plaatsen maken we eerst een uitstapje naar wat fysica. Quantummechanica of Quantumfysica is een theoretisch raamwerk uit de fysica dat tot doel heeft de microscopische wereld te beschrijven, met name de wereld op de schaal van atomen en moleculen. Jullie herinneren zich misschien de wetten van Newton voor de beschrijving van onze alledaagse wereld. Hoe meer je echter de wereld uitvergroot, hoe sneller blijkt dat deze wetmatigheden de wetenschappelijke toets niet meer doorstaan. In de 19de en begin van de 20ste eeuw werden een aantal fysische experimenten uitgevoerd die dit duidelijk aantoonden. Er was nood aan een betere beschrijving van onze wereld op atomair niveau, dit werd onder andere de Quantummechanica.
Een belangrijke ontdekking was de zogenaamde golf-deeltje dualiteit. Kort gezegd kan je een klein deeltje zoals een elektron ook beschrijven als een golf. Dit heeft zeer eigenaardige effecten tot gevolg. Het bekendste experiment dat dit duidelijk weergeeft is het dubbelspleten experiment van Young. Dit illustreert al onmiddellijk het tegen-intuïtieve karakter van quantummechanica, wat het voor iedereen moeilijk maakt om deze theorie te aanvaarden (ook voor Einstein). Misschien heb je al ooit aan een waterpoel twee stenen in het water gegooid. Dat kan je vergelijken met één watergolf die door twee openingen wordt gestuurd. Je kan dan zien dat de golven als cirkels uitdeinen en waar de golven elkaar tegenkomen krijg je interferentie. Op bepaalde plaatsen verdwijnt een stuk van de golf (een piek van de ene golf compenseert het dal van een andere) en op andere plaatsen heb je dan weer een hogere golf (de pieken van beide golven versterken mekaar). Op de figuur wordt dit weergeven op het linkse schema. Als je dit experiment met licht uitvoert krijg een interferentiepatroon met donkere en lichte banden (zie a op de figuur).
Vreemd genoeg krijg je dit gedrag ook met kleine deeltjes zoals elektronen. Je zou verwachten dat elektronen zich gedragen als harde bolletjes die door de ene of andere opening vliegen. Niets is minder waar, je krijgt een verdeling in zones die net zoals bij golven mekaar opheffen of versterken. Zoals je kan zien in de figuur rechts van b tot e krijg je bij de detectie van de aparte elektronen (elke stipje is een gedetecteerd elektron) op de duur een interferentiepatroon met donkere en bleke banden. Het vreemde is dat dit één elektron per keer gebeurt, het is dus alsof het elektron door beide openingen tegelijk gaat en met zichzelf interfereert.Wat je hiervan kan onthouden is dat het deeltje zich lijkt te bevinden in 2 toestanden tegelijk, namelijk het door de ene spleet gaan of de andere. Dat het zich in in twee verschillende toestanden tegelijk bevindt, heet een superpositie. En het heeft een zekere waarschijnlijkheid om zich in een bepaalde toestand te bevinden.
Dat brengt ons op een tweede speciaal element van Quantummechanica: het meten. Zolang je niet meet in welke toestand zich zo een deeltje bevindt, dan is het in een superpositie of combinatie van bijvoorbeeld 2 toestanden, voor de eenvoud 0 en 1. Het moment dat je meet, beïnvloed je het systeem zodanig dat het deeltje zich een welbepaalde toestand zal bevinden, zijnde 0 of 1 en geen combinatie van beide. De superpositie verdwijnt dus. Als we het experiment van hierboven terugnemen en aan elke spleet een detector plaatsen om te zien langswaar het deeltje passeert, dan heeft dit als gevolg dat het interferentiepatroon verdwijnt. Een meer grafische beschrijving maar daarom niet meer begrijpbare uitleg kan je vinden in de kat van Schrödinger.
Dan rest er ons nog een laatste ingrediënt: entanglement of verstrengeling. Je kan deeltjes of quantum systemen met elkaar verstrengelen zodat hun toestanden sterk van elkaar afhangen. Dit gaat zo ver dat als je het ene systeem meet, je de toestand van het andere systeem ook bepaalt en dit onafhankelijk van de afstand tussen beide systemen. Dit is wat Einstein ‘spooky action at a distance’ heette.
Ik hoor jullie al zeggen “wat heeft dit nu nu allemaal te maken met computerwetenschap?”. Dat kom je te weten in de volgende paragraaf. Onthou vooral drie zaken:
- een deeltje of systeem bevindt zich in een combinatie van verschillende toestanden (superpositie)
- van zodra je meet, komt het systeem terecht in één specifieke toestand
- je kan systemen met elkaar verstrengelen zodat de toestand van het ene helemaal bepaald wordt door de andere (entanglement)
Quantum computing
Allereerst kan je in de huidige wereld niet omheen dat allerlei electronica kleiner en kleiner wordt en dus te maken heeft met quantum-effecten. Deze kunnen zowel voor problemen zorgen maar in sommige gevallen kan je echter gebruik maken van die speciale eigenschappen om heel kleine structuren te bouwen. Daar gaan we het hier niet over hebben.
In klassieke computers werken we met bits die een toestand 0 of 1 hebben. Het equivalent in de quantum wereld noemt met een qubit (quantum bit). Zoals hierboven besproken bevindt deze qubit zich niet in de toestand 0 of 1 maar in een combinatie van beide, tot we de toestand proberen te meten. Als we een systeem zouden bouwen met een aantal qubits dan kunnen we de toestand van het totale systeem beschrijven aan de hand van de combinaties van de onderlinge toestanden van de qubits. Een systeem van 2 qubits kan je beschrijven als een combinatie van 2×2 toestanden, een systeem van 3 qubits aan de hand van 2³=2x2x2=8 toestanden en zo verder. Moest je er in slagen een 300 qubits systeem te bouwen heb je dus een mengvorm van 2300 toestanden wat een aantal is dat groter is dan het aantal deeltjes in het universum. Verwar dit niet met een klassiek systeem met 300 bits waarin je een getal van de grootte 2300 kan opslaan. Een quantumsysteem van 300 qubits bevat alle 2300 getallen (toestanden) tegelijk.
Het lijkt er dus op dat het veel krachtiger is dan een klassieke 0/1 bit systeem van de computers zoals we ze kennen. Je zou denken dat het systeem de oplossingruimte voor een probleem veel sneller zou kunnen doorzoeken dan bij een klassiek computer. Er is echter een obstakel: als je het systeem meet krijg je een specifieke (willekeurige) toestand die niet noodzakelijk de toestand (of oplossing) is die je zoekt. Het zal er dus op aankomen om het systeem zo te beïnvloeden dat je zonder het te meten, het toch in de richting van de oplossing stuurt. Deze hulp komt uit de hoek van de superpositie. We kunnen de toestanden van de verschillende qubits met elkaar laten interfereren zodat de toestanden die niet overeenstemmen met de gezochte oplossing elkaar opheffen. Als we dan meten dan krijgen we een resultaat dat ons dichter bij de oplossing brengt.
In Quantum computing zijn er een aantal algoritmen ontwikkeld die bepaalde sets van problemen sneller kunnen oplossen dan op een klassieke manier. Eerst iets meer over klassieke computersystemen. Men spreekt over efficiënte algoritmen om problemen op te lossen als dit kan in een “polynomiale tijd”. Een mooi voorbeeld van polynomiale tijd is het vermenigvuldigen zoals we dit op school hebben geleerd maar dan toegepast op binaire getallen. Als je twee binaire getallen, elk van lengte n met elkaar vermenigvuldigt dan zijn het aantal stappen die je nodig hebt van de orde n². Als n=10 dan komt dit op een 100-tal stappen. Daarnaast heb je problemen zoals het factoriseren van een getal in priemgetallen, namelijk een getal opsplitsen in het product van enkel priemgetallen, zoals 15=3×5. Daarvoor heb je met klassieke algoritmen een “super-polynomiale tijd” nodig. Het aantal stappen stijgt (quasi) exponentieel met de lengte van het getal. Dat betekent voor een getal van 10 bits dat je eerder 2n stappen zal nodig hebben, of 1024 stappen. Deze priemfactorisatie is iets wat de basis vormt van private/publieke sleutel cryptografie, zoals bijvoorbeeld in het RSA-algoritme. Dit vind je terug in alledaagse cryptografische bescherming zoals SSL dat bij https wordt gebruikt. Je kan de sleutel enkel breken door een factorisatie uit te voeren. Gezien we al snel spreken van sleutellengtes groter dan 1024 bits, begrijp je dat de tijd die je nodig hebt om die factorisatie uit te voeren evenredig is met het doorlopen van de 21024 stappen, wat heel lang zou duren. Ter informatie, het factoriseren van een 768-bits getal werd in 2009 uitgevoerd in een effort van 2.5 jaar met honderden machines.
Quantum computing verandert de balans echter. Shor heeft in 1994 een quantumalgoritme uitgewerkt dat het factoriseren van getallen terugbrengt tot een probleem dat in polynomiale tijd kan berekend worden. Dat maakt het dus vrij eenvoudig om snel een dergelijk cryptografisch systeem te breken. Er is intussen al sprake van “post-quantum” crypto algoritmen die op andere technieken gebaseerd zijn.
Een ander bekend quantum algoritme is dat van Grover. Dit laat toe om heel snel een ongesorteerde database te doorzoeken. In tegenstelling tot de klassieke manier waar je alle elementen één per één zou moeten doorlopen en gemiddeld n/2 pogingen zou nodig hebben, wordt dit mogelijk in √n stappen.. Wat voor systemen met veel elementen (bijvoorbeeld 1.000.000) een veel snellere manier wordt, namelijk 1000 in plaats van 500.000 stappen.
Maar kan een quantum computer dan alle problemen in polynomiale tijd oplossen? Neen, jammer genoeg niet. Er zijn nog veel types van computationele problemen die zelfs met een quantum computer momenteel niet veel sneller kunnen opgelost worden dan met een klassieke computer. Een voorbeeld is dat van het inkleuren van een kaart met 3 of 4 kleuren waarbij aangrenzende landen niet dezelfde kleur mogen hebben. Quantum computers kunnen echter ingezet worden om heel wat problemen te modelleren en op te lossen zoals het simuleren van quantumfysica zelf. Dat kan leiden tot betere inzichten in domeinen zoals chemie en nanotechnologie.
In een volgende post gaan we kijken wanneer we een quantumcomputer in de Aldi kunnen gaan kopen en nog een andere toepassing van quantummechanica, namelijk quantumcryptografie.
Leave a Reply