Trettio år senare, en hastighetsökning för Quantum Factoring | Quanta Magazine

Peter Shor ville inte bryta internet. Men en algoritm som han utvecklade i mitten av 1990-talet hotade att göra just det. I en landmärke papperShor visade hur en hypotetisk dator som utnyttjade kvantfysikens egenheter kunde bryta in stora tal i sina primfaktorer mycket snabbare än någon vanlig klassisk maskin.

Resultatet fick konsekvenser långt bortom matematik. På den tiden kallade en viktig komponent av internetsäkerhet offentlig nyckelkryptografi förlitat sig på antagandet att faktorisering av stora tal är så beräkningsmässigt svårt att det i praktiken är omöjligt. Det antagandet stöder fortfarande vissa kritiska protokoll idag. Shors algoritm visade att den skulle misslyckas spektakulärt i en värld med kraftfulla kvantdatorer.

Under de senaste 30 åren har datavetare effektiviserat Shors algoritm som förberedelse för den dag då kvantteknologin mognar tillräckligt för att köra den. Men en ny variant, från New York Universitys datavetare Oded Regev, är snabbare i en fundamentalt ny mening. Det är det första som förbättrar förhållandet mellan storleken på det antal som faktoriseras och antalet kvantoperationer som krävs för att faktorisera det.

"Det är verkligen anmärkningsvärt att någon tydligen har kunnat förbättra komplexiteten i detta resultat många, många år senare," sa Ashley Montanaro, en kvantberäkningsforskare vid University of Bristol. "Det här är riktigt spännande."

Martin Ekerå, en kryptograf vid Svenska Kommunikationssäkerhetsmyndigheten, instämde i att Regevs papper är intressant men varnade för att det kommer att krävas ytterligare optimering för att slå den senaste tekniken i praktiken. "Shors ursprungliga algoritmer är redan förvånansvärt effektiva, så det är inte trivialt att göra stora förbättringar", skrev han i ett mejl.

Regev utvecklade sin nya algoritm genom att utöka Shors algoritm med tekniker från en gren av kryptografi som handlar om högdimensionell geometri.

"Jag skulle ha trott att alla algoritmer som fungerade med denna grundläggande kontur skulle vara dömda", säger Shor, en tillämpad matematiker nu vid Massachusetts Institute of Technology. "Men jag hade fel."

Att hitta faktorer

Kvantdatorer får sin kraft från det märkliga sättet de bearbetar information. Klassiska datorer använder bitar, som var och en alltid måste vara i ett av två tillstånd, märkta 0 och 1. Kvantbitar, eller "qubits", kan dessutom vara i kombinationer av deras 0- och 1-tillstånd - ett fenomen som kallas superposition. Det är också möjligt att coaxa flera qubits till ett kollektivt superpositionstillstånd: En två-qubit superposition har fyra komponenter som kan utföra olika beräkningar samtidigt, och antalet sådana komponenter växer exponentiellt när antalet qubits ökar. Det gör att kvantdatorer effektivt kan utföra exponentiellt många olika beräkningar parallellt.

Men det finns en hake: Att läsa resultatet av en beräkning utförd i överlagring avslöjar bara svaret på delen som beräknats av en slumpmässig komponent. För att skörda fördelarna med datoranvändning i superposition måste du på något sätt mappa slutresultatet till ett enklare tillstånd där det är säkert att läsa resultatet. Det är inte möjligt i de flesta fall, och till en början visste ingen hur man skulle få det att fungera för något problem. "Det var väldigt få människor som ens hade modet att tänka på kvantberäkningar," sa Regev.

Sedan 1994 läste Shor ett papper av datavetaren Daniel Simon som visade hur man kan utnyttja kvantsuperposition för att lösa ett konstruerat problem. Shor kom på hur man kunde utöka Simons resultat till ett mer allmänt och praktiskt problem som kallas periodfynd. En matematisk funktion sägs vara periodisk när dess utdata cyklar upprepade gånger genom samma värden när ingången ökar; längden på en enskild cykel kallas funktionens period.

