Quantum Computing uitgelegd

Door Marco Dufour

Het begin van Quantum computing

In 1981 werd voor het eerst de term quantumcomputer genoemd door de Amerikaanse natuurkundige Richard Feynman. Het woord “quantum” (Latijns woord voor “hoeveelheid”) komt uit de quantummechanica. In deze tak van de natuurwetenschappen houdt men zich bezig met de studie naar het gedrag van atomaire en subatomaire deeltjes. Een gewone computer kan met twee bits informatie opslaan in vier mogelijke combinaties: 00, 01, 10 en 11. Een quantumcomputer kan al deze combinaties tegelijk aannemen. Wanneer je bijvoorbeeld 32 bitjes neemt, dan heb je het over 4,3 miljard mogelijkheden. Een “ouderwetse” computer kan maar één combinatie tegelijk aannemen. Een quantumcomputer kan al deze combinaties tegelijk innemen en daarmee een paar miljard keer sneller rekenen dan de klassieke computer. Dit wordt ook wel quantum parallel processing genoemd. In theorie zou een quantum computer dus 2n sneller zijn dan jouw computer thuis! In de praktijk ligt het iets gecompliceerder. Na 2n berekeningen krijg je maar één uitkomst en je weet niet eens waarvan dit de uitkomst is. Gelukkig zijn er allerlei trucs bedacht om toch met één bewerking alle uitkomsten van alle bewerkingen te achterhalen.

De eerste quantumcomputer (met twee qubits) zag in 1998 het levenslicht bij de Universiteit van Californië in Berkeley. Nou moet je niet denken dat dit gelijk een praktisch inzetbare computer is, want zelfs tot op de dag van vandaag hebben de bestaande quantumcomputers nagenoeg enkel academische waarde. Eind 2021 maakte IBM bekend dat het zijn tot nu toe grootste “superconducting quantum computer” heeft gebouwd. Deze bestaat uit 127 qubits, wat meer dan twee keer zoveel is als de computers die Google en de University of Science and Technology in China hebben gemaakt. Bedenk hierbij dat iedere qubit extra de theoretische verwerkingssnelheid van een quantumcomputer verdubbelt!

Factoriseren

Eén ding waar een quantum computer goed in is, is factoriseren. Hierbij ga je bijvoorbeeld proberen de volgende formule op te lossen: x * y = 53293

Het antwoord blijkt te zijn: 137 * 389. Dit zijn trouwens twee priemgetallen… (een priemgetal is alleen deelbaar door 1 en zichzelf). Er is in de traditionele computerwereld geen enkele manier gevonden om dit op een eenvoudige manier uit te rekenen. Het enige wat je kunt doen is iedere mogelijke waarde uit te proberen. Echter… Peter Shor heeft een algoritme bedacht waardoor de quantum computer dit nou juist wél sneller kan!!! Peter Shor’s algorithm.

Qubits

Een quantum computer gebruikt qubits. Wat is een qubit? Nou, dat kan alles zijn dat 2 staten tegelijk heeft. Je kunt hier bijvoorbeeld elektronen voor gebruiken. Een elektron is een geladen deeltje met een spin. Door deze draaiing creëert het elektron een soort van noord- en zuidpool. Wanneer je zo’n elektron in een magnetisch veld plaatst, dan kun je deze spin manipuleren om zich omhoog (noord) of omlaag (zuid) te richten. Dit zou je kunnen zien als de status 1 of 0 die je bij de klassieke bit ook kent. De qubit kan in meerdere toestanden tegelijk verkeren; dit noem je superpositie. Verder beïnvloedt de status van elk deeltje dat van een ander, wat verstrengeling (entanglement) wordt genoemd. Met deze eigenschappen is het mogelijk om sommige berekeningen exponentieel sneller te laten verlopen.

Dan wil je ook nog “goede” qubits hebben. Om hieraan te voldoen moeten ze onder andere uniform zijn, controleerbaar en betrouwbaar. Het voordeel van uniforme qubits is dat ze dan eenvoudigere structuren toelaten. Anders heb je qubits die ieder zijn/haar 😉 eigen persoonlijkheid heeft en heb je per qubit veel fysieke connecties nodig om al deze persoonlijkheden te controleren. Betrouwbaarheid druk je uit in coherentietijd. Na verloop van tijd verliezen qubits hun waarde. Als deze eerst de waarde “1” had, dan vervalt die in een onbekende (en dus nutteloze) toestand. Hoe langer een qubit goed functioneert, des te meer berekeningen kun je ermee uitvoeren voordat de qubit moet worden gereset.

Quantum decoherence

Helaas zijn de qubits zeer gevoelig voor omgevingsinvloeden. Wanneer je de staat van een qubit meet, dan ga je met een meetinstrument kijken naar de waarde van de qubit. Hierbij verliest deze de superpositie. Echter, wanneer de qubit door iets anders beïnvloed wordt (externe invloeden of zelfs binnen de quantum computer), dan kan het ook al die superpositie verliezen! Dit noemen we “quantum decoherence”. Wanneer je de quantum omgeving perfect zou kunnen isoleren, dan heb je geen decoherence; echter, dan kun je ook geen metingen meer uitvoeren. Er zijn zelfs mensen die voorspellen dat er helemaal geen stabiele quantum computer kan worden gebouwd, vanwege de altijd aanwezige decoherentie problematiek in de quantum computer.

De fysieke quantum computer

Vanwege het feit dat de qubits zo instabiel zijn, wordt de computer tot bijna het absolute nulpunt gekoeld. Dat is in de buurt van -273 graden Celsius. Hiervoor heb je cryogene units nodig en deze zijn groot. Naarmate er meer qubits in de supercomputer moeten worden geplaatst, krijg je ook een steeds grotere unit, van zo groot als een kamer naar zo groot als een voetbalveld, etc.

