Cookies op Tweakers

Tweakers is onderdeel van DPG Media en maakt gebruik van cookies, JavaScript en vergelijkbare technologie om je onder andere een optimale gebruikerservaring te bieden. Ook kan Tweakers hierdoor het gedrag van bezoekers vastleggen en analyseren. Door gebruik te maken van deze website, of door op 'Cookies accepteren' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt? Bekijk dan ons cookiebeleid.

Meer informatie

Door Aad Offerman

Freelancer

Kwantumcomputers komen eraan

Op de kleinste deeltjes kun je rekenen

Modellering en berekenbaarheid

Modellering

Er zijn diverse manieren om kwantumbewerkingen te modelleren. De analytisch-wiskundige theorie is gebaseerd op de eerder beschreven golffuncties: lineaire combinaties van basiswaarden (notatie: |0> en |1>), met complexe coëfficiënten, de amplitudes. Bloch sphere - Credits SmiteMeister and Wikipedia

De bol van Bloch vormt dan een meetkundige representatie van een enkele qubit. Aan de bovenkant en onderkant zijn respectievelijk de waarden |0> en |1> weergegeven. Een superpositie is een punt ergens 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 superpositiepunt per se 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 is. In deze modellering bestaan (eenvoudige) kwantumbewerkingen uit meetkundige rotaties, verplaatsingen van het superpositiepunt over het boloppervak.

Voor techneuten is het natuurlijk veel handiger om over kwantumbewerkingen 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. Hieronder zie je bijvoorbeeld een 'Controlled NOT'-poort (CNOT). De negatieoperatie (|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 kwantumoperaties daadwerkelijk te kunnen uitvoeren, is ondersteuning van de volledige reeks 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 kwantumcomputer drie poorten voldoende.

Berekenbaarheid

Naar aanleiding van de honderdste geboortedag van Alan Turing publiceerden we medio 2012 al een uitgebreid verhaal over Turing-machines en de theorie van berekenbaarheid en complexiteit van problemen en algoritmen. Om op een vergelijkbare manier over de rekenkracht van kwantumcomputers te kunnen praten, heeft de natuurkundige David Deutsch de Quantum Turing Machine bedacht. Op vergelijkbare wijze is er een klasse van problemen gedefinieerd die met een kwantumcomputer in een redelijke tijd op te lossen zijn. Dat wil zeggen, in polynomiale tijd ten opzichte van de lengte van de input.

De figuur hiernaast laat zien hoe deze klasse BQP of 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 overigens voor de meeste relaties tussen de verschillende complexiteitsklassen geldt, lijkt het erop dat kwantumcomputers inderdaad problemen kunnen oplossen die we met de huidige deterministische computers, klasse P, niet aankunnen. Sterker nog, inmiddels zijn er al diverse kwantumalgoritmen bekend voor problemen waarvoor nog niemand een deterministisch algoritme heeft kunnen bedenken. Aan de andere kant heeft nog niemand een kwantumalgoritme 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 kwantumcomputers 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 interessantste kwantumalgoritmen die we nu kennen, is het algoritme van Shor, gebaseerd op kwantum-Fouriertransformaties. Daarmee kunnen de priemfactoren van een integer worden berekend. Deze factorisatie kan worden ingezet om een groot deel van de asymmetrische (public-key-) cryptografie die we nu op internet gebruiken, te kraken. Meest in het oog springend is de tls/ssl-beveiliging, die bij https en starttls wordt gebruikt. Hetzelfde geldt echter ook voor ssh en alle protocollen die via deze versleutelde verbindingen worden getunneld, en voor elektronische handtekeningen.

Zodra de eerste, echt bruikbare kwantumcomputer het licht ziet, zijn al deze beveiligingen in één klap waardeloos. De huidige public-key-technologie is namelijk gebaseerd op de moeilijkheid om het product van twee grote priemgetallen in zijn factoren te ontleden. Hoewel die kwantumcomputer nog niet bestaat, is het dus van cruciaal belang om nu al te werken aan de wiskundige theorie voor deze machines. Bijvoorbeeld om kwantum-proof algoritmen te vinden voor een nieuwe vorm van public-key-cryptografie, die wel bestand is tegen kwantumkrakers.

Verstrengeling

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

Wat vind je van dit artikel?

Geef je mening in het Geachte Redactie-forum.

Nintendo Switch (OLED model) Apple iPhone 13 LG G1 Google Pixel 6 Call of Duty: Vanguard Samsung Galaxy S21 5G Apple iPad Pro (2021) 11" Wi-Fi, 8GB ram Nintendo Switch Lite

Tweakers vormt samen met Hardware Info, AutoTrack, Gaspedaal.nl, Nationale Vacaturebank, Intermediair en Independer DPG Online Services B.V.
Alle rechten voorbehouden © 1998 - 2021 Hosting door True