Tredive år senere, et hastighedsboost for kvantefaktorer | Quanta Magasinet

Peter Shor satte sig ikke for at bryde internettet. Men en algoritme, han udviklede i midten af ​​1990'erne, truede med at gøre netop det. I en milepæl papirShor viste, hvordan en hypotetisk computer, der udnyttede kvantefysikkens særheder, kunne bryde store tal ind i deres primfaktorer langt hurtigere end nogen almindelig klassisk maskine.

Resultatet havde implikationer langt ud over matematik. På det tidspunkt kaldte en vital komponent af internetsikkerhed kryptografi med offentlig nøgle påberåbt sig den antagelse, at faktorisering af store tal er så beregningsmæssigt vanskeligt, at det faktisk er umuligt. Denne antagelse understøtter stadig nogle kritiske protokoller i dag. Shor's algoritme viste, at den ville fejle spektakulært i en verden med kraftfulde kvantecomputere.

I de sidste 30 år har dataloger strømlinet Shors algoritme som forberedelse til den dag, hvor kvanteteknologien modnes nok til at køre den. Men en ny variant, fra New York University datalog Oded Regev, er hurtigere i en grundlæggende ny forstand. Det er den første til at forbedre forholdet mellem størrelsen af ​​det tal, der faktoriseres, og antallet af kvanteoperationer, der kræves for at faktorisere det.

"Det er virkelig bemærkelsesværdigt, at nogen tilsyneladende har været i stand til at forbedre kompleksiteten af ​​dette resultat mange, mange år senere," sagde Ashley Montanaro, en kvantecomputerforsker ved University of Bristol. "Det her er virkelig spændende."

Martin Ekerå, en kryptograf ved den svenske nationale kommunikationssikkerhedsmyndighed, var enig i, at Regevs papir er interessant, men advarede om, at det vil kræve yderligere optimering at slå det nyeste i praksis. "Shors originale algoritmer er allerede overraskende effektive, så det er ikke trivielt at lave større forbedringer," skrev han i en e-mail.

Regev udviklede sin nye algoritme ved at udvide Shors algoritme med teknikker fra en gren af ​​kryptografi, der beskæftiger sig med højdimensionel geometri.

"Jeg ville have troet, at enhver algoritme, der arbejdede med denne grundlæggende skitse, ville være dødsdømt," sagde Shor, en anvendt matematiker nu ved Massachusetts Institute of Technology. "Men jeg tog fejl."

At finde faktorer

Kvantecomputere henter deres kraft fra den ejendommelige måde, de behandler information på. Klassiske computere bruger bits, som hver især altid skal være i en af ​​to tilstande, mærket 0 og 1. Kvantebits, eller "qubits", kan desuden være i kombinationer af deres 0- og 1-tilstande - et fænomen kaldet superposition. Det er også muligt at lokke flere qubits til en kollektiv superpositionstilstand: En to-qubit superposition har fire komponenter, der kan udføre forskellige beregninger samtidigt, og antallet af sådanne komponenter vokser eksponentielt, efterhånden som antallet af qubits stiger. Det gør det muligt for kvantecomputere effektivt at udføre eksponentielt mange forskellige beregninger parallelt.

Men der er en fangst: Læsning af resultatet af en beregning udført i superposition afslører kun svaret på delen beregnet af en tilfældig komponent. For at høste fordelene ved computing i superposition skal du på en eller anden måde kortlægge slutresultatet til en enklere tilstand, hvor det er sikkert at læse resultatet. Det er ikke muligt i de fleste tilfælde, og i første omgang vidste ingen, hvordan man fik det til at fungere for noget problem. "Der var meget få mennesker, der overhovedet havde modet til at tænke på kvanteberegninger," sagde Regev.

Så i 1994 læste Shor et papir af datalogen Daniel Simon, der viste, hvordan man udnytter kvantesuperposition til at løse et konstrueret problem. Shor fandt ud af, hvordan man udvidede Simons resultat til et mere generelt og praktisk problem kaldet periodefund. En matematisk funktion siges at være periodisk, når dens output cykler gentagne gange gennem de samme værdier, når inputtet stiger; længden af ​​en enkelt cyklus er kendt som funktionens periode.

