Kwantumcomputer

Geschiedenis

Coming soon...

Kwantumbits

De klassieke digitale informatiewereld draait om bits. Een bit is de eenvoudigste eenheid van informatie, meestal aangeduid als 0 of 1. Hij is altijd all��n 0 of all��n 1. Dat is in ieder geval duidelijk. die duidelijkheid ontbreekt in de kwantumwereld. Neem de spin van een elektron, een eigenschap van het deeltje naast massa en elektrische lading. De spin van het deeltje is de interne rotatie om zijn eigen as, zoiets als het rondtollen van een tennisbal. Ook sommige atoomkernen hebben een spin. De rotatie van het deeltje kan links- of rechtsom zijn. Daarom kan zo'n spin dienst doen als kwantumbit, de eenvoudigste eenheid van kwantuminformatie. Bij een rotatie linksom kennen we een 0 aan de spintoestand toe. En 1 hebben niet betrekking op de grootte van de spin, die voor elk deeltje precies is bepaald, maar zijn toegekend naar analogie van de twee toestanden van een klassiek bit.

Superpositie

Het bijzondere van de kwantummechanica is dat deze het tevens toestaat dat een spin zich in een superpositie bevindt van 0 �n 1. Je kunt zeggen dat de spin tegelijkertijd 0 �n 1 is, tegelijkertijd omhoog en omlaag staat. In een superpositietoestand is er een kans ? dat de spin bij meting 0 blijkt te zijn en een kans (1-?) dat die spin bij meting 1 is. Voordat je kijkt, bevindt de spin zich in zo'n superpositie. Zodra je echter kijkt welke waarde de spin heeft, meet je ofwel een 1 ofwel een 0, net als bij een klassiek bit. Na de meting keert de superpositie niet vanzelf terug. De vraag naar het waar�m van dit intu�tief bizarre gedrag is zinloos. Feit is dat de kwantummechanische wereld zo in elkaar blijkt te zitten. Dan kan de fysicus niets anders dan toegeven.

Het is precies dit fundamentele, ingebakken waarschijnlijkheidskarakter van de kwantumwereld dat ongekende rekenmogelijkheden biedt. Vervang N klassieke bits maar eens door N kwantumbits, waarbij een kwantumbit bijvoorbeeld een spintoestand is of de polarisatie van een lichtdeeltje (foton). N klassieke bits kunnen 2^N toestanden voorstellen, alleen niet tegelijkertijd. Twee bits kunnen dan vier combinaties vormen: 00, 01, 10 en 11. Met twee kwantumbits ziet de informatiewereld er heel anders uit. Omdat een kwantumbit zich in een superpositie van 0 en 1 kan bevinden, kunnen twee kwantumbits zich in een superpositie van 00, 01, 10 en 11 bevinden: vier toestanden tegelijkertijd in twee kwantumbits. N kwantumbits representeren dus 2^N toestanden tegelijkertijd. Een kwantumcomputer met N kwantumbits kan daarom 2^N berekeningen tegelijkertijd uitvoeren. In plaats van het een voor een optellen van getallen, kan een kwantumcomputer bijvoorbeeld alle getallen tegelijkertijd bij elkaar optellen. Een soort natuurlijke paralelle computer. In theorie althans, want op alle fronten liggen er nog obstakels. De belangrijkste onderzoeksvragen zijn allereerst �f je een kwantumcomputer kunt bouwen, en zo ja met hoeveel kwantumbits en met welke precisie. En vervolgens, als je zo'n apparaat hebt, wat kun je er mee doen.

De kwantumcomputer

Het factoristatieprobleem

Van een aantal belangrijke problemen is al een decennium bekend dat een kwantumcomputer ze veel sneller kan oplossen dan elke denkbare klassieke computer. Het belangrijkste probleem is het factorisatieprobleem: hoe ontbind je een getal in zijn priemdelers, precies die delers die priemgetallen zijn. Voor kleine getallen is dat makkelijk te zien. Zo is 15 gelijk aan 3 X 5 en 30 gelijk aan 2 X 3 X 5. Maar hoe groter het getal, hoe moeilijker het wordt om de priemdelers te vinden. De oplossingstijd neemt bij alle bekende factorisatiemethoden exponentieel toe met het aantal cijfers. Dat is nauwelijks sneller dan de meest eenvoudige aanpak: gewoon probere welke priemdelers werken. De allersnelste computers doen er tegenwoordig vier maanden over om een getal van ongeveer 130 cijfers te factoriseren. Maak je het getal nog tweemaal zo lang, dan is er geen computer die de opslossing binnen een menselijke tijdschaal kan vinden. Digitale beveiliging is hierop gebaseerd. Als het maar lang genoeg is, is er geen klassieke computer die de priemdelers kan vinden.

Aan die schijnbare zekerheid kan een kwantumcomputer een einde maken, in theorie althans. Peter Shor bedacht in 1994 een superslimme rekenmethode waarmee een toekomstige kwantumcomputer het factorisatieprobleem wezenlijk veel sneller kan oplossen. Shors rekenmethode laat een kwantumcomputer veel meer tegelijkertijd rekenen. Met zijn algoritme toegepast op een kwantumcomputer raken de huidige digitale beveiligingen zo lek als een zeef. Alleen bestaat er nog geen kwantumcomputer. Overigens bestaan er inmiddels ook al absoluut onkraakbare kwantumbeveiligingen die een nieuw ondoordringbaar beveilgingspantser kunnen opwerpen. Om een getal van tweehonderd cijfers te factoriseren met het Shor-algoritme - geheel ondoenlijk voor de huidige computers - zou een kwantumcomputer 3500 perfecte kwantumbits nodig hebben. Maar net zoals een cd-speler een correctiemethode heeft voor bits die per ongeluk een verkeerde waarde hebben gekregen, zo zal de toekomstige kwantumcomputer een kwantumcorrectiemethode bevatten. In plaats van 3500 perfecte kwantumbits zijn dan in de orde van honderduizend kwantumbits nodig om een getal van tweehonderd cijfers te factoriseren. Een factorisatie die een klassieke computer in duizenden jaren klaart, lost een kwantumcomputer binnen enkele seconden op. Dat is een revolutionaire tijdwinst.

