Kvantdatorer

Jags skulle behöva lite hjälp med att föstå hur en kvantdator fungerar, jag har sökt runt lite men jag tycker att det jag hittar rör mest till saker. De länkar jag har lyckats samla på mig hittills är

www.qubit.org
http://qist.lanl.gov
www.quiprocone.org/protected/dd_lectures.htm
www.cordis.lu/ist/fet/qipc-eu.htm

och så klart det som står på wikipedia.

Hur som helst så känns allt väldigt abstrakt så nu undrar jag om någon här kan göra en begriplig beskrivning hur en kvantdator fungerar och gärna dra paraleller med en klassisk dator.

Börja först att förklara vad det mest grundläggande du inte begriper är =)

Jag begriper i princip ingenting

Jag har fått en liten aning om vad det handlar om vad entagled states handlar om nu

Säg att vi har 2 elektroner
1: (a_1 |up_1> + b_1 |down_1>)
2: (a_2 |up_2> + b_2 |down_2>)
multiplikationen av dessa blir

a_1*a_2 |up_1> |up_2> + b_1*b_2 |down_1> |down_2> + a_1*b_2 |up_1> |down_2> + a_2*b_1 |down_1> |up_2>

Detta är inte ett entagled state just eftersom det går att faktorisera. När denna multiplikationen har utförts är elektronerna i superposition om det krävs 2 eller fler basvektorer för att beskriva stadiet.

Dvs.
1/sqrt(2) (|up,down> + |down,up>) är entagled eftersom det inte går att faktorisera. Det är även i superposition eftersom det krävs 2 basvektorer för att beskriva.

Problemet är att jag begriper inte vad denna kunskap ska vara bra för. Vad jag har fått berättat för mig är att när man skickar in ett state som inte är i superposition så har man inte vunnit något jämfört med en klassisk dator, men när man skickar in ett entagled state som är i superpostion så utförs flera beräkningar samtidigt. Varför och hur fungerar det?

Invärdet behöver inte vara ett "entangled state" för att dra nytta av kvantdatorn.

Antag att du har en funktion f(x) som tar ett invärde x, och genererar ett utvärde y = f(x). Antag vidare att x bara är en enda bit.

På en vanlig klassisk dator kan en bit vara antingen "0" eller "1". För att evaluera funktionen f(x) måste du köra funktionen två ggr. Ett exempel på en funktion är

f("0") = "1"
f("1") = "0"

d.v.s funktionen inverterar invärdet. Det finns 3 andra funktioner, men det är oviktigt.

Med en kvantdator, och kvantbitar, kan varje bit vara antingen |0>, |1> eller en superposition av de båda, typ a|0> + b|1>.

Är funktionen f(x) linjär ser vi att vi får (om vi matar in en kvantbit i tillståndet 1/sqrt(2)*(|0> + |1>) )

f(1/sqrt(2)*(|0> + |1>)) = 1/sqrt(2)*f("0") + 1/sqrt(2)*f("1") = 1/sqrt(2)|1> + 1/sqrt(2)|0>

Vi får alltså ut funktionens värde i alla punkter ("0" och "1") på en gång, genom att bara köra funktionen EN ENDA gång. Detta p.g.a. att invärdet kan vara en superposition av alla möjliga "klassiska" invärden på en gång.

Det är exakt detta som är styrkan med kvantdatorer. Givetvis är inte verkligheten lika enkel, eftersom vi i slutändan måste få ett enda tal som svar från vår funktion. Att säga att svaret är "en superposition" räcker inte, för vi tvingas till slut att mäta vad resultatet blev och då kollapsar superpositionen till antingen "0" eller "1" med sannolikheter som beror av koefficienterna i superpositionen. För att veta hur funktionen f(x) ser ut måste vi istället antingen göra om samma mätning (sätta kvantbiten i samma initialtillstånd, köra funktionen och sedan mäta på samma sätt) flera gånger, eller alternativt tillverka flera identiska system, ge dem samma invärde och sedan mäta resultatet på samma sätt. På så viss skaffar vi oss en bild av hur sannolikhetsfördelningen (koefficienterna) ser ut och därmed hur funktionen f(x) ser ut. Klassiskt sett vet vi exakt hur många gånger vi måste köra funktionen för att få ett exakt svar (2 i det här fallet). I kvantmekaniken finns inga exakta svar, utan vi måste göra om proceduren "tillräckligt" många gånger för att vara "hyffsat" säkra.

