HØit

Nr. 1-99

Kvantemaskinen

Åge Eide

Innledning

Datamaskinens utviklingshistorie henger nøye sammen med den teknologiske utviklingen, om hva som er fysisk realiserbart. Dagens datamaskin fungerer etter de samme prinsipper som den gjorde for 50 år siden. Den har likevel utviklet seg dramatisk i denne tiden, en utvikling som er nøye knyttet til den tilhørende utviklingen i fysikk og teknologi.

Bredde på en "ledning" i en integrert krets er ofte benyttet som et mål på hvor langt utviklingen i denne teknologien har kommet. I dag er denne "bredden" kommet ned i så små verdier at vi må kunne anta at den dagen hvor en logikk port i en datamaskin bare består av en håndfull atomer, ikke er så langt unna.

I denne atomære verdenen vil det være reglene fra kvantemekanikken som gjelder, regler som er ganske annerledes enn reglene som styrer dagens datamaskiner. Så dersom datamaskinene i fremtiden skal benytte stadig mindre transistorer, så må ny kvantemekanikkbasert teknologi erstatte eller supplere det som vi har benyttet oss av helt frem til i dag.

Et sentralt poeng ved overgang til kvantemekanikkbasert databehandling er at det her ikke bare dreier seg om nok en økning av transistor tettheten, og en ennå mer slagkraftig prosessor. Det gjelder riktignok også dette, men langt mer interessant er forhold som bringer nye prinsipper inn på arenaen. Det ene forholdet dreier seg om muligheten for å konstruere kvantemekanikkbasert datamaskin, en kvantemaskin. Det andre forholdet dreier seg om å utvikle kvantemekanikkbaserte algoritmer. Et tredje forhold dreier seg om kvantemekanikkbasert transport av informasjon.

I denne artikkelen vil vi ta opp et par sentrale forhold knyttet til kvantemekanikkbasert prosessering. Vi vil vise hvorledes de kvantemekaniske prinsippene direkte impliserer parallell prosessering. Vi vil omtale algoritmer som utnytter disse egenskapene. Vi vil også redegjøre for sentrale problemer som er knyttet til den fysiske realiseringen av denne typen maskiner - kanskje betegnet som kvantemaskiner.

Makro-verdenen og mikro-verdenen

I denne artikkelen benytter vi begrepet makro-verdenen for de forhold som vi noe løst kan betegne som "de som hører til vår hverdag", med andre ord de kjente og vanlige forholdene, og som vi stort sett kan observere, og forstå. De beskrives ved hjelp av Newtons og Maxwells ligninger.

Med mikro-verdenen forstår vi her de fenomenene som bare kan beskrives ved hjelp av kvantemekanikken. Det er ingen kjent grense mellom disse to verdenene, men for vårt formål er det tilstrekkelig at vi har den "atomære" verdenen i tankene, med små partikler, og små energi forskjeller.

Tilstand - et sentralt begrep

Når vi omtaler forhold fra vår makro-verden, så er det vanligvis små eller store system som vi refererer til. Det minste systemet vi omtaler i makro-verdenen er vanligvis en såkalt partikkel. Tilstanden til denne partikkelen er da fullstendig beskrevet ved en enkel vektor

w = (r , v)

hvor r refererer til posisjonen til partikkelen og v refererer til hastigheten av partikkelen.

I kvantemekanikken kan vi også uttrykke tilstanden til en partikkel ved en vektor, en tilstandsvektor. Vektor symbolet er litt annerledes:

|w>

Når vi skal oppgi tilstandsvektoren i mikro-verdenen, så går vi fram på det som kanskje kan oppfattes på en litt spesiell måte. Vi må vanligvis først avklare alle mulige "situasjoner" systemet/partikkelen kan befinne seg i. Snakker vi om lokalisering, må vi avklare hvilke lokaliseringer som er mulig. Snakker vi om energinivåer, så må vi skaffe oversikt over disse. Partikler kan ha noe vi kaller spinn, og i så fall må disse avklares.

Hvordan disse "avklaringene" foregår, skal vi ikke komme inn på. Derimot skal vi feste oppmerksomheten ved hvordan tilstandsvektoren settes opp etter at vi har avklart de mulige situasjonene, eller alternativene som man også kan kalle dem.