För att hitta perioden för en given funktion med hjälp av en kvantdator, börja med att sätta upp en mycket stor superposition där varje komponent beräknar funktionens utdata för en annan ingång. Använd sedan Shors metod för att konvertera den stora överlagringen till ett enklare tillstånd och läs resultatet. Då kan en klassisk dator ta över och avsluta beräkningen snabbt. Sammantaget kör Shors periodhittande algoritm exponentiellt snabbare än något klassiskt alternativ eftersom den beräknar olika utdata från den periodiska funktionen samtidigt med hjälp av superposition.

När Shor letade efter tillämpningar för sin kvantperiod-hittande algoritm, återupptäckte han en tidigare känd men oklar matematisk teorem: För varje tal finns det en periodisk funktion vars perioder är relaterade till talets primtalsfaktorer. Så om det finns en siffra du vill ta hänsyn till kan du beräkna motsvarande funktion och sedan lösa problemet med hjälp av periodhittande - "exakt vad kvantdatorer är så bra på", sa Regev.

På en klassisk dator skulle detta vara ett plågsamt långsamt sätt att faktorisera ett stort antal - långsammare till och med än att försöka alla möjliga faktorer. Men Shors metod påskyndar processen exponentiellt, vilket gör period att hitta ett idealiskt sätt att konstruera en snabb kvantfaktoreringsalgoritm.

Shors algoritm var ett av några viktiga tidiga resultat som förvandlade kvantberäkningar från ett dunkelt delområde av teoretisk datavetenskap till det tumult det är idag. Men att omsätta algoritmen i praktiken är en skrämmande uppgift, eftersom kvantdatorer är notoriskt känsliga för fel: Förutom de qubits som krävs för att utföra sina beräkningar behöver de många andra göra extraarbete för att hålla dem från att misslyckas. A nyligen papper av Ekerå och Google-forskaren Craig Gidney uppskattar att användning av Shors algoritm för att faktorisera ett säkerhetsstandard 2,048 600-bitars nummer (cirka 20 siffror långt) skulle kräva en kvantdator med XNUMX miljoner qubits. Dagens toppmoderna maskiner har som mest några hundra.

Det är därför vissa kritiska internetprotokoll fortfarande förlitar sig på hur svårt det är att faktorisera stora siffror, men forskare vill inte bli alltför självbelåtna. Teoretisk och tekniska innovationer kan få ner den nödvändiga qubit-räkningen ytterligare, och det finns inga bevis för att Shors algoritm är optimal – det kan finnas en bättre kvantfaktoreringsalgoritm där ute som ingen har upptäckt.

Om så är fallet, sa Regev, "bör vi veta så tidigt som möjligt, innan det är för sent."

Lost in the Trees

Regev började sin akademiska karriär i slutet av 1990-talet, när kryptografer letade efter en ny form av kryptografi med offentlig nyckel som inte var sårbar för Shors algoritm. Det mest lovande tillvägagångssättet, kallas gitterbaserad kryptografi, förlitar sig på den uppenbara svårigheten med beräkningsproblem som involverar högdimensionella uppsättningar av punkter eller gitter. Ett sådant problem är besläktat med uppgiften att lokalisera trädet närmast en slumpmässig punkt i en skog.

"Om det är en hundradimensionell skog, då är det mycket mer komplicerat än om det är en tvådimensionell skog," sa Greg Kuperberg, en matematiker vid University of California, Davis.

Regev började studera gitterbaserad kryptografi som postdoc, till en början som angripare - han ville stresstesta det nya tillvägagångssättet genom att hitta svagheter som en kvantdator kunde utnyttja. Men han kunde inte göra några framsteg, och han undrade snart om det fanns en djupare anledning till det. 2005 hittade han ett sätt att omvandla dessa misslyckade attacker till ett form av gitterbaserad kryptografi överlägsen alla andra varianter.

"Oded är helt briljant med galler", sa Kuperberg.