Het zoekprobleem

Een tweede belangrijk probleem dat een kwantumcomputer veel sneller kan oplossen heeft te maken met het zoeken in grote gegevensbestanden. Stel dat je een specifiek gegeven zoekt in een ongeordend bestand van N gegevens. In de klassieke wereld bestaat er geen handigere methode dan een voor een alle gegevens doorlopen. Gemiddeld gesproken vind je dat bestand dan in N/2 stappen. De kwantumwereld staat het daarentegen toe dat een kwantumcomputer - dankzij kwantumsuperposities - alle gegevens tegelijkertijd doorzoekt. Lov Grover bedacht in 1996 een rekenmethode waarbij de tijdswinst kwadratisch is in het aantal gegevens. In plaats van in N/2 stappen duikt het gezochte bestand al op na √N zoekstappen. Waar een hedendaagse supercomputer een maand nodig zou hebben om een bepaald telefoonnummer te vinden in een gegevensbestand van alle telefoonnummers ter wereld, zou een kwantumcomputer er minder dan een half uur over doen. weliswaar bevindt een kwantumsysteem van N kwantumbits zich tegelijkertijd in 2^N toestanden, maar zodra iemand gaat meten, blijft er maar ��n uitkomst over. De grote truc is dan om te zorgen dat die ene uitkomst precies de gewenste uitkomst is. We moeten daarom een zodanig kwantum-algoritme ontwerpen dat de gewenste berekeningen elkaar versterken en de ongewenste berekeningen elkaar uitdoven. Als je uiteindelijk gaat meten aan het systeem, dan moet de kwantumbits precies het juiste antwoord geven.

Het uitdoven en versterken van berekeningen is gebaseerd op het kwantummechanische principe van interferentie. Naast superpositie is interferentie een tweede belangrijke eigenschap van een kwantumcomputer die fundamenteel verschilt van de klassieke computer. Een kwantummechanische toestand valt als een golffunctie voor te stellen. Overlappende golffuncties kunnen elkaar op sommige punten versterken en op andere punten juist verzwakken, zoals licht- of geluidsgolven elkaar kunnen versterken of verzwakken als ze elkaar overlappen. Het kwantumalgoritme regelt dat versterken en verzwakken van alle kwantumbits.

Verstrengeling

Het derde fundamentele nieuwe van een kwantumcomputer is verstrengeling. Bij twee klassieke bits heeft de inhoud van het ene bit geen invloed op de inhoud van het andere bit. Kwantumbits kunnen daarentegen verstrengeld zijn. Fysici krijgen dat voor elkaar door een uitwendige kracht aan te brengen op de kwantumbits. Twee kwantumbits zijn dan bijvoorbeeld samen voor dertig procent gelijk aan de toestand 00 en voor zeventig procent gelijk aan 11. Als bij meting het eerste kwantumbit 0 is, dan is automatisch het tweede kwantumbit een 0. Maar als het eerste kwantumbit 1 oplevert, dan is het tweede kwantumbit ook een 1. Hoe ver de kwantumbits ook van elkaar worden verwijderd, de informatie tussen de kwantumbits is automatisch en onverbreekbaar gekoppeld, iets wat bij zomaar een willekeurige superpositie niet het geval hoeft te zijn. Absurd, maar waar.

Naast het factorisatieprobleem en het zoekprobleem, wat in essentie mathematische problemen zijn, zou de kwantumcomputer ook een belangrijke rol spelen bij het simuleren van een ander kwantummechanisch probleem. Een klassieke computer heeft nu al moeite om een systeem van tien kwantumobjecten te simuleren. Hij heeft echter geen schijn van kans om ooit het gedrag van honderd van die kwantumobjecten door te rekenen. Er zijn te veel superposities mogelijk. In principe kan een kwantumcomputer met enkele tientallen kwantumbits w�l al een eenvoudig kwantumsysteem simuleren. Hoe en wat precies, moeten we echter nog ontdekken.

Kortom, voor de wiskundige problemen is een kwantumcomputer van honderd kwantumbits niet interessant, maar voor het nabootsen van de fysica van een kwantumsysteem kan dezelfde kwantumcomputer wel degelijk interessant zijn.

Een van de grote praktische problemen bij het bouwen van een kwantumcomputer is dan een systeem van kwantumbits enerzijds toegankelijk moet zijn om er concrete berekeningen mee uit te voeren, maar anderzijds zo goed van de buitenwereld afgesloten moet zijn dat de kwantumtoestanden niet vervallen, want dan wordt de hele berekening waardeloos. Als we niet meten aan het kwantumsysteem, mag er helemaal geen decoherentie zijn. En als we wel meten, moet er zo min mogelijk decoherentie optreden. Decoherentie is het weglekken van kwantuminformatie naar de omgeving. Eigenlijk is dit het resultaat van een natuurlijke verstrengeling tussen het kwantumsysteem en zijn omgeving.