La oss anta at en partikkel, et elektron , bare har to mulige posisjoner hvor det kan befinne seg på, A eller B. La oss betegne tilstandsvektoren for at elektronet er i A for |A> og tilstandsvektoren for at det er i B for |B>. I følge kvantemekanikken er det da også andre mulige tilstander tilgjengelig for dette elektronet, nemlig

|w> = r |A> + s |B>

hvor r og s er komplekse tall.

Her er vi ved ett av de forholdene ved kvantemekanikken som gjør den så fremmed. Dette uttrykket forteller at på en eller annen merkelig måte så er elektronets tilstand gitt ved at det samtidig er i både tilstand |A> og tilstand |B>. Det er vel ikke mulig å forklare med ord og begrep fra makro-verdenen hva det "betyr" at elektronet kan være i en såkalt superposisjon av to tilstander samtidig, vektet med komplekse tall. Vi må bare akseptere at dette er den eneste måten vi kjenner til som gjør det mulig å beskrive denne virkeligheten som hører mikro-verdenen til. Vi må bare akseptere som et faktum at denne mikro-verdenen fremtrer på denne måten.

I dette eksemplet opererte vi med en superposisjon av bare to tilstandsvektorer. Det kan selvfølgelig være flere.

Tilstandsutvikling

I vår makro-verden vil begivenhetene, enten det er bevegelse av en enkelt partikkel, eller det er prosesseringen i en datamaskin, alle følge regler utgått fra Newton eller Maxwell sine ligninger. Hvordan er det med våre kvante mekaniske tilstander, for eksempel

|w> = r |A> + s |B>

hvordan vil de utvikle seg etter hvert som tiden går? Svaret er at disse tilstandene i mikro-verdenen utvikler seg etter en fullstendig presis matematisk beskrivelse, en beskrivelse som er fullstendig deterministisk. Schrødinger ligningen beskriver denne utviklingen som funksjon av tiden. Vi skal ikke gå inn på den her, men bare nevne at den er lineær. Dette betyr at dersom vi ved et tidspunkt har to tilstander |A> og |B>, vil Schrødinger ligningen fortelle at etter tiden t vil disse hver for seg ha utviklet seg til tilstandene |A’> og |B’> henholdsvis. I en slik situasjon har vi også at en hvilken som helst lineær superposisjon

r |A> + s |B>

vil utvikle seg til

r |A’> + s |B’>

i det samme tidsrom.

Bits og Qubits

Konvensjonelle datamaskiner opererer med to Boolske tilstander, 0 og 1, med en eller annen type transistor som den fysiske byggesteinen. Den digitale datamaskinen etablerer etter hvert prosesserings step, en presis og observerbar tilstand. I den digitale transmisjonen kopieres bits, fra sender til mottager , hvor to spenningsverdier vanligvis er de fysiske representantene for bitverdiene 0 og 1.

Den kvantemekaniske bit kalles qubit. Som for den digitale datamaskinen kan også en qubit ha flere mulige fysiske representasjoner, en partikkel med spin 1/2, polarisasjonen til et foton, en superposisjon av to energitilstander for et atom.

Den fysiske representasjonen for en qubit er med andre ord en enhet fra "mikro-verdenen", og den får derfor også egenskaper som gjelder der.

Som for en vanlig bit har en qubit to mulige tilstander, men i tillegg kan den være i disse to tilstandene samtidig, i tråd med hva vi har diskutert ovenfor. Tilstandsvektoren er en vektor i et todimensjonalt komplekst vektor rom, og med referanse til den klassiske bit kaller vi de orthonormale basisvektorene i dette rommet for |1> og |0>. En normalisert tilstandsvektor kan dermed skrives

|w> = r |0> + s |1> , | r |² + | s |² = 1

hvor r og s er komplekse tall.

En qubit kan altså representere to verdier samtidig. To qubits 4 verdier, og N qubits kan samtidig representere 2N verdier. Lagringsutsiktene fortoner seg med andre ord lyse!

Fra tilstand til observasjon