De problem där en kvantdator är bättre är de som kan formuleras så att antalet klassiska körningar som krävs är större än det antal mätningar som krävs kvantmekaniskt för "hyfsad säkerhet". I dessa fall överväger fördelen med kvantdatorns "parallellism" nackdelarna med att man måste mäta flera gånger. Det gäller även att designa algoritmerna på ett sådant sätt att så få mätningar som möjligt krävs. Hittills finns det ytterst få problem som är kända där kvantdatorer är bättre. Några av de mest kända är primtalsfaktorisering, sökning och simulering av kvantmekaniska system. Ordbehandling eller liknande är inte snabbare på en kvantdator, och det finns inget som en kvantdator kan göra som en klassisk dator i teorin inte klarar av, iaf vad jag vet.


==========================

Entanglement är överkurs och det är ingenting som krävs för att förstå de grundläggande egenskaperna hos en kvantdator. Entanglement används i exempelvis "kvantteleportering", "quantum encoding" eller liknande.

Antag att du har två kvantbitar i ett gemensamt tillstånd du kan skriva |q1, q2> där q1 och q2 vardera kan vara antingen 0 eller 1.

Om du fixar så att det gemensamma tillståndet för båda kvantbitarna är ett "entangled state", exempelvis

|q1,q2> = |00> + |11> (jag har ignorerat normeringen här)

och sedan separerar kvantbitarna (typ, person A tar sin kvantbit och åker till Säffle, och person B tar den andra kvantbiten och åker till Stockholm) så ser vi att om person A (ägare av den första kvantbiten) nu mäter på sin kvantbit och får resultatet "1", så vet vi direkt vad person B kommer att få då han mäter på sin kvantbit.

Innan person A mäter är tillståndet

|00> + |11>

Efter mätningen (som vi antar blir "1") kollapsar tillståndet till

|11>

Detta innebär att person B's kvantbit endast kan vara i tillståndet 1. "Information" har således på "nolltid" överförts mellan de två kvantbitarna.
Ordet information är här lite vagt. Tillståndet hos person B's kvantbit ändras på en gång så fort en mätning på kvantbit 1 sker. Information färdas dock inte snabbare än ljuset, eftersom information i det här syftet avser vad person A och B vet om sina kvantbitar. Person B vet inte utgången av person A's mätning innan person A meddelar person B om detta (typ via telefon). Ingen "information" har därmed färdats snabbare än ljuset.

Wow!
Mycket intressant läsning, tackar ödmjukast för ett så ambisiöst svar Anencefali!!





Vad tror vi om framtiden. Kommer vi inom vår livstid att få uppleva persondatorer som bygger på denna teknik?

Är min uppfattning av vad entaglement således fel?

Min nästa fråga är vad blochsfären har med allt det här att göra.

Sen berättade även min handledare att den stora vinsten med kvantdatorer är att antalet beräkningar som behöver göras växer linjärt med problemets storlek till skillnad från med klassiska datorer då antalet beräkningar växer exponentiellt. Dvs oavsett hur mycket snabbare det går att göra en beräkning med en klassisk dator så kommer kvantdatorn ändå att vara snabbare för tillräckligt stora problem. Kan du utveckla hur detta fungerar?

Hur kan antalet beräkningar växa linjärt? vågar man tro att det har med den harmoniska oscillatorn att göra? eller är det helt ute och cyklar...?

Sedan så kommer vi nog få se en fungerande kvantdator om max 15 år. Troligtvis mycket snabbare, skulle tro att det ligger ett nobelpris till den som får den första fungerande kvantdatorn, dvs med mer än några qubits.

vad är kvantteleportering?

Njae, entanglement är mycket riktigt ett tillstånd för två kvantbitar som inte kan skrivas som en direkt produkt av tillstånden för de båda kvantbitarna var för sig, d.v.s du saknar antingen termerna |01> och |10> eller |00> och |11>.

Det finns väl inget som säger att alla problem växer linjärt bara för att det är på en kvantdator de utförs.

Problem och dess svårighet kategoriseras genom att man delar in dem i så kallade "komplexitetsklasser". Väldigt hårddraget finns det två klasser, de problem vars tidsåtgång ökar linjärt (eller som ett polynom, d.v.s ordo(N^k)) med dess storlek N (där N kan vara ett primtals storlek, antalet noder i en graf, antalet element i nån mängd etc), och de problem vars tidsåtgång växer exponentiellt.

Problem som tillhör den första klassen (även kallad P, för "polynomial") betraktas som "enkla problem" medan de som tillhör den andra klassen, "inte P " betraktas som svåra/olösbara.