Peter Shor’s Algorithm

1994 - Peter Shor’s Algorithm

Wanneer je een computer iets laat uitrekenen, dan duurt dat een zekere tijd. Wanneer je de uit te rekenen informatie in blokjes op zou delen en kijkt hoe lang ieder blokje erover doet om uitgerekend te worden, dan kun je een voorspelling doen over de totale tijdsduur van de berekening, ook wanneer je de rekenopdracht uitbreidt met meer van die blokjes. Wanneer de tijdsverlenging lineair is, bijvoorbeeld bij een dubbel aantal blokjes wordt de rekentijd ook 2x langer, dan spreek je van een “lineair time algorithm”. Dit kun je als volgt noteren: O(n) waarbij n = het aantal te berekenen blokjes. Wanneer de tijdsduur kwadratisch toeneemt, spreek je van een “polynomial time algorithm”. Dit noteer je als volgt: O(nα) waarbij de constante α > 1.

Shor’s Algorithm is een quantum computer algorithm om “prime factors” van een integer (heel getal) te vinden.Bij diverse encryptie standaarden worden speciale berekeningen gemaakt die ervoor zorgen dat de door deze encryptie versleutelde informatie moeilijk te kraken is. Een voorbeeld hiervan is RSA. Bij RSA maak je gebruik van twee bij elkaar horende sleutels. De ene sleutel kan data versleutelen, waarbij alleen de andere bijbehorende sleutel die data weer kan ontsleutelen. We noemen deze sleutels de public key en de private key. Deze manier van encryptie noem je ook wel asymmetrische encryptie, omdat je niet (zoals bij symmetrische encryptie) dezelfde sleutel gebruikt bij het versleutelen en ontsleutelen. Bij het genereren van de public en private keys worden twee grote priemgetallen p en q met elkaar vermenigvuldigd. Het blijkt namelijk heel lastig om uit het product van twee grote priemgetallen de oorspronkelijke twee priemgetallen terug te rekenen. Met Shor’s algorithm blijkt dat een quantum computer met voldoende qubits dit binnen een redelijke tijd voor elkaar kan krijgen.

Om een bepaald getal N te factoriseren in zijn twee “prime factors”, werkt Shor’s algorithm in polynomial time, dus de tijd die het kost is polynomiaal in log N, met de grootte van het getal als input. Zoals in de klassieke computers bestaan er in de quantum computers ook logic gates (denk hierbij aan de AND, OR, XOR, NOT operators; je kunt deze ook zien als true/false checks, dus boolean operations). Een logic gate dient bij quantum computers “reversible” te zijn. Dat houdt in dat je op basis van het antwoord (output) terug kunt rekenen naar de input. Er is bewezen dat ook quantum computers reversible logic gates kunnen hebben (quantum gates) die alle boolean operations kunnen uitvoeren. Shor’s algorithm heeft quantum gates nodig in de orde van O((log N)2(log log N)(log log log N)) met gebruikmaking van “fast multiplication” (een algoritme waarmee je sneller kunt vermenigvuldigen dan domweg bijvoorbeeld “x” keer een waarde bij “y” op te tellen)

Shor’s algorithm kan met een zekerheid van 2/3 en binnen polynomiale tijd de berekening uitvoeren.Dit zorgt ervoor dat het algoritme voldoet aan de complexity class BQP (Bounded-error Quantum Polynomial time). Hierbij mag er een error rate van hooguit 1/3 zijn en binnen polynomiale tijd uit te rekenen. Shor’s algorithm past binnen deze eisen.

QKD / Quantum Computing

Wanneer het ons lukt om echt werkende quantum computers te bouwen dan zijn alle huidige asymmetrische encryptiealgoritmes snel te kraken (en niet de huidige die enkel academische waarde hebben omdat ze maar enkele tientallen microseconden stabiel zijn; de 50 qubit computer van IBM “maar liefst” 90 microseconden, dat is 0,000090 seconden). Daarom moeten we nú al denken aan het post-quantumcomputing tijdperk. Hoe ga je de huidige data versleutelen? Hoe ga je de beveiligde verbindingen verbeteren om veilige communicatie mogelijk te houden? Hiervoor zijn er twee richtingen: QKD en Quantum Computing. De ene sluit de andere trouwens niet uit; ze kunnen prima allebei hun geschikte toepassingen vinden.

Bij QKD (Quantum Key Distribution) ga je op basis van de quantum mechanica veilige verbindingen opbouwen. Hier heb je echter gespecialiseerde apparatuur voor nodig en dat zal absoluut niet goedkoop zijn! Dit systeem garandeert “full secrecy” maar tegen een “high cost”. Iedere poging om het verkeer tussen twee partijen af te luisteren zal DIRECT opgemerkt worden. Deze technologie kan interessant zijn voor overheden, defensie en financiële instellingen waar de kosten ondergeschikt zijn aan de vertrouwelijkheid.

Met Quantum Computing (PQC; Post Quantum Cryptography) komen post quantum encryptiealgoritmes beschikbaar voor de gewone man. Op dit moment is er een proces geïnitieerd door NIST (https://csrc.nist.gov/Projects/post-quantum-cryptography )waarbij kandidaten worden geëvalueerd en gestandaardiseerd. Op dit moment (2022) zit het proces in ronde 3.

Tot slot

Praktisch inzetbare quantum computers zijn er nog niet, maar de toekomst staat volledig open. Zorg ervoor dat jouw organisatie nu al nadenkt over jullie beveiliging en hoe je jouw data veilig houdt zodra deze rekenmonsters echt inzetbaar zijn.

2 jaren geleden