Så langt har vi bare diskutert det vi har kalt tilstanden til det kvantemekaniske systemet, for eksempel tilstanden til en qubit. Vi har videre nevnt at det eksisterer et matematisk apparat , Schrødinger ligningen, som beskriver utviklingen over tid. En slik utvikling kan for eksempel være prosessen fra input til output i en kvantemekanikkbasert logikkport, en prosessering med andre ord. En slik prosessering er en prosessering med tilstandsvektorer , gjerne gjennom mange kvantemekanikkbaserte logikk porter.

Nå har vi imidlertid ikke gått inn på hvordan vi skal kunne registrere eller lese ut resultatene etter en slik prosessering. Et atom er ikke direkte tilgjengelig for observasjon. Og det er her det dukker opp enda et uvant fenomen. Output fra de kvantemekanikkbaserte logikk portene eksisterer fortsatt i mikro-verdenen, som en tilstandsvektor. Mens vi som skal observere, samme hva slags hjelpe-instrument vi benytter, tilhører makro-verdenen. Og nå viser det seg at når makro-verdenen møter mikro-verdenen så skjer det noe dramatisk med tilstandsvektoren vår. Den oppfører seg nærmest som en såpeboble som brister. I det øyeblikk vi foretar observasjonen vil tilstandsvektoren, som kan være en superposisjon av mange tilstandsvektorer, kollapse på en slik måte at bare en av de mange tilstandsvektorene "overlever". Hvilken vektor som overlever er gitt som en sannsynlighet, gitt av de komplekse vektene. Så etter at en qubit er observert, eksisterer den ikke lenger i to tilstander samtidig, men bare i en av de to mulige. I uttrykket

|w> = r |0> + s |1> , | r |² + | s |² = 1

vil resultatet etter en observasjon være 0 med en sannsynlighet | r |² og 1 med en sannsynlighet gitt ved | s |².

I makro-verdenen er et systems tilstand, med sine observerbare verdier, sammenfallende med det man observerer. Det som tilstanden beskriver, er det som man observerer. I mikro-verdenen er det annerledes. Der må man skarpt skille mellom tilstanden til systemet, og det som en representant fra makro-verdenen vil observere.

En kvantemaskin

Vi kan elementene fra diskusjonene ovenfor: Qubit-registerne kan, som nevnt, lagre et stort antall verdier/tilstander samtidig. Det eksisterer kvantemekanikkbaserte logikkporter. Prosesseringen arbeider med tilstandene, fra begynnelse til slutt, uten mulighet for sjekking av mellomregninger. Når man observerer resultatet, kollapser tilstandsvektoren.

Utfra hva vi har nevnt om hva som skjer med tilstandsvektoren, når makro- og mikro-verdenen møtes, skjønner vi at det er store praktiske problemer som møter enhver som vil forsøke å konstruere en kvantemaskin.

De åpenbare fordelene ved muligheten for parallell prosessering alene, ville neppe ha vært tilstrekkelig vitaliserende for en utvikling mot en kvantemaskin. Når denne utviklingen likevel er akselererende, er det en vanlig oppfatning at dette skyldes

Det er mulig å designe kvantemekanikkbaserte algoritmer. Disse er langt mer slagkraftige enn de tilsvarende klassiske algoritmene. (Faktoriseringsalgoritmer, algoritme for det diskrete logaritmeproblemet (for gitte heltall b, m, og y, finn x slik at bx mod m=y).
Det er utviklet metoder for feilkorrigering, uten at tilstandsvektoren kollapser.
De første fysiske logikkportene er allerede konstruert.

Konklusjon

I dette notatet har vi forsøkt å lage en enkel beskrivelse av sentrale forhold ved en mulig fremtidig kvantemaskin. Vi har pekt på at dersom utviklingen fortsetter i dagens spor, så vil man om en tid være tvunget til å legge de kvantemekaniske prinsipper til grunn i konstruksjonen og bruken av datamaskinen.

Dersom man klarer å konstruere en slik maskin, en kvantemaskin, så vil denne kunne få en økning av slagkraften som langt overstiger det man hittil har vært vant med. It -spesialisten vil også kunne oppleve et større omstillingskrav enn det man hittil har vært vant med.

HØit Nr. 1-99