Tretti år senere, en hastighetsøkning for Quantum Factoring | Quanta Magazine

Peter Shor hadde ikke tenkt å bryte internett. Men en algoritme han utviklet på midten av 1990-tallet truet med å gjøre nettopp det. I en landemerke papir, viste Shor hvordan en hypotetisk datamaskin som utnyttet kvantefysikkens særegenheter kunne bryte store tall inn i sine primfaktorer langt raskere enn noen vanlig klassisk maskin.

Resultatet hadde implikasjoner langt utover matematikk. På den tiden kalte en viktig komponent av internettsikkerhet offentlig nøkkel kryptografi basert på antakelsen om at faktorisering av store tall er så beregningsmessig vanskelig at det faktisk er umulig. Denne antagelsen underbygger fortsatt noen kritiske protokoller i dag. Shors algoritme viste at den ville mislykkes spektakulært i en verden med kraftige kvante datamaskiner.

I løpet av de siste 30 årene har informatikere strømlinjeformet Shors algoritme som forberedelse til dagen da kvanteteknologien modnes nok til å kjøre den. Men en ny variant, fra New York University dataforsker Oded Regev, er raskere i en fundamentalt ny forstand. Det er den første som forbedrer forholdet mellom størrelsen på tallet som faktoriseres og antall kvanteoperasjoner som kreves for å faktorisere det.

"Det er virkelig bemerkelsesverdig at noen tilsynelatende har vært i stand til å forbedre kompleksiteten til dette resultatet mange, mange år senere," sa Ashley Montanaro, en kvantedataforsker ved University of Bristol. "Dette er virkelig spennende."

Martin Ekerå, en kryptograf ved den svenske nasjonale myndigheten for kommunikasjonssikkerhet, var enig i at Regevs artikkel er interessant, men advarte om at det å slå toppmoderne i praksis vil kreve ytterligere optimalisering. "Shors originale algoritmer er allerede overraskende effektive, så det er ikke trivielt å gjøre store forbedringer," skrev han i en e-post.

Regev utviklet sin nye algoritme ved å utvide Shors algoritme med teknikker fra en gren av kryptografi som omhandler høydimensjonal geometri.

"Jeg ville trodd at enhver algoritme som fungerte med denne grunnleggende oversikten ville være dømt," sa Shor, en anvendt matematiker nå ved Massachusetts Institute of Technology. "Men jeg tok feil."

Finne faktorer

Kvantedatamaskiner henter sin kraft fra den særegne måten de behandler informasjon på. Klassiske datamaskiner bruker biter, som hver alltid må være i en av to tilstander, merket 0 og 1. Kvantebiter, eller "qubits", kan i tillegg være i kombinasjoner av deres 0- og 1-tilstander - et fenomen som kalles superposisjon. Det er også mulig å lokke flere qubits til en kollektiv superposisjonstilstand: En to-qubit superposisjon har fire komponenter som kan utføre forskjellige beregninger samtidig, og antallet slike komponenter vokser eksponentielt ettersom antall qubits øker. Det gjør at kvantedatamaskiner effektivt kan utføre eksponentielt mange forskjellige beregninger parallelt.

Men det er en hake: Lese resultatet av en beregning utført i superposisjon avslører bare svaret på delen beregnet av én tilfeldig komponent. For å høste fordelene av databehandling i superposisjon, må du på en eller annen måte kartlegge sluttresultatet til en enklere tilstand der det er trygt å lese resultatet. Det er ikke mulig i de fleste tilfeller, og til å begynne med visste ingen hvordan de skulle få det til å fungere for noe problem. "Det var veldig få mennesker som til og med hadde mot til å tenke på kvanteberegninger," sa Regev.

Så i 1994 leste Shor et papir av informatikeren Daniel Simon som viste hvordan man utnytter kvantesuperposisjon for å løse et konstruert problem. Shor fant ut hvordan han kunne utvide Simons resultat til et mer generelt og praktisk problem kalt periodefunn. En matematisk funksjon sies å være periodisk når utgangen går gjentatte ganger gjennom de samme verdiene når inngangen øker; lengden av en enkelt syklus er kjent som funksjonens periode.

For å finne perioden til en gitt funksjon ved hjelp av en kvantedatamaskin, start med å sette opp en veldig stor superposisjon der hver komponent beregner funksjonens utgang for en annen inngang. Bruk deretter Shors metode for å konvertere den store superposisjonen til en enklere tilstand og les resultatet. På det tidspunktet kan en klassisk datamaskin ta over og fullføre beregningen raskt. Samlet sett kjører Shors periodesøkende algoritme eksponentielt raskere enn noe klassisk alternativ fordi den beregner forskjellige utdata fra den periodiske funksjonen samtidig ved å bruke superposisjon.

Mens Shor lette etter anvendelser for sin kvanteperiode-finnende algoritme, gjenoppdaget han en tidligere kjent, men obskur matematisk teorem: For hvert tall eksisterer det en periodisk funksjon hvis perioder er relatert til tallets primfaktorer. Så hvis det er et tall du vil faktorisere, kan du beregne den tilsvarende funksjonen og deretter løse problemet ved å bruke periodefinning - "nøyaktig hva kvantedatamaskiner er så gode på," sa Regev.

På en klassisk datamaskin ville dette være en smertelig treg måte å faktorisere et stort antall på - tregere til og med enn å prøve alle mulige faktorer. Men Shors metode fremskynder prosessen eksponentielt, noe som gjør perioden å finne en ideell måte å konstruere en rask kvantefaktoreringsalgoritme.

Shors algoritme var en av få viktige tidlige resultater som forvandlet kvanteberegning fra et uklar underfelt av teoretisk informatikk til juggernaut det er i dag. Men å utføre algoritmen i praksis er en skremmende oppgave, fordi kvantedatamaskiner er notorisk utsatt for feil: i tillegg til qubits som kreves for å utføre sine beregninger, trenger de mange andre som gjør ekstra arbeid for å forhindre at de mislykkes. EN nyere artikkel av Ekerå og Google-forskeren Craig Gidney anslår at bruk av Shors algoritme for å faktorisere et sikkerhetsstandard 2,048-bit tall (omtrent 600 sifre langt) ville kreve en kvantedatamaskin med 20 millioner qubits. Dagens topp moderne maskiner har på det meste noen hundre.

Det er derfor noen kritiske internettprotokoller fortsatt er avhengige av hvor vanskelig det er å faktorisere store tall, men forskere ønsker ikke å bli for selvtilfredse. teoretisk og teknologiske innovasjoner kan bringe den nødvendige qubit-tellingen ytterligere ned, og det er ingen bevis for at Shors algoritme er optimal - det kan være en bedre kvantefaktoreringsalgoritme der ute som ingen har oppdaget.

I så fall, sa Regev, "bør vi vite så tidlig som mulig, før det er for sent."

Lost in the Trees

Regev begynte sin akademiske karriere på slutten av 1990-tallet, da kryptografer lette etter en ny form for offentlig nøkkelkryptografi som ikke var sårbar for Shors algoritme. Den mest lovende tilnærmingen, kalt gitterbasert kryptografi, er avhengig av den tilsynelatende vanskeligheten ved beregningsproblemer som involverer høydimensjonale punkter med punkter, eller gitter. Et slikt problem er beslektet med oppgaven med å lokalisere treet nærmest et tilfeldig punkt i en skog.

"Hvis det er en hundredimensjonal skog, så er det mye mer komplisert enn om det er en todimensjonal skog," sa Greg Kuperberg, en matematiker ved University of California, Davis.

Regev begynte å studere gitterbasert kryptografi som postdoktor, først som angriper - han ønsket å stressteste den nye tilnærmingen ved å finne svakheter som en kvantedatamaskin kunne utnytte. Men han kunne ikke gjøre noen fremskritt, og han lurte snart på om det var en dypere grunn til det. I 2005 fant han en måte å omforme de mislykkede angrepene til en form for gitterbasert kryptografi overlegen alle andre varianter.

"Oded er helt genial med gitter," sa Kuperberg.

Gjennom årene, da Regev lærte Shors algoritme til påfølgende generasjoner av studenter, fant han seg selv på å lure på om teknikkene han hadde brukt til å angripe gitterbasert kryptografi faktisk kan vise seg å være nyttige i å ta fakturering av algoritmer. Det er fordi ett trinn i det siste, klassiske stadiet av Shors algoritme utgjør å finne det nærmeste punktet i et endimensjonalt gitter. Det endimensjonale problemet er trivielt enkelt, men likheten med det analoge problemet i hundrevis av dimensjoner hvis hardhet understøtter gitterbasert kryptografi var umiskjennelig.

"Hvis du er en som gjør gitter som meg, tenker du," OK, det er noe gitter på gang her," sa Regev. "Men det var ikke klart for meg hvordan jeg skulle bruke det." I årevis lekte han med andre ideer til nye kvantefaktoreringsalgoritmer, men han kom aldri noen vei. Så sist vinter kom han tilbake til problemet og bestemte seg for å finne den fristende forbindelsen mellom factoring og gitterbasert kryptografi. Denne gangen fant han suksess.

Ekstra dimensjoner

Regev visste at han måtte starte med å generalisere den periodiske funksjonen i hjertet av Shors algoritme fra én dimensjon til mange dimensjoner. I Shors algoritme involverer denne funksjonen gjentatte ganger å multiplisere et tilfeldig tall, kalt g, med seg selv. Men perioden for denne funksjonen - antall ganger du må multiplisere med g før utgangen av funksjonen begynner å gjenta — kan være veldig stor, og det betyr at en kvantedatamaskin må multiplisere store tall i noen komponenter av superposisjonen den bruker for å beregne den periodiske funksjonen. Disse store multiplikasjonene er den mest beregningsmessig kostbare delen av Shors algoritme.

Den analoge todimensjonale funksjonen bruker i stedet et tallpar, g₁ og g₂. Det innebærer å multiplisere g₁ med seg selv mange ganger og deretter gjentatte ganger gange med g₂. Perioden for denne funksjonen er også todimensjonal - den er definert av antallet g₁ multiplikasjoner og g₂ multiplikasjoner som sammen gjør at funksjonens utgang begynner å gjenta seg. Det finnes mange forskjellige kombinasjoner av g₁ og g₂ multiplikasjoner som vil gjøre susen.

Regev jobbet gjennom de tekniske detaljene for å generalisere algoritmen til et vilkårlig antall dimensjoner, ikke bare to, men de første resultatene hans var ikke oppmuntrende. For å beregne den periodiske funksjonen i mange dimensjoner, ville kvantedatamaskinen fortsatt måtte multiplisere mange tall sammen. Hvert tall trenger ikke å bli multiplisert så mange ganger som i endimensjonale tilfelle, men det var flere forskjellige tall å multiplisere. Det hele så ut til å være en vask.

"Du tenker: "Flott, jeg gjorde alt i høye dimensjoner, og det er nøyaktig samme kjøretid som Shors," sa Regev. "Jeg ble sittende fast med det en stund." Så skjønte han at han kunne komme rundt problemet ved å endre rekkefølgen på multiplikasjonene. I stedet for gjentatte ganger å sette tall på et enkelt produkt som ville vokse seg stadig større i løpet av kvanteberegningen, startet han med par med små tall, multipliserte de resulterende produktene sammen og fortsatte oppover. Det totale antallet multiplikasjoner endret seg ikke mye, men nå involverer nesten alle relativt små tall, noe som gjør beregningen raskere.

"Det utgjør hele forskjellen i verden," sa Vinod Vaikuntanathan, en kryptograf ved MIT.

Først så det ut som om Regev nettopp hadde byttet ut ett problem med et annet. Han hadde fremskyndet kvanteberegningen av den periodiske funksjonen ved å øke antall dimensjoner, men den påfølgende klassiske beregningen som kreves for å trekke ut perioden liknet nå på å lokalisere det nærmeste gitterpunktet i et høydimensjonalt rom - en oppgave som er allment antatt å være vanskelig. Analogien til gitterbasert kryptografi som motiverte hans nye tilnærming, så ut til å dømme den til å mislykkes.

En kald morgen i mars før en tur til et seminar ved Princeton University, fant Regev seg selv og ventet på kollegaen han samkjørte med. "Jeg kom tidlig, og han var sen med å hente bilen," sa han. Mens han satt og ventet, kom plutselig den siste brikken i puslespillet til ham. "Det var øyeblikket da ting falt på plass, men det bakte en stund."

Det hele kom ned til riktig antall dimensjoner. Når gitterdimensjonen var for lav, kunne ikke algoritmen hans dra full nytte av hastigheten ved å multiplisere mindre tall. Når den var for høy, var kvanteberegningen rask, men den klassiske delen krevde å løse et uoverkommelig hardt gitterproblem. Regev hadde visst fra begynnelsen at for å ha noe håp om suksess, måtte han jobbe et sted i mellom, men det var ikke klart om det fantes en sweet spot. Den morgenen i mars innså han hvordan han kunne finjustere detaljene i algoritmen for å få den til å kjøre raskt i noen dusin dimensjoner.

Skrive i sanden

Forbedringen var dyptgripende. Antall elementære logiske trinn i kvantedelen av Regevs algoritme er proporsjonalt med n^1.5 når man faktoriserer en n-bit nummer, i stedet for n² som i Shors algoritme. Algoritmen gjentar den kvantedelen noen dusin ganger og kombinerer resultatene for å kartlegge et høydimensjonalt gitter, hvorfra den kan utlede perioden og faktor tallet. Så algoritmen som helhet kjører kanskje ikke raskere, men å øke hastigheten på kvantedelen ved å redusere antall nødvendige trinn kan gjøre det lettere å implementere den.

Selvfølgelig er tiden det tar å kjøre en kvantealgoritme bare ett av flere hensyn. Like viktig er antallet qubits som kreves, som er analogt med minnet som kreves for å lagre mellomverdier under en vanlig klassisk beregning. Antall qubits som Shors algoritme krever for å faktorisere en n-bitnummer er proporsjonalt med n, mens Regevs algoritme i sin opprinnelige form krever et antall qubits proporsjonal med n^1.5 — en stor forskjell for 2,048-biters tall.

I klassisk databehandling er hastighet vanligvis en viktigere faktor enn minne, fordi klassiske biter er ekstremt robuste: Du kan lagre en fil på datamaskinen din og ikke bekymre deg for at den endres tilfeldig når du åpner den igjen senere. Kvantedataforskere er ikke alltid like heldige.

"Qubitene våre prøver hele tiden å falle fra hverandre, og vi prøver å stoppe dem fra å falle fra hverandre," sa Gidney. "Det er som om du prøver å skrive i sanden og vinden blåser det bort." Det betyr at de ekstra qubitene som kreves av Regevs algoritme kan være en stor ulempe.

Men Regevs papir er ikke slutten på historien. For to uker siden fant Vaikuntanathan og doktorgradsstudenten hans Seyoon Ragavan en måte å redusere algoritmens minnebruk. Deres variant av Regevs algoritme, som Shors originale algoritme, krever et antall qubits proporsjonal med n snarere enn n^1.5. Ekerå skrev i en e-post at arbeidet «bringer oss mye nærmere en implementering som ville vært mer effektiv i praksis».

Den bredere lærdommen av Regevs nye algoritme, utover implikasjonene for factoring, er at kvantedataforskere alltid bør være åpne for overraskelser, selv i problemer som har blitt studert i flere tiår.

"Denne varianten av algoritmen min var uoppdaget i 30 år og kom ut av det blå," sa Shor. "Det er sannsynligvis fortsatt mange andre kvantealgoritmer å finne."

Redaktørens notat: Oded Regev mottar midler fra Simons Foundation, som også finansierer dette redaksjonelt uavhengige magasinet. Simons Foundation-finansieringsbeslutninger har ingen innflytelse på dekningen vår. Flere detaljer er tilgjengelig her.

Quanta gjennomfører en serie undersøkelser for å tjene publikum bedre. Ta vår informatikk leserundersøkelse og du vil bli registrert for å vinne gratis Quanta varer.