Att söka efter ett visst element bland totalt N stycken element är ett enkelt problem, eftersom tidsåtgången är direkt proportionell mot N. På en kvantdator går dock samma problem att lösa (iaf i teorin) som sqrt(N) och en kvantdator är därför bättre på sådana sökningar än en klassisk.

Att faktorisera primtal kräver (om jag inte minns fel) exponentiell tidsåtgång, ordo(k^N) eller liknande, medan det på en kvantdator endast kräver ordo(log(N)^3), d.v.s. polynomtid m.a.p log(N).

Hur tidsåtgången ser ut beror främst på hur problemet ser ut, inte på om det är en kvantdator eller inte. "The travelling salesman problem" är mig veterligen fortfarande ett "svårt problem" och det finns ingen kvantdator-version som gör det till ett "enkelt problem".

Däremot kan kvantdatorer även förenkla problem med avseende på de resurser som krävs. För att simulera ett kvantmekaniskt system på en klassisk dator måste man använda komplexa tal, och därmed vektorer av storleken C^N där N är antal komponenter och C en konstant. Om samma simulering görs på en kvantdator behövs bara kN kvantbitar. Jag försökte räkna lite snabbt, och kom fram till att det för att simulera 100 kvantbitar på en klassisk dator krävs motsvarande (med 32 bitars precision) 10 000 biljarder terrabyte (~10^31) minnesutrymme bara för att representera systemet. Det är rätt mycket

==================================

Bloch-sfären är bara ett hjälpmedel för att visualisera tillståndet för EN kvantbit. En förenklad förklaring kan vara att du för att representera en ensam kvantbit och dess tillstånd som en linjärkombination av basvektorerna |0> och |1> behöver två komplexa tal (koefficienterna), d.v.s. a|0> + b|1>, eller snarare

Aexp(iTheta_a)|0> + Bexp(iTheta_b)|1>

där jag bara skrivit om de komplexa talen a och b, och A och B är reella tal. Den ena av koefficienterna kan alltid göras reell genom att multiplicera uttrycket med en "global fas" (exp(iRho), d.v.s. tillståndet är

A|0> + Bexp(iTheta)|1>

Vidare vet vi att |a|^2 + |b|^2 = 1 måste gälla eftersom den totala sannolikheten att hitta kvantbiten i NÅGOT tillstånd alltid är 1.

Detta innebär att A^2 + B^2 = 1, vilket gör att vi kan skriva detta som
A = cos(Phi), B = sin(Phi) eftersom cos^2 + sin^2 = 1.

Kvar har vi då att tillståndet för kvantbiten kan skrivas som

cos(Phi)|0> + sin(Phi)exp(iTheta)|1>

vilket är det samma som en punkt på en enhetssfär som beskrivs av vinklarna Phi och Theta. Dock visar det sig att det nu finns två punkter (på motsatt sida från varandra) på denna sfär som svarar mot exakt samma tillstånd, så man brukar betrakta endast den övre halvan av denna sfär och "dra ut den till en ny sfär", vilket ger att man istället skriver

cos(Phi/2)|0> + sin(Phi/2)exp(iTheta)|1>

Det praktiska med Blochsfären är att alla operationer som går att utföra på en kvantbit nu svarar mot att man roterar den vektor som jag skrivit ovan (eller man flyttar punkten på Blochsfären). Alla möjliga operationer, eller kvantgrindar, svarar därför mot en rotation vilket är hemskt finurligt när man skall börja räkna på saker och ting.

Njae, jag vet inte riktigt vad du menar med den harmoniska oscillatorn. Utveckla gärna Antalet beräkningar (eller snarare tidsåtgången) växer som jag skrev ovan beroende av problemet ser ut.

Jag är tveksam till att det kommer att finnas kvantdatorer inom 15 år. Detta med tanke på hur utvecklingen sett ut hittills. Det finns fortfarande ingen som kan visa upp en fullt fungerande kvantdator med endast TVÅ kvantbitar. Visst, de har lyckats göra beräkningar på 7-8 kvantbitar genom att använda molekyler, men det räknas inte riktigt eftersom ett sådant system knappast är skalbart. De två stora "fiender" som finns är "dephasing" och "relaxation", och det har hittills visat sig att de kvantbitar (olika realiseringar såsom SQUIDS, molekyler, SCB, optiska varianter) etc är bra med avseende på det ena men då mycket dåligt på det andra. Kommersiella kvantdatorer (typ desktops) är helt i framtiden eftersom det krävs ett mindre laboratorium för att få dem att fungera (med kylning och avancerad mätutrustning). Något behov för "desktop"-varianter finns iofs inte heller, eftersom ordbehandling och liknande inte kräver någon kvantdator.

Kvantteleportering är en teoretisk (och även praktisk) realisering av hur man överför ett okänt kvanttillstånd från en punkt till en annan (typ från Stockholm till Säffle) genom att använda sig av entanglement.

Antag att det finns två personer, A och B, på två separerade platser i landet. Innan personerna skiljdes åt tog de med sig var sin kvantbit tillhörande ett "entangled", eller sammanflätat, tillstånd |00> + |11>.

Person A har nu en extra kvanbit i ett okänt tillstånd a|0> + b|1> som han/hon vill överföra till person B.

Det gemensamma tillståndet för alla tre kvantbitarna kan skrivas

(a|0> + b|1>)*(|00> + |11>) där "kvantbiten som skall teleporteras" skrivs först och de båda sammanflätade kvantbitarna sist. Vi kan multiplicera ut skiten och erhålla

a|000> + a|011> + b|100> + b|111>

där jag använder skrivsättet att |1>*|00> = |100> o.s.v.

De två första siffrorna XY i varje basvektor (|XYZ>) tillhör kvantbitarna som är i person A's ägo. Person A har fritt fram att utföra vilka operationer på sina två kvantbitar han/hon vill, och vi antar nu att hon utför en så kallad CNOT-operation på dem. Jag orkar inte förklara vad CNOT gör exakt, men vi kan säga att resultatet är att

|00> -> |00>
|01> -> |01>
|10> -> |11>
|11> -> |10>

alltså typ om första kvantbiten är "1" så flippas tillståndet på kvantbit 2. Efter CNOT-operationen (som bara utförs på de två första kvantbitarna XY) har vi tillståndet

a|000> + a|011> + b|110> + b|101>

eller

a|0>*(|00> + |11>) + b|1>*(|10> + |01>)

Person A utför sedan en s.k. "Hadamard, eller sqrt(NOT)"-operation på kvantbiten som skall teleporteras. Denna operation gör att

|0> -> |0> + |1>
|1> -> |0> - |1>

(där jag struntat i normeringskoefficienter).

Efter att person A gjort detta är tillståndet

a*(|0> + |1>)*(|00> + |11>) + b*(|0> - |1>)*(|10> + |01>)

eller

|00>*(a|0> + b|1>) + |01>*(b|0> + a|1>) + |10>*(a|0> - b|1>) + |11>*(-b|0> + a|1>)

(ingen magi, bara omskrivning). Nu har vi brutit ut person A's båda kvantbitar först (|00>, |01>, |10> och |11>). Person A behöver nu bara mäta sina båda kvantbitar och se i vilket tillstånd de är.

Antag att person A mäter och ser att de är i tillståndet |00>. Tillståndet för de tre kvantbitarna tillsammans kollapsar då (p.g.a. entanglement) till |00>*(a|0> + b|1>), d.v.s. person B's kvantbit är a|0> + b|1> vilket innebär att vi TELEPORTERAT tillståndet hos den kvantbit person A ville överföra till kvantbiten tillhörande person B! Voila!

Om person A istället skulle ha mätt och fått svaret |01> så kollapsar vi till
|01>*(b|0> + a|1>), d.v.s person B's kvantbit är nu i tillståndet b|0> + a|1>. Person A ringer då till person B och säger, "Hej, du måste utföra operationen X på din kvantbit". Operationen X innebär att |0> -> |1> och |1> -> |0>, och efter att person B gjort detta är dennes kvantbit nu i a|0> och b|1> och vi har teleporterat. På samma sätt finns andra operationer B kan göra om A mäter upp |10> eller |11>.

Intressant är även att under teleporteringen så förstördes det okända kvanttillståndet (a|0> + b|1>) hos person A's kvantbit. Detta är nödvändigt då det finns en regel ("No cloning theorem") som säger att ett okänt tillstånd inte kan kopieras.

Woot, QC here we go!

http://www.nature.com/news/quest-for...k-gold-1.10124
http://hardware.slashdot.org/story/1...g-breakthrough

Se hur lång tid innan vi bönder får se en kvantdator

Orelaterat men ändå intressant angående datateknik utveckling ->
http://www.nature.com/news/optical-m...enecks-1.10108

Har inte provat själv, men de verkar hävda att om man formulerar optimeringen rätt så fungerar det bra för vissa typer av problem.

Testa emulatorn kanske?

http://www.dwavesys.com/en/dev-portal.html

Går det med gridteknologi att skynda på utvecklingen?