Under årens lopp, när Regev lärde Shors algoritm till på varandra följande generationer av studenter, fann han sig själv att undra om de tekniker han hade använt för att attackera gitterbaserad kryptografi faktiskt kan visa sig vara användbara för att faktorisera algoritmer. Det beror på att ett steg i det sista, klassiska stadiet av Shors algoritm motsvarar att hitta den närmaste punkten i ett endimensionellt gitter. Det endimensionella problemet är trivialt enkelt, men likheten med det analoga problemet i hundratals dimensioner vars hårdhet ligger till grund för gitterbaserad kryptografi var omisskännlig.

"Om du är någon som gör galler som jag, tänker du," OK, det är något galler på gång här," sa Regev. "Men det var inte klart för mig hur jag skulle använda det." I flera år lekte han med andra idéer för nya kvantfaktoreringsalgoritmer, men han kom aldrig någonstans. Sedan i vintras återvände han till problemet och beslöt sig för att fastställa den där lockande kopplingen mellan factoring och gitterbaserad kryptografi. Den här gången fann han framgång.

Extra mått

Regev visste att han behövde börja med att generalisera den periodiska funktionen i hjärtat av Shors algoritm från en dimension till många dimensioner. I Shors algoritm innebär den funktionen att upprepade gånger multiplicera ett slumpmässigt tal, dubbat g, med sig själv. Men perioden för denna funktion — antalet gånger du måste multiplicera med g innan utmatningen av funktionen börjar upprepas — kan vara mycket stor, och det betyder att en kvantdator måste multiplicera stora tal i vissa komponenter av superpositionen den använder för att beräkna den periodiska funktionen. Dessa stora multiplikationer är den mest beräkningsmässigt kostsamma delen av Shors algoritm.

Den analoga tvådimensionella funktionen använder istället ett par tal, g₁ och g₂. Det handlar om att multiplicera g₁ med sig själv många gånger och sedan upprepade gånger multiplicera med g₂. Perioden för denna funktion är också tvådimensionell - den definieras av antalet g₁ multiplikationer och g₂ multiplikationer som tillsammans gör att funktionens utdata börjar upprepas. Det finns många olika kombinationer av g₁ och g₂ multiplikationer som kommer att göra susen.

Regev arbetade igenom de tekniska detaljerna för att generalisera algoritmen till ett godtyckligt antal dimensioner, inte bara två, men hans initiala resultat var inte uppmuntrande. För att beräkna den periodiska funktionen i många dimensioner skulle kvantdatorn fortfarande behöva multiplicera många tal tillsammans. Varje tal skulle inte behöva multipliceras lika många gånger som i det endimensionella fallet, men det fanns mer distinkta tal att multiplicera. Det hela verkade vara en tvätt.

"Du tänker:" Jättebra, jag gjorde bara allt i höga dimensioner, och det är exakt samma gångtid som Shors, " sa Regev. "Jag var fast med det ett tag." Sedan insåg han att han kunde komma runt problemet genom att ändra ordningen på multiplikationerna. Istället för att upprepade gånger fästa siffror på en enskild produkt som skulle växa successivt större under loppet av kvantberäkningen, började han med par av små tal, multiplicerade de resulterande produkterna tillsammans och fortsatte uppåt. Det totala antalet multiplikationer förändrades inte mycket, men nu involverar nästan alla relativt små tal, vilket gör beräkningen snabbare.

"Det gör hela skillnaden i världen," sa Vinod Vaikuntanathan, en kryptograf vid MIT.

Först såg det ut som om Regev precis hade ersatt ett problem med ett annat. Han hade påskyndat kvantberäkningen av den periodiska funktionen genom att öka antalet dimensioner, men den efterföljande klassiska beräkningen som krävdes för att extrahera perioden liknade nu att lokalisera den närmaste gitterpunkten i ett högdimensionellt utrymme - en uppgift som allmänt antas att vara hård. Analogin med gitterbaserad kryptografi som motiverade hans nya tillvägagångssätt verkade döma det till att misslyckas.

