Har lest litt om kvanteprossesorer og jeg ser det er mange som skriver at de vil endre hele verden.
Utifra hva jeg skjønner er det sånn at datamaskiner vanligvis operer med 0 og 1, mens med kvanteprossesorer kan de opere med begge på en gang.
Det jeg lurer litt på er om dette får noe stor betydning for hvordan bruksområdet blir på datamaskiner med kvanteprossesorer framover?

Dersom vi får til å bygge en brukbar kvantedatamaskin, det vil si at vi klarer å skalere opp til en respektabel andel qubits (kvanteanalogen til en bit), redusere støy og implementere feildeteksjon og feilkorrigering, så kan det få dramatiske konsekvenser. Grunnen til dette er at en kvantedatamaskin vil være ekstremt god til å faktorisere store tall sammenlignet med dagens datamaskiner. Å faktorisere store tall er enormt tidkrevende på en klassisk datamaskin, og all kryptering vi bruker i dag er basert på at denne oppgaven er så og si umulig i praksis. Dersom man blir i stand til å faktorisere store tall fort kan man knekke krypteringen som brukes i dag. Av nettop denne grunn har det oppstått et eget område innenfor kryptografi kalt Post-quantum cryptography.

Videre så tror teoretikerne at en kvantedatamaskin vil være ekstremt effektiv for å gjøre simuleringer. Hvis dette er tilfellet så kan det bety at kvantedatamaskiner blir et kraftig verktøy for å drive med vitenskap, og at de dermed kan akselerere nye oppdagelser. Usikker på hva basisen for dette utsagnet er, men har hørt det sagt av et par teoretiske fysikere tidligere.

Det er dog viktig å påpeke at en kvantedatamaskin ikke vil være bedre en en klassisk datamaskin på alle områder, så kvantedatamaskiner vil sannsynligvis blir komplementært og ikke en erstatter.

Jeg er ikke så glad i å linke til videoer som svar, men jeg var på et foredrag om kvanteberegning med John Preskill for et par uker siden. John Preskill har gjort flere betydelige bidrag til fagområdet, så han vet hva han snakker om. Foredraget ble filmet, så hvis du er interessert i å forstå litt mer av detaljene kan du ta en titt her: https://drive.google.com/file/d/0B0g...pLWlI5Um8/view.

Kort svar fra en som ikke har særlig ekspertise på området:
Det er vanskeligere å løse en sudoku enn å verifisere at løsningen er korrekt, men med en kvantedatamaskin blir dette to sider av samme sak.

I prinsippet kan en klassisk datamaskin gjøre alt en kvantedatamaskin kan, sålenge du er villig til å gi den stadig sprekere hardware og mer tid til å løse problemet. Ulempen er bare at du for noen problemer veldig fort kommer dit at selv om datamaskinen din er en idéell skapning som består av mesteparten av universet, så vil den likevel ikke gjøre målbar fremgang - selv om du lar den kverne og gå i flere milliarder år. Det er termodynamiske betraktninger som tilsier at visse problemer ikke kan løses med klassiske datamaskiner.

Jeg tror du har et litt feil bilde på hva kvantemekanikk er. Det vil føre for langt å skrive en avhandling om kvantemekanikkens irrganger, men for øyeblikket må du bare godta at det eksisterer kvantefenomener som ikke eksisterer i klassisk fysikk. Så. Et sett N klassiske bits gir det totalt 2^N mulige tilstander, men datamaskinen kan kun være i én slik tilstand av gangen. Men hvert qubit er en superposisjon av alle mulige verdier, og dermed er systemet som helhet i en superposisjon av alle mulige egentilstander. Samtidig. (Akkurat det der er litt kjernen i kvantemekanikk.) Når du utfører målingen for å hente ut resultatet kollapser du bølgefunksjonen ned til én av disse egentilstandene - den som har svaret ditt hvis du har kodet algoritmen din riktig. Det er en del problemer som før hadde eksponensiell skalering som plutselig blir polynomiske. Og dét er en viktig forskjell.

Alt det der vet jeg. Jeg ser bare ikke sammenhengen mellom dét og en gangbar algoritme for f.eks. faktorisering av gigantiske tall. Det virker bare som magi og hand-waving for min del. I en drøss av mulige tilstander, hvordan ender man opp på den riktige? Hvordan bygger man opp en "kvantealgoritme"? Hvordan vet man at operasjonene som utføres har det resultatet de har?

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:

1. Den avbilder all verdier til samme verdi. Den er dermed en konstant funksjon.
2. 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:

1. 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.
2. 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.
3. 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.
4. 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.