De fremveksten av kvanteberegning og dens implikasjoner for gjeldende krypteringsstandarder er velkjente. Men hvorfor skulle kvantedatamaskiner være spesielt flinke til å bryte kryptering? Svaret er en kjekk bit av matematisk sjonglering kalt Shor algoritme. Spørsmålet som fortsatt etterlater seg er: Hva er det denne algoritmen gjør som gjør at kvantedatamaskiner blir så mye bedre til å knekke kryptering? I denne videoen, YouTuber minuttfysikk forklarer det i sin tradisjonelle tegneseriestil.
"Kvanteberegning har potensialet til å gjøre det super, superenkelt å få tilgang til krypterte data - som å ha et lyssabel du kan bruke til å skjære gjennom enhver lås eller barriere, uansett hvor sterk," sier minutephysics. "Shors algoritme er det lyssabelet."
I følge videoen virker Shors algoritme ut av forståelsen at for et hvilket som helst tallpar, til slutt å multiplisere ett av dem med seg selv vil nå en faktor av det andre tallet pluss eller minus 1. Du gjetter altså på det første tallet og faktoriserer det. ut, legg til og trekk fra 1, til du kommer til det andre tallet. Det ville låse opp krypteringen (spesifikt RSA her, men det fungerer på noen andre typer) fordi vi da ville ha begge faktorene.
En grunn til at denne tilsynelatende enkle prosessen er avhengig av utviklingen av kraftige kvantedatamaskiner, er at det å finne den riktige kraften til å multiplisere det første tallet med for å finne en faktor av det andre tallet (N) ± 1 krever en enorm mengde forsøk. Krypteringsnøkkelen er et ganske langt tall og dermed kan kraften være alt fra 1 til millioner. Men brute force er ikke grunnen til at kvantedatamaskiner fungerer så bra her.
Supermakter av superposisjoner
Kort fortalt, takket være kvantesuperposisjonering, kan en kvantedatamaskin beregne mange svar for en enkelt inngang. Videoen sier imidlertid at du bare får ut ett svar om gangen, med sannsynligheter knyttet. For å løse det problemet, er regnestykket satt opp slik at feil svar forstyrrer hverandre, slik at bare det riktige svaret (eller i det minste en god gjetning) sannsynligvis blir utgitt. Det regnestykket, som fokuserer på å finne riktig kraft p, er Shors algoritme.
Det hele er ekstremt matematisk, med en assist fra Euklids algoritme, samt en kvante-Fourier-transformasjon som gjør en serie superposisjoner av superposisjoner til sinusbølger som enten konstruktivt (legger til hverandre) eller destruktivt forstyrrer - dvs. kansellerer hverandre. Videoen sier at du i hovedsak kan rigge den slik at bare 1/p er reddet, med alle de andre svarene destruktivt forstyrret av strid. Når du først er der, er det en tur i parken å finne p, noe som gjør det mye enklere å finne de to krypteringsfaktorene. Se hele videoen for flere detaljer, og for å kanskje føle deg litt smartere.
Det er forresten Peter Shor trives fortsatt, og hvis du er interessert i et dypdykk om hvordan han brøt Internett, her er en annen video der mannen selv forklarer hvordan han fant ut hans eponyme mesterverk.