En kall morgon i mars innan en resa till ett seminarium vid Princeton University, fann Regev att han väntade på kollegan han samåkte med. "Jag kom tidigt, och han var sen att hämta bilen," sa han. Medan han satt och väntade kom plötsligt den sista pusselbiten till honom. "Det var det ögonblick då saker och ting föll på plats, men det höll på att baka ett tag."

Det hela kom ner till rätt antal dimensioner. När gitterdimensionen var för låg kunde hans algoritm inte dra full nytta av snabbheten från att multiplicera mindre tal. När den var för hög var kvantberäkningen snabb, men den klassiska delen krävde att lösa ett oöverkomligt hårt gitterproblem. Regev hade vetat från början att för att ha något hopp om framgång skulle han behöva jobba någonstans däremellan, men det var inte klart om det fanns en sweet spot. Den morgonen i mars insåg han hur han kunde justera detaljerna i algoritmen för att få den att köras snabbt i några dussin dimensioner.

Att skriva i sanden

Förbättringen var djupgående. Antalet elementära logiska steg i kvantdelen av Regevs algoritm är proportionell mot n^1.5 vid faktorisering av en n-bit nummer, snarare än n² som i Shors algoritm. Algoritmen upprepar den kvantdelen några dussin gånger och kombinerar resultaten för att kartlägga ett högdimensionellt gitter, från vilket den kan härleda perioden och faktorisera antalet. Så algoritmen som helhet kanske inte går snabbare, men att påskynda kvantdelen genom att minska antalet nödvändiga steg kan göra det lättare att omsätta det i praktiken.

Naturligtvis är tiden det tar att köra en kvantalgoritm bara en av flera överväganden. Lika viktigt är antalet qubits som krävs, vilket är analogt med det minne som krävs för att lagra mellanliggande värden under en vanlig klassisk beräkning. Antalet qubits som Shors algoritm kräver för att faktorisera en n-bitnummer är proportionell mot n, medan Regevs algoritm i sin ursprungliga form kräver ett antal qubits proportionellt mot n^1.5 — en stor skillnad för 2,048 XNUMX-bitars nummer.

Inom klassisk datoranvändning är hastighet vanligtvis en viktigare faktor än minne, eftersom klassiska bitar är extremt robusta: Du kan spara en fil på din dator och inte oroa dig för att den slumpmässigt ändras när du öppnar den igen senare. Kvantberäkningsforskare har inte alltid lika tur.

"Våra qubits försöker ständigt falla isär, och vi försöker hindra dem från att falla isär," sa Gidney. "Det är som att du försöker skriva i sanden och vinden blåser bort det." Det betyder att de extra qubits som krävs av Regevs algoritm kan vara en stor nackdel.

Men Regevs tidning är inte slutet på historien. För två veckor sedan hittade Vaikuntanathan och hans doktorand Seyoon Ragavan ett sätt att minska algoritmens minnesanvändning. Deras variant av Regevs algoritm, liksom Shors ursprungliga algoritm, kräver ett antal qubits proportionellt mot n snarare än n^1.5. Ekerå skrev i ett mejl att arbetet "för oss mycket närmare en implementering som skulle vara mer effektiv i praktiken."

Den bredare lärdomen av Regevs nya algoritm, bortom implikationerna för factoring, är att kvantberäkningsforskare alltid bör vara öppna för överraskningar, även i problem som har studerats i decennier.

"Denna variant av min algoritm var oupptäckt i 30 år och kom ut ur det blå," sa Shor. "Det finns förmodligen fortfarande massor av andra kvantalgoritmer att hitta."

Redaktörens anmärkning: Oded Regev får finansiering från Simons Foundation, som också finansierar denna redaktionellt oberoende tidning. Simons Foundation-finansieringsbeslut har inget inflytande på vår täckning. Mer information finns finns här.

Quanta genomför en serie undersökningar för att bättre betjäna vår publik. Ta vår datavetenskaplig läsarundersökning och du kommer att delta för att vinna gratis Quanta merch.