For at finde perioden for en given funktion ved hjælp af en kvantecomputer, start med at opsætte en meget stor superposition, hvor hver komponent beregner funktionens output for et andet input. Brug derefter Shors metode til at konvertere den store superposition til en enklere tilstand og aflæse resultatet. På det tidspunkt kan en klassisk computer tage over og afslutte beregningen hurtigt. Samlet set kører Shor's periodefindende algoritme eksponentielt hurtigere end noget klassisk alternativ, fordi den beregner forskellige output af den periodiske funktion samtidigt ved hjælp af superposition.

Da Shor ledte efter anvendelser til sin kvanteperiode-findende algoritme, genopdagede han en tidligere kendt, men obskur matematisk sætning: For hvert tal eksisterer der en periodisk funktion, hvis perioder er relateret til tallets primfaktorer. Så hvis der er et tal, du vil medregne, kan du beregne den tilsvarende funktion og derefter løse problemet ved hjælp af periodefinding - "præcis hvad kvantecomputere er så gode til," sagde Regev.

På en klassisk computer ville dette være en pinefuldt langsom måde at faktorisere et stort tal på - langsommere endda end at prøve alle mulige faktorer. Men Shors metode fremskynder processen eksponentielt, hvilket gør periodesøgning til en ideel måde at konstruere en hurtig kvantefaktoreringsalgoritme.

Shor's algoritme var et af nogle få vigtige tidlige resultater, der transformerede kvantecomputere fra et obskurt underfelt af teoretisk datalogi til den juggernaut, den er i dag. Men at omsætte algoritmen i praksis er en skræmmende opgave, fordi kvantecomputere notorisk er modtagelige for fejl: Ud over de qubits, der kræves for at udføre deres beregninger, har de brug for mange andre, der gør. ekstra arbejde for at forhindre dem i at fejle. EN nyligt papir af Ekerå og Google-forskeren Craig Gidney anslår, at brug af Shor's algoritme til at faktorisere et sikkerhedsstandard 2,048-bit tal (ca. 600 cifre langt) ville kræve en kvantecomputer med 20 millioner qubits. Dagens topmoderne maskiner har højst et par hundrede.

Det er derfor, nogle kritiske internetprotokoller stadig er afhængige af, hvor svært det er at faktorisere store tal, men forskere ønsker ikke at blive for selvtilfredse. Teoretisk og teknologiske innovationer kunne bringe den nødvendige qubit-optælling yderligere ned, og der er intet bevis for, at Shors algoritme er optimal - der kan være en bedre kvantefaktoreringsalgoritme derude, som ingen har opdaget.

Hvis det er tilfældet, sagde Regev, "bør vi vide det så tidligt som muligt, før det er for sent."

Fortabt i træerne

Regev begyndte sin akademiske karriere i slutningen af ​​1990'erne, da kryptografer søgte efter en ny form for offentlig nøglekryptografi, der ikke var sårbar over for Shors algoritme. Den mest lovende tilgang, kaldet gitterbaseret kryptografi, er afhængig af den tilsyneladende vanskelighed ved beregningsproblemer, der involverer højdimensionelle arrays af punkter eller gitter. Et sådant problem er beslægtet med opgaven med at lokalisere træet tættest på et tilfældigt punkt i en skov.

"Hvis det er en hundrededimensionel skov, så er det meget mere kompliceret, end hvis det er en todimensionel skov," sagde Greg Kuperberg, en matematiker ved University of California, Davis.

Regev begyndte at studere gitterbaseret kryptografi som postdoc, først som angriber - han ville stressteste den nye tilgang ved at finde svagheder, som en kvantecomputer kunne udnytte. Men han kunne ikke gøre fremskridt, og han spekulerede hurtigt på, om der var en dybere grund til det. I 2005 fandt han en måde at omforme disse mislykkede angreb til en form for gitterbaseret kryptografi bedre end alle andre varianter.

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

