I en kvantedatamaskin kan du utføre en logisk operasjon på en superposisjoner av tilstander. Det vil si at du manipulerer alle qubits samtidig i stedet for én og én. Disse logiske operasjonene kan naturligvis være av en annen natur enn de man har i en klassisk datamaskin. Hvis du gjør disse logiske operasjonene på en smart måte kan du manipulere superposisjonen din på en slik måte at når du endelig velger å måle tilstanden din, så kollapser superposisjonen til forskjellige måleverdier avhengig av hva som er resultatet av problemet. Det er ingen hand-waving inne i bildet. Alt er kvantifiserbart og kan regnes ut eksakt.
Et interessant (dog ikke særlig nyttig) eksempel er Deutsch-Jozsa-algoritmen. Problemet du skal løse er som følger:
Du har en funksjon f:{0,1}^n -> {0,1}. Det vil si, du har en funksjon som avbilder n bit til enten 1 eller 0. Jeg sier nå til deg at denne funksjonen gjør én av to ting:
- Den avbilder all verdier til samme verdi. Den er dermed en konstant funksjon.
- Den avbilder halvparten av verdiene til 0 og halvparten av verdiene til 1.
For å avgjøre hvilke av de to tilfellene som stemmer må du med en klassisk datamaskin i worst case scenario evaluere funksjonen 2^(n - 1) + 1 ganger. Hvis du derimot kan bruke kvantelogikk og har tilstrekkelig mange qubits, kan du i stedet evaluere funksjonen èn enkelt gang og få svaret!
Så kommer spørsmålet ditt: hvordan er dette tilfellet? Det er umulig å forklare dette uten å bruke de tekniske aspektene ved kvantemekanik. Jeg kan prøve å si litt. La oss si funksjonen f bare kan ta verdiene 0 og 1 som input. Dvs, n=1. I en klassisk maskin er du nødt til å evaluere f[0] og [1] og se om verdiene er like.
La oss nå si vi har to qubits til vår disposisjon, og vi bygger en logikk slik at funksjonen f kan operere på verdien til qubit nummer 2. La oss kalle de fire tilstandene våre qubits kan ta for (0,0), (0,1), (1,0) og (1,1). I denne notasjonen er det første sifferet verdien til qubit nr. 1 og det andre sifferet verdien til qubit nr. 2. I kvantemekanikk kan vi snakke om tilstander som for eksempel a*(0,1) + b* (1,0). Hva betyr dette? Det betyr at hvis du måler begge qubitsene, så vil de anta verdien (0,1) med sannsynlighet a^2 og verdien (1,0) med sannsynlighet b^2. Det du kan gjøre med kvantelogikk er å blande sammen koeffisientene a og b på en smart måte, og det er dette, sammen med muligheten til å la f operere på qubit nr. 2, som utgjør algoritmen din. Merk at vi har kravet a^2 + b^2 = 1, siden sannsynlighetene må adderes til 1. I det følgende kommer jeg til å neglisjere dette kravet for at ikke ting skal se for stygt ut å lese. Du kan normalisere sannsynlighetene til 1 selv om du vil.
Du kan nå gjøre følgende:
- Start med tilstanden (0,1) - dvs qubit nr.1 har verdi 0 med 100% sannsynlighet og qubit nr.2 har verdi 1 med 100% sannsynlighet.
- Bruk en logisk port og send dette til tilstanden (0,0) - (0, 1) + (1,0) - (1,1). Dette betyr at, hvis du måler de to qubitsene, så det er 25% sjanse for at de sammen antar en av de fire mulige verdiene. Merk at minustegnene ikke har noen effekt på sannsynlighetene siden (-a)^2 = a^2, men de er viktige grunnet reglene for hvordan man kombinerer kvantetilstander.
- La f operere på denne tilstanden. Her man man definere hva dette betyr, men man kan f.eks konstruere logikken sin slik at f[(a,b)] = (a, b + f(a)), hvor addisjon er modulo 2. La oss ta utgangspunkt i dette.
- Bruk diverse logikk for å omforme superposisjonen. Man kan da vise at man kan ende opp med følgende superposisjon i den første biten (vi bryr oss ikke lenger hva som er i bit nr. 2. Man kan gjøre operasjoner slik at de ikke lenger er sammenfiltrede):
{ 1 + {-1}^[ f[0]+ f[1] ] } * (0, whatever) + { 1 - {-1}^[ f[0]+ f[1] ] } * (1, whatever).
Hvis vi nå måler qubit nummer 1, så har vi to muligheter: dersom f[0]=f[1] vil den siste koeffisienten { 1 - {-1}^[ f[0]+ f[1] ] } være lik 0 siden f[0]+f[1] adderer til et partall, og vi måler med hundre prosent sikkerhet verdien 0 i qubit nr. 1. Hvis på den andre siden f[0] ulik f[1], så vil f[0]+f[1] være odde, og den første koeffisienten forsvinner. Da måler vi med 100% sikkerhet at qubit nr. 1 har verdiene 1. Ergo så har vi avgjort hvorvidt f er en konstant funksjon med kun èn evaluering av f. Dette generaliserer til en hvilken som helst n, og vi har redusert antall funksjonsevalueringer fra 2^(n-1) + 1 til èn.
Shor's algoritme, som er den som omhandler primtallsfaktorisering, er nok langt mer komplisert. Slik jeg har forstått det, så handler algoritmen om å bygge en svær superposisjon der koeffisientene til hver tilstand er et tall i en viktig tallreke tilknyttet det store tallet du vil faktorisere. Denne tallrekken er periodisk, men vanligvis er perioden så lang at man ikke klarer å finne den ved klassiske beregninger. I kvantemekanikk kan man visstnok bruke en
Quantum Fourier transform for å hente ut perioden til tallrekka på en effektiv måte. Dersom du har perioden kan man enklere finne fram til primtallsfaktorene. Hvordan man bygger opp denne tallrekka i første omgang og hvordan man faktisk kan ta den Fouriertransformen kan jeg ikke gi noe svar på, men hand-waving er det nok ikke.