Kako kvantna fizika vodi do dešifriranja običajnih algoritmov

O vzpon kvantnega računalništva in njegove posledice ker so trenutni standardi šifriranja dobro znani. Toda zakaj bi morali biti kvantni računalniki posebej spretni pri razbijanju šifriranja? Odgovor je izvrstno matematično žongliranje, imenovano Shorjev algoritem. Vprašanje, ki še vedno ostaja, je: Kaj je tisto, kar počne ta algoritem, zaradi česar so kvantni računalniki toliko boljši pri razbijanju šifriranja? notri Ta video, YouTuber minutna fizika razloži v svojem tradicionalnem slogu risanke na tabli.

»Kvantno računanje ima potencial, da naredi super, super enostaven dostop do šifriranih podatkov – kot bi imeli svetlobni meč, s katerim lahko prerežete katero koli ključavnico ali oviro, ne glede na to, kako močna je,« pravi minutephysics. "Shorov algoritem je tisti svetlobni meč."

Glede na videoposnetek Shorov algoritem deluje na podlagi razumevanja, da bo za kateri koli par števil končno množenje enega od njiju samega doseglo faktor drugega števila plus ali minus 1. Tako ugibate prvo število in ga faktorizirate ven, seštevaj in odštevaj 1, dokler ne prideš do druge številke. To bi odklenilo šifriranje (natančneje RSA, vendar deluje naprej nekatere druge vrste), ker bi potem imeli oba faktorja.

Eden od razlogov, zakaj je ta navidezno preprost postopek odvisen od razvoja zmogljivih kvantnih računalnikov, je ta, da iskanje prave moči za množenje prvega števila, da bi našli faktor drugega števila (N) ± 1, zahteva ogromno poskusov. Šifrirni ključ je precej dolga številka, zato je moč lahko od 1 do milijonov. Toda surova sila ni razlog, zakaj kvantni računalniki pri nas delujejo tako dobro.

Supermoči superpozicij

Na kratko, zahvaljujoč kvantni superpoziciji lahko kvantni računalnik izračuna veliko odgovorov za en sam vnos. Vendar videoposnetek pravi, da dobite samo en odgovor naenkrat s priloženimi verjetnostmi. Da bi rešili to težavo, je izračun nastavljen tako, da se napačni odgovori medsebojno motijo, tako da bo verjetno izpisan samo pravilen odgovor (ali vsaj dobro ugibanje). Ta izračun, ki se osredotoča na iskanje prave moči p, je Shorov algoritem.

Vse je izjemno matematično, vključuje pomoč Evklidov algoritem, kot tudi kvantno Fourierjevo transformacijo, ki spremeni niz superpozicij superpozicij v sinusne valove, ki bodisi konstruktivno (se dodajajo drug drugemu) bodisi destruktivno interferirajo — tj. drug drugega izničijo. Videoposnetek pravi, da ga lahko v bistvu prilagodite tako, da samo 1/p je shranjen, vsi drugi odgovori pa so uničujoče moteni zaradi spora. Ko ste enkrat tam, se morate sprehoditi po parku p, zaradi česar je iskanje obeh dejavnikov šifriranja veliko lažje. Oglejte si celoten video za več podrobnosti in se morda počutite malo pametnejši.

Mimogrede, Peter Šor je še vedno uspeva, in če vas zanima podrobnejši potop o tem, kako je zlomil internet, je tukaj še en video, v katerem moški sam pojasnjuje, kako je ugotovil njegova istoimenska mojstrovina.