I årenes løb, da Regev lærte Shor's algoritme til successive generationer af studerende, fandt han sig selv i tvivl om, hvorvidt de teknikker, han havde brugt til at angribe gitterbaseret kryptografi, faktisk kunne vise sig at være nyttige til faktorisering af algoritmer. Det skyldes, at et trin i den sidste klassiske fase af Shors algoritme svarer til at finde det nærmeste punkt i et endimensionelt gitter. Det endimensionelle problem er trivielt nemt, men ligheden med det analoge problem i hundredvis af dimensioner, hvis hårdhed understøtter gitterbaseret kryptografi, var umiskendelig.

"Hvis du er en, der laver gitter som mig, tænker du," OK, der foregår noget gitter her," sagde Regev. "Men det var ikke klart for mig, hvordan jeg skulle bruge det." I årevis legede han med andre ideer til nye kvantefaktoreringsalgoritmer, men han kom aldrig nogen vegne. Sidste vinter vendte han så tilbage til problemet og besluttede at fastlægge den fristende forbindelse mellem factoring og gitterbaseret kryptografi. Denne gang fik han succes.

Ekstra dimensioner

Regev vidste, at han skulle starte med at generalisere den periodiske funktion i hjertet af Shors algoritme fra én dimension til mange dimensioner. I Shors algoritme involverer denne funktion gentagne gange at gange et tilfældigt tal, kaldet g, med sig selv. Men perioden for denne funktion — antallet af gange, du skal gange med g før outputtet af funktionen begynder at gentage - kan være meget stort, og det betyder, at en kvantecomputer skal gange store tal i nogle komponenter af den superposition, den bruger til at beregne den periodiske funktion. Disse store multiplikationer er den mest beregningsmæssigt omkostningstunge del af Shors algoritme.

Den analoge todimensionelle funktion bruger i stedet et par tal, g₁ , g₂. Det involverer multiplikation g₁ med sig selv mange gange og derefter gentagne gange gange med g₂. Perioden for denne funktion er også todimensionel - den er defineret af antallet af g₁ multiplikationer og g₂ multiplikationer, der tilsammen gør, at funktionens output begynder at gentage sig. Der er mange forskellige kombinationer af g₁ , g₂ multiplikationer, der vil gøre tricket.

Regev gennemarbejdede de tekniske detaljer for at generalisere algoritmen til et vilkårligt antal dimensioner, ikke kun to, men hans første resultater var ikke opmuntrende. For at beregne den periodiske funktion i mange dimensioner, ville kvantecomputeren stadig skulle gange mange tal sammen. Hvert tal behøvede ikke at blive ganget så mange gange som i det endimensionelle tilfælde, men der var flere forskellige tal at gange. Det hele så ud til at være en vask.

"Du tænker, 'Fantastisk, jeg lavede bare alt i høje dimensioner, og det er nøjagtig den samme køretid som Shor's," sagde Regev. "Jeg sad fast med det i et stykke tid." Så indså han, at han kunne komme uden om problemet ved at ændre rækkefølgen af ​​multiplikationerne. I stedet for gentagne gange at sætte tal på et enkelt produkt, der ville vokse sig gradvist større i løbet af kvanteberegningen, startede han med par af små tal, multiplicerede de resulterende produkter sammen og fortsatte opad. Det samlede antal multiplikationer ændrede sig ikke meget, men nu involverer næsten alle af dem relativt små tal, hvilket gør beregningen hurtigere.

"Det gør hele forskellen i verden," sagde Vinod Vaikuntanathan, en kryptograf ved MIT.

Først så det ud som om, at Regev lige havde erstattet et problem med et andet. Han havde fremskyndet kvanteberegningen af ​​den periodiske funktion ved at øge antallet af dimensioner, men den efterfølgende klassiske beregning, der krævedes for at udtrække perioden, svarede nu til at lokalisere det nærmeste gitterpunkt i et højdimensionelt rum - en opgave, der i vid udstrækning menes at være hård. Analogien til gitterbaseret kryptografi, der motiverede hans nye tilgang, så ud til at dømme den til at mislykkes.

En kold morgen i marts før en tur til et seminar på Princeton University, stod Regev i at vente på den kollega, han kørte sammen med. "Jeg ankom tidligt, og han kom for sent til at hente bilen," sagde han. Mens han sad og ventede, kom den sidste brik i puslespillet pludselig til ham. "Det var det øjeblik, hvor tingene faldt på plads, men det bagte i et stykke tid."

Det hele kom ned til det rigtige antal dimensioner. Når gitterdimensionen var for lav, kunne hans algoritme ikke drage fuld fordel af hastigheden ved at gange mindre tal. Når det var for højt, var kvanteberegningen hurtig, men den klassiske del krævede at løse et uoverkommeligt hårdt gitterproblem. Regev havde fra begyndelsen vidst, at for at have et håb om succes, skulle han arbejde et sted midt imellem, men det var ikke klart, om der fandtes en sweet spot. Den morgen i marts indså han, hvordan han kunne justere detaljerne i algoritmen for at få den til at køre hurtigt i et par dusin dimensioner.

At skrive i sandet

Forbedringen var dyb. Antallet af elementære logiske trin i kvantedelen af ​​Regevs algoritme er proportional med n^1.5 ved faktorisering af en n-bit nummer, i stedet for n² som i Shors algoritme. Algoritmen gentager den kvantedel et par dusin gange og kombinerer resultaterne for at kortlægge et højdimensionelt gitter, hvorfra den kan udlede perioden og faktor tallet. Så algoritmen som helhed kører måske ikke hurtigere, men at fremskynde kvantedelen ved at reducere antallet af nødvendige trin kan gøre det lettere at omsætte det i praksis.

Selvfølgelig er den tid, det tager at køre en kvantealgoritme, blot en af ​​flere overvejelser. Lige så vigtigt er antallet af nødvendige qubits, som er analogt med den hukommelse, der kræves for at gemme mellemværdier under en almindelig klassisk beregning. Antallet af qubits, som Shor's algoritme kræver for at faktorisere en n-bit nummer er proportional med n, mens Regevs algoritme i sin oprindelige form kræver et antal qubits proportionalt med n^1.5 — en stor forskel for 2,048-bit tal.

I klassisk databehandling er hastighed normalt en vigtigere overvejelse end hukommelse, fordi klassiske bits er ekstremt robuste: Du kan gemme en fil på din computer og ikke bekymre dig om, at den tilfældigt ændrer sig, når du åbner den igen senere. Kvantecomputerforskere er ikke altid så heldige.

"Vores qubits forsøger konstant at falde fra hinanden, og vi forsøger at forhindre dem i at falde fra hinanden," sagde Gidney. "Det er som om du prøver at skrive i sandet, og vinden blæser det væk." Det betyder, at de ekstra qubits, der kræves af Regevs algoritme, kan være en stor ulempe.

Men Regevs papir er ikke slutningen på historien. For to uger siden fandt Vaikuntanathan og hans kandidatstuderende Seyoon Ragavan en måde at reducere algoritmens hukommelsesbrug på. Deres variant af Regevs algoritme, ligesom Shors originale algoritme, kræver et antal qubits proportionalt med n snarere end n^1.5. Ekerå skrev i en e-mail, at arbejdet "bringer os meget tættere på en implementering, der ville være mere effektiv i praksis."

Den bredere lektie af Regevs nye algoritme, ud over implikationerne for factoring, er, at kvantecomputerforskere altid bør være åbne over for overraskelser, selv i problemer, der er blevet undersøgt i årtier.

"Denne variant af min algoritme var uopdaget i 30 år og kom ud af det blå," sagde Shor. "Der er sandsynligvis stadig masser af andre kvantealgoritmer at finde."

Redaktørens note: Oded Regev modtager midler fra Simons Foundation, som også finansierer dette redaktionelt uafhængige blad. Simons Fondens finansieringsbeslutninger har ingen indflydelse på vores dækning. Flere detaljer er tilgængelig her.

Quanta gennemfører en række undersøgelser for bedre at kunne betjene vores publikum. Tag vores datalogisk læserundersøgelse og du vil være med til at vinde gratis Quanta merch.