|
Projektarbete, 1.5 p, på kursen Modern fysik, 5 p, vt 2002, vid Malmö högskola. Location: http://www.df.lth.se.orbin.se/~mikaelb/modfys/kvantdatorer.html Datum: 3/6 2002 |
Det utmärkande för kvantdatorer är att kvantmekaniskt kopplad hårdvara räknar ut samtliga lösningsförslag samtidigt. Detta är inte samma sak som en klassisk parallell dator, för den använder hårdvara som inte är kvantmekaniskt kopplad för att lösa de olika delproblemen. En kvantdator är heller inte en klassisk analog dator, ej heller normalt en klassisk dator försedd med en äkta slumpgenerator. Däremot är det så att klassiska parallella datorer används för att simulera kvantdatorer, och de klassiska datorerna med slumpgenerator kommer för vissa problem upp i samma hastighet som de egentliga kvantdatorerna.
För att förstå hur en kvantdator kan utföra beräkningar tänk dig att du vill få ett antal slumptal med samma sannolikhetsfördelning som resultatet av ett dubbelspaltförsök. Systemet med ljus, spalter och skärm är kvantmekaniskt kopplade. Det är möjligt att skriva ett datorprogram som beräknar ett slumptal med en sådan fördelning, men detta är en tidsödande beräkning som kräver ett antal loopar. I stället skulle du kunna utföra experimentet och på kort tid få många slumptal med den önskade fördelningen. Då har du använt en kvantdator. Nu utgör dubbelspaltförsöket inte lösningen på något vanligt mänskligt problem, men det finns sätt att sätta upp och använda kvantmekaniska system så att de löser viktiga problem.
Kvantdatorer kan t ex utföra faktorisering av heltal och sökuppgifter betydligt snabbare än dagens klassiska digitala datorer, oavsett vilken arkitektur dessa klassiska datorer har.
En traditionell klassisk dator använder bits (binary digit) som kan vara antingen 0 eller 1, t ex ett 4-bit register kan innehålla något av talen 0 till 15, men endast ett tal åt gången. Ett register i en kvantdator på 4 qubit (quantum bit) kan däremot innehålla talen 0 till 15, samtidigt!
Snabbheten hos kvantdatorn jämfört med den klassiska kan leda till en kvalitativ skillnad. Om en viss beräkningstid varierar med datastorleken som n*n på en digital dator, respektive log n på en kvantdator, så kan det innebära en kvalitativ skillnad om beräkningsenheten har ändlig livslängd, t ex 100 år. För tillräckligt stora datamängder kommer kvantdatorn alltid att vara snabbare än en klassisk dator.
Dagens kvantdatorer måste närmast beskrivas som en klassisk dator försedd med matteprocessor av kvantmekanisk typ. Det är fortfarande den klassiska datorn som kör programmet, men vissa beräkningar snabbas upp av kvantkomponenter.
Det finns åtminstone tre teknologier för att realisera kvantdatorer:
Det finns ett känt kryptosystem kallat RSA som används vid t ex säker dataöverföring på Internet. T ex använder de flesta av Internetbankerna detta (märks på att adressraden i webbläsaren börjar med https i stället för http). Detta krypto fungerar så att vissa heltal (n och e) skickas över publikt till användarens webbläsare, samtidigt som vissa heltal hålls hemliga (p, q och d). Nu är det så att n=p*q, där p och q är stora primtal. I princip kan man faktorisera alla tal, men även med dagens snabbaste superdatorer skulle det ta månader eller år. Med kvantdatorer förändras detta.
Shors algoritm används för att finna ett heltals faktorer. Den använder två stycken kvantmekaniska register som dock utgör ett kvantmekaniskt system. Den kvantmekaniska kärnan i Shors algoritm är att man laddar det ena registret med tillstånd motsvarande alla heltal som registret kan representera. Alla heltalstillstånden har samma sannolikhet. Det andra registret laddas med enbart tillståndet 0. Man utför operationen xa mod n (resten vid heltalsdivision), där a är tillstånden i första registret, och divisionsresten sparas i det andra registret. Denna operation utnyttjar alltså kvantparallellitet. Andra registret mäts. Detta leder till att vågfunktionen kollapsar så att första registret är konsistent med mätresultatet av det andra, eftersom registren är delar av samma kvantmekaniska system. Sedan gör man en diskret fouriertransform av det första registret, dvs man tar reda på de rumsliga perioderna hos registet. Även denna operation är kvantmekanisk. Sedan mäter man det första registret, och då får man sannolikt perioden hos första registret. Denna använder man för att snabbt räkna ut en faktor (Hayward).
För att förstå Shors algoritm till fullo måste man bl a kunna kongruensräkning (även kallad restklassaritmetik) och den diskreta fouriertransformen, förutom linjär algebra och räkning med komplexa tal.
Grovers algoritm används för att söka efter ett element i en osorterad lista. Först flyttas data in i registret från omvärlden så att tillståndet (elementet) man letar efter fortfarande är märkt. Sedan utför man en kvantparallell operation på registret så att det märkta tillståndet negeras. Sedan utför man en kvantoperation som förstärker sannolikheten hos det negerade tillståndet. Sedan mäter man och kollapsar vågfunktionen, resultatet är indexet på det element man letade efter.
Det finns ännu ingen hårdvara som realiserar Grovers algoritm, men det är bevisat att samtliga operationer är fysikaliskt möjliga (Hayward).
Ett stort problem med kvantdatorer är att vågfunktionen kollapsar vid andra tillfällen än de avsedda p g a yttre störningar (Lotsson). Man håller på att utveckla felrättande system för kvantdatorer som skall kunna kompensera detta (IBM). I vilket fall utnyttjar kvantdatorerna slumpeffekter som ibland inte ger det önskade resultatet. Det finns också problem med bristande kunskap om t ex exakt hur kollapsen av vågfunktionen går till och det finns olika teorier på detta område, bl a involverar vissa gravitationen (Talk America). Gravitationen är en speciell kraft eftersom den kröker rummet.
Vi har alltså just börjat konstruera artificiella kvantdatorer, men det kanske redan finns naturliga: våra egna hjärnor.
Argument för att hjärnan är en kvantdator:
Argument mot att hjärnan är en kvantdator:
Argument mot några av motargumenten:
Singularitet är namnet på ett framtidsscenario som
innebär att utvecklingen går mot maskiner med högre
intelligens än människan, och när dessa har
konstruerats så kommer de oundvikligen att ta över.
När de artificiella kvantdatorerna blivit fullfjädrade
kommer de att ersätta människans roll som den ledande
varelsen på jorden. Detta kommer troligen, men inte
säkert, att vara negativt för mänskligheten. Ordet
singularitet
Framtidens kvantdatorer kommer kanske att vara kvantdator helt igenom och inte någon hjälpprocessor till en klassisk dator: Vågfunktionen utvecklas i dess material och den kollapsar p g a indata och utvecklingen av den nya vågfunktionen fortsätter och den kollapsar och så vidare.
Om människans hjärna inte är en kvantdator skulle singulariteten inträffa tidigare eftersom utvecklingen av de klassiska datorerna håller på att nå sin fulländning, sedan skulle bara lite kodningsarbete återstå. Är människans hjärna en kvantdator dröjer det kanske 300 år innan singulariteten inträffar, eftersom en hel del problem rörande vågfunktionens kollaps först måste lösas.
En ekonomisk drivkraft till hjärncellsforskningen, som kan utröna om hjärnan är en kvantdator eller inte, kan vara att man vill kunna bota sjukdomen Alzheimer (Talk America).
Eftersom den kvantmekaniska faktoriseringsalgoritmen kan användas för att knäcka det mycket kommersiellt använda RSA-kryptot, så har insatserna på kvantdatorområdet blivit mycket intensiva. Den som först får fram en fungerande kvantdator har onekligen ett försprång. Denna kapplöpning är något som påskyndar singulariteten.
Jag vill passa på att tacka alla debattörer på DF:s aktiva-lista som i februari 2002 diskuterade kvantdatorer och singularitet. Jag vill även tacka Anna Tollstén som höll kursen Modern fysik.