Faktorisera stora tal? Shor!

Det här är en översättning av Scott Aaronsons text Shor, I’ll do it, som jag publicerar här med hans tillåtelse. Det är en jättefin introduktion till den mest berömda av alla kvantdatoralgoritmer, alltså en beräkning som en kvantdator borde kunna göra bättre än en vanlig dator. Dessutom är jag lite förtjust i Scott Aaronsons personliga sätt att uttrycka sig. (För fler exempel, läs hans blogg. Eller lyssna på avsnittet av Vetandets värld där jag intervjuade honom bland andra: Så funkar kvantdatorn.)

Jag ska inte sticka under stol med att det ändå är rätt mycket tuggmotstånd i texten, och den passar kanske bäst för den som kommer ihåg åtminstone lite gymnasiematte och har google till sin hjälp. Fast två ledtrådar kan jag ge:

ket
Från Diracs bra(c)ket-notation, ett sätt att skriva saker i kvantmekaniken.
RSA
Ett krypteringssystem, uppfunnet på 70-talet och väldigt brett tillämpat.

Nu: över till Scott Aaronson!

Shor, I’ll do it

Jag har pratat mycket på sista tiden om hur kvantalgoritmer inte fungerar. Men förra veckan frågade JR Minkel, en redaktör på Scientific American, om jag kunde skriva en kort essä om hur kvantalgoritmer faktiskt fungerar, som han sen kunde länka till från SciAm’s webb. ”OK” svarade jag, och glömde tillfälligt bort alla (x^{10})^{5000} kvantalgoritm-tutorials som redan finns på webben. Så jag ställde upp den här uppgiften för mig själv: att förklara Shors algoritm utan att använda ett enda ket-tecken, eller för den delen nån matte alls utöver aritmetik.

Okej, så säg att du vill knäcka krypteringssystemet RSA, för att råna några banker, läsa ditt ex:s epost, nåt sånt. Vi vet alla att det här att knäcka RSA i grunden handlar om att hitta primtalsfaktorerna av ett stort heltal N. Tyvärr vet vi också att ”testa alla möjliga delare parallellt,” och sen omedelbart plocka ut den rätta, inte funkar. Oavsett vad det står i hundratals populärvetenskapliga tidskriftsartiklar är det här med att testa allting parallellt helt enkelt inte nåt som en kvantdator kan göra. Visst, på sätt och vis kan du ”testa alla möjliga delare” — men om du sen ska mäta resultatet kommer du att få en slumpmässig delare, som nästan säkert inte är den du vill ha.

Så vad det betyder är att om vi vill ha en snabb kvantfaktoriseringsalgoritm, så måste vi utnyttja nån struktur i faktoriseringsproblemet: med andra ord, nån matematisk egenskap hos faktorisering som det inte har gemensamt med det allmänna problemet att hitta en nål i en höstack.

Som tur är har faktoriseringsproblemet mängder av speciella egenskaper. Ett exempel: om jag ger dig ett positivt heltal kanske du inte vet vad det har för primtalsfaktorer, me du vet att det har exakt en faktorisering! Jämför det med, säg, att jag ger dig en Sudoku-gåta — då skulle du inte kunna veta om det finns exakt en lösning, 200 miljoner lösningar, eller inga lösningar alls. Det är klart, att veta att det finns exakt en nål i höstacken är inte till mycket hjälp för att hitta den! Men den här entydigheten är en ledtråd till att faktoriseringsproblemet skulle kunna ha andra trevliga matematiska egenskaper som väntar på att plockas upp. Och så visar det sig faktiskt vara.

Den egenskap vi ska utnyttja är att faktorisering kan reduceras till ett annat problem, som kallas att hitta en period. OK, nu är det dags för en utvikning om talteori. Vi tar en titt på en talföljd som varit min favorit sen jag var fem år gammal: tvåpotenserna.

2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, …

Nu tar vi och tittar på tvåpotenserna ”modulo 15”: med andra ord, resten som blir över när vi delar varje tvåpotens med 15.

2, 4, 8, 1, 2, 4, 8, 1, 2, 4, …

Som du ser får vi en periodisk följd när vi tar potenser av två modulo 15, vars period (alltså hur långt du måste gå innan den börjar upprepa sig) är 4. Vi tar ett till exempel, potenser av två modulo 21:

2, 4, 8, 16, 11, 1, 2, 4, 8, 16, …

Den här gången får vi en periodisk talföljd vars period är 6.

Nu kanske du undrar: finns det någon allmän regel som vi kan använda för att förutsäga perioden? Oj oj, jag undrar om nån matematiker har tänkt på den frågan…

Öh, ja, det har de, och det finns ett vackert mönster som upptäcktes av Euler på 1760-talet. Låt N vara en produkt av två primtal, p och q, och betrakta följden

x mod N, x² mod N, x³ mod N, x⁴ mod N, …

Givet att x inte är delbar med p eller q kommer den ovanstående följden att upprepa sig med någon period som går jämnt upp i (p-1)(q-1).

Till exempel om N=15, då är primtalsfaktorerna av N p=3 och q=5, så (p-1)(q-1)=8. Och faktiskt, perioden av följden var 4, som går jämnt upp i 8. Om N=21, då är p=3 och q=7, så (p-1)(q-1)=12. Och faktiskt, perioden var 6, som går jämnt upp i 12.

Nu vill jag att du tar ett steg tillbaka och funderar på vad det betyder. Det betyder att om vi kan hitta perioden av följden

x mod N, x² mod N, x³ mod N, x⁴ mod N, …

så kan vi lära oss något om primtalsfaktorerna i N. Specifikt kan vi få ut en delare av (p-1)(q-1). Nu ska jag erkänna att det inte är lika bra som att få ut p eller q direkt, men medge att det alltid är något. Det är faktiskt mer än bara något: det visar sig att om vi kan hitta flera slumpmässiga delare av (p-1)(q-1) — till exempel genom att testa olika värden på x — då är det en god chans att vi kan sätta ihop de här delarna och komma fram till (p-1)(q-1). Och känner vi bara (p-1)(q-1), så kan vi använda några fler små knep för att få ut p och q, primtalsfaktorerna vi ville åt.

Så vad är smolket i glädjebägaren? Ja, även om följden

x mod N, x² mod N, x³ mod N, x⁴ mod N, …

kommer att börja upprepa sig efter ett tag, kan antalet steg innan den upprepar sig vara nästan lika stort som N självt — och N kan ha hundratal eller tusentals siffror! Det är därför det här med att hitta perioden inte verkar leda till någon snabb klassisk faktoriseringsalgoritm.

Aha, men vi har en kvantdator! (Eller, vi tänker oss att vi har.) Så kanske finns det ännu hopp. Specifikt, anta att vi kunde skapa en enorm kvantöverlagring (superposition) av alla talen i vår talföljd: x mod N, x² mod N, x³ mod N, etc. Då kanske det finns någon kvantoperation som vi kan utföra på det överlagrade tillståndet som kan avslöja perioden.

Nyckeln är att vi inte längre försöker hitta en nål i en exponentiellt stor höstack, något som vi vet är svårt även för en kvantdator. Istället försöker vi hitta perioden av en talföljd, vilket är en global egenskap hos alla talen i följden tillsammans. Och det gör stor skillnad.

Så här: om du tänker på kvantberäkningar i termer av ”parallella universa” (och om du gör det eller inte är upp till dig) så finns det ingen praktiskt tillgänglig metod att detektera ett specifikt universum som skiljer sig från alla de andra. En sådan ensam röst i öknen skulle dränkas i den stora mängden förortsbosatta, Dockers-klädda konformistiska universa. Vad man kan hoppas detektera, däremot, är en gemensam egenskap för alla de här parallella universumen tillsammans — en egenskap som bara kan avslöjas av en beräkning som alla universa bidrar till.

(OBS: Av säkerhetsskäl, var snäll och förklara inte ovanstående för skribenter av skolan ”kvantberäkningar = exponentiell parallellism”. De kan skrumpna ihop som vampyrer som kommer ut i solljuset.)

Så uppgiften framför oss är inte hopplös! Men om vi vill få den här periodfinnaridén att funka måste vi svara på två frågor:

  • Kan vi använda en kvantdator för att snabbt hitta en superposition av x mod N, x2 mod N, x3 mod N, och så vidare?
  • Om vi antar att vi har en sådan superposition, hur listar vi ut perioden?

Vi tar oss an den första frågan först. Vi kan verkligen skapa en superposition över alla heltal r, från 1 upp till N eller så. Problemet är, att för ett givet r, hur beräknar vi snabbt xr mod N? Om r var (säg) 300 kvadriljoner, skulle vi behöva multiplicera x med sig själv 300 kvadriljoner gånger? Det skulle verkligen inte vara snabbt nog, och som tur är är det inte nödvändigt. Vad vi kan göra istället kallas upprepad kvadrering. Det är förmodligen enklast att bara visa ett exempel.

Antag N=17, x=3 och r=14. Då är första steget att representera r som en summa av tvåpotenser:

r = 23 + 22 + 21.

Då är

x^r = 3^{14} = 3^{2^3 + 2^2 + 2^1} = 3^{2^3} \cdot 3^{2^2} \cdot 3^{2^1} = ((3^2)^2)^2 \cdot (3^2)^2 \cdot 3^2

Notera också att vi kan göra alla multiplikationer mod N, och förhindra talen för att växa ohanterligt stora i mellanstegen. Detta ger oss resultatet

314 mod 17 = 2.

OK, så vi kan skapa en kvant-superposition över alla par av heltal på formen (r, xr mod N), där r går från 1 upp till N eller så. Men sen, givet en superposition över alla element i en periodisk följd, hur får vi ut perioden av den här följden?

Ja, äntligen har vi kommit till sakens kärna — den del av Shors kvantalgoritm som faktiskt beror på kvantmekanik. För att få ut perioden använder Shor något som kallas kvant-fouriertransform, QFT. Utmaningen för mig nu är att förklara QFT utan att faktiskt använda matte. Hmmmm…

Ok, låt mig pröva detta. Liksom många datavetare jobbar jag på extremt udda tider. Du vet, det där berömda experimentet där de stopper in folk i flera veckor i ett slutet rum utan klockor och solljus, och folk gradvis skiftar från ett 24-timmarsdygn till ett 25- eller 26- eller 28-timmarsdygn? Alltså, det är bara vardagsliv för mig. En dag vaknar jag vid 09, nästa dag vid 11, dagen efter det vid 13, och så vidare. Faktum är att jag gladeligen ”loopar hela vägen runt” om det inte kommer några lektioner eller möten ivägen. (Jag gjordet det hela tiden när jag var vid Berkeley.)

Nu kommer min fråga: säg att jag berättar att jag vaknade klockan 17 den här eftermiddagen. Från enbart detta faktum, vad kan du dra för slutsats om hur långt mitt ”dygn” är, om jag är på ett 25-timmarsschema, eller 26,3-timmarsschema, eller vad?

Svaret är, förstås, inte mycket! Jag menar, det är en ganska säker gissning att jag inte håller ett 24-timmarsschema, för då borde jag vakna upp på morgonen och inte klockan 17. Men nästan varje annat schema — 25 timmar, 26 timmar, 28 timmar, o.s.v. — kommer att leda till att jag ”loopar runt dygnet”, så att det inte är någon överaskning att jag stiger upp vid 17 någon eftermiddag.

Nu vill jag att du tänker dig att min sovrumsvägg är täckt med analoga klockor. De är väldigt konstiga klockor: en av dem gör ett helt varv på 17 timmar, en av dem går runt på 26 timmar, en på 24,7 timmar, och så vidare för alla möjliga antal timmar. (För enkelhetens skull har varje klocka bara en timvisare, ingen minutvisare.) Tänk dig också att under varje klocka finns en anslagstavla med ett häftstift. När jag först flyttade in i den här lägenheten satt varje häftstift i mitten av sin tavla. Men varje gång jag vaknar på ”morgonen” är det första jag gör att gå runt i rummet och flytta varje häftstift precis en tum i den riktning som visaren på klockan ovanför pekar.

Här är nu min nya fråga: genom att studera häftstiften i mitt rum, kan du lista ut vilken längd jag har på mitt dygnsschema?

Jag hävdar att det är möjligt. För att ta ett exempel, anta att jag håller mig till ett 26-timmarsdygn. Vad händer då med häftstiftet vid 24-timmarsklockan? Det är inte svårt att inse att det får en periodisk rörelse: visst, det driver omkring lite, men var tolfte dag kommer det tillbaka till mitten av tavlan där det började. En morgon skulle jag flytta häftstiftet en tum åt det här hållet, en annan morgon åt det där hållet, men små småningom skulle alla dessa rörelser i olika riktningar ta ut varandra.

Å andra sidan — anta återigen att jag håller mig till ett 26-timmarsdygn — vad skulle hända med häftstiftet vid 26-timmarsklockan. Här blir svaret annorlunda. För vad 26-timmarsklockan anbelangar har jag vaknat exakt samma tid varje ”morgon”! Varje gång jag vaknar, pekar 26-timmarsklockan i samma riktning som den visade förra gången jag vaknade. Så jag flyttar häftstiftet en tum i samma riktning hela tiden, tills den inte ens är kvar på anslagstavlan!

Av detta följer att du bara genom att titta på vilket häftstift som flyttat sig längst från startpunkten kan lista ut vilken sorts dygnsschema jag håller. Med andra ord kan du sluta dig till ”perioden” av den periodiska följd som är mitt liv.

Och det, i grund och botten, är kvantfouriertransformen. Nå, lite mer noga uttryckt är QFT:n en linjär transformation (en enhetstransformation [unitary transformation] rentav) som avbildar en vektor av komplexa tal på en annan vektor av komplexa tal. Inputvektorn har ett nollskilt element som motsvarar varje gång jag vaknar upp, och noll överallt annars. Outputvektorn visar positionerna för häftstiften på anslagstavlorna (som man kan tänka på som punkter i det komplexa planet). Så vad vi får, i slutänden, är en linjär transformation som avbildar ett kvanttillstånd som kodar en periodisk sekvens på ett kvanttillstånd som kodar perioden för den sekvensen.

Ett annat sätt att tänka på detta är i termer av interferens. Jag menar, nyckelpoängen med kvantmekanik — det som skiljer den från klassisk sannolikhetsteori — är att där sannolikheter alltid är ickenegativa, så kan amplituder i kvantmekanik vara positiva, negativa, eller komplexa. Och på grund av det kan amplituderna som motsvararar olika sätt att få ett visst svar ”interferera destruktivt” och ta ut varandra.

Och det är precis vad som pågår i Shors algoritm. Varje ”parallellt universum” som motsvarar ett element i följden bidrar med någon amplitud till varje ”parallellt universum” som motsvarar en möjlig period av den följden. Haken är att för alla perioder utom den ”sanna” kommer de här bidragen att peka i olika riktningar och därför ta ut varandra. Bara för den ”sanna” perioden pekar bidragen från olika universa i samma riktning. Och det är därför vi, när vi mäter i slutänden, kan hitta den sanna perioden med hög sannolikhet.

Det är uppenbarligen en hel del jag har hoppat över här; titta här [eller här (död länk från Aaronsons artikel] eller här eller här eller här eller här eller här eller här eller här eller här eller här eller här för detaljerna.

Om åka

Fysiker, sf-fantast, allmän entusiast.
Det här inlägget postades i kvantmekanik, Nivå: intresserad (4), Tillämpningar, Uncategorized. Bokmärk permalänken.

Kommentera

Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

WordPress.com Logo

Du kommenterar med ditt WordPress.com-konto. Logga ut / Ändra )

Twitter-bild

Du kommenterar med ditt Twitter-konto. Logga ut / Ändra )

Facebook-foto

Du kommenterar med ditt Facebook-konto. Logga ut / Ändra )

Google+ photo

Du kommenterar med ditt Google+-konto. Logga ut / Ändra )

Ansluter till %s