Filmul lui Robert Redford a prezis bomba de calcul cuantică a lui Shor

Prima din două părți

Cu mult înainte ca oamenii de știință să vorbească mult despre asta, fanii lui Robert Redford au aflat despre puterea computerelor cuantice.

Era 1992. Un film prost numit Adidași a avertizat despre pericolele computerelor și cantitățile masive de informații criptate pe care le controlau. Redford și cohortele au achiziționat o cutie mică, deghizată ca un robot telefonic, care era capabil să decodeze toate datele clasificate computerizate din lume.

„Sistemele de criptare se bazează pe probleme matematice atât de complexe încât nu pot fi rezolvate fără o cheie”, a spus David Strathairn, jucând rolul unuia dintre complicii lui Redford. Cumva, un matematician pe nume Gunter Janek a programat un cip în interiorul cutiei robotului telefonic pentru a rezolva astfel de probleme.

Când Adidași a apărut în cinematografe, nimeni nu avea idee cum va funcționa un astfel de cip. Cu toate acestea, la mai puțin de doi ani mai târziu, un matematician de la Bell Labs a duplicat descoperirea ficției Gunter Janek. În urmă cu douăzeci de ani în această lună, Peter Shor și-a dat seama de matematica care făcea criptografia vulnerabilă la calculatoarele cuantice.

Desigur, pe atunci nu exista un computer cuantic. A fost doar o idee, discutată la începutul anilor 1980 de Richard Feynman și chiar înainte de atunci de Paul Benioff. Dacă ai putea valorifica puterea ciudățeniei cuantice, au presupus acei fizicieni, ai putea să faci calcul în moduri în care computerele clasice obișnuite nu ar putea. În 1985, fizicianul David Deutsch a subliniat că calculul cuantic ar putea fi foarte rapid – ar fi ca și cum ați calcula în mai multe universuri simultan. (De fapt, el a crezut că într-adevăr vei calcula în multe universuri simultan.)

Totul a fost foarte interesant, dar nimeni nu a crezut că computerele cuantice vor scoate IBM din afacere. În primul rând, nu era clar că acestea oferă avantaje pentru orice problemă practică anume. Vă puteți imagina probleme în care computerele cuantice ar fi rapide, dar nu foarte utile. Computerul dvs. cuantic ar putea funcționa de cinci ori mai rapid decât Mac-ul dvs., de exemplu, dar ar oferi răspunsul corect doar o cincime din timp. Trebuia să fii destul de norocos să fii în universul potrivit pentru a obține răspunsul corect.

Dar apoi Shor a aruncat o bombă. A găsit aplicația ucigașă a computerului cuantic: factoring.

Factorizarea este problema matematică complexă la care se face referire în Adidași. Factorizarea este baza pentru metoda de criptare standard utilizată pentru a codifica majoritatea comunicațiilor și date computerizate guvernamentale, militare și comerciale. Puteți cripta datele folosind un număr foarte lung, cu sute de cifre. Dar puteți sparge codul pentru a citi date criptate numai dacă cunoașteți cei doi factori primi care, atunci când sunt înmulțiți împreună, dau acel număr lung de codare.

Pentru numere mici, factorizarea este destul de ușoară. Luați 35, de exemplu. Este produsul a două numere prime, 5 și 7. Totuși, nu ar trebui să utilizați 35 pentru a crea un cod, deoarece factorii săi tocmai au fost dezvăluiți în propoziția anterioară. Sau cineva ar putea folosi un calculator.

Dar pentru numere cu câteva sute de cifre, găsirea celor două numere prime ar necesita câteva sute de supercalculatoare de câteva sute de ori mai mare decât vârsta universului. De aceea, toată lumea credea că criptarea standard este atât de sigură și asta Adidași era prost. Dar în filmul în sine, Gunter Janek a făcut aluzie la posibilitatea unei surprize matematice. „Există o posibilitate intrigantă pentru o abordare mult mai elegantă” pentru factorizarea numerelor mari, a spus Janek. „Ar fi o descoperire a proporțiilor gaussiene.”

În film, desigur, Janek a rezolvat problema factoringului și a fost ucis imediat. Un an și jumătate mai târziu, Shor a rezolvat aceeași problemă și a fost imediat imortalizat. (Probabil este un lucru bun pe care nu l-a văzut Adidași.)

Shor a început să lucreze la algoritmul său de factoring în 1993. În aprilie 1994, a ținut o conferință la Bell Labs despre un algoritm înrudit pentru calcularea logaritmilor. Câteva zile mai târziu, a descoperit cheia factoringului cuantic. Curând, lucrarea sa care descrie algoritmul de factoring a circulat pe internet.

Lucrarea lui Shor a arătat cum să combinați metodele matematice obișnuite pentru găsirea factorilor primi cu un truc care ar putea fi efectuat doar pe un computer cuantic. A implicat găsirea perioadei unei funcții periodice – o expresie matematică care își repetă răspunsul la anumite intervale sau perioade. În formularea lui Shor a problemei, este (relativ) ușor să găsiți factorii primi dacă cunoașteți perioada funcției. Dar ar dura o veșnicie pentru a găsi acea perioadă cu computerele obișnuite.

Cu un computer cuantic, totuși, ai putea rezolva problema mult mai rapid – poate zile, ore sau minute, în loc de miliarde de ani. Și cea mai bună parte a fost că ai foarte probabil să obții răspunsul corect. De fapt, un computer cuantic ar putea genera miliarde de răspunsuri, dar aproape toate ar fi șterse de interferența cuantică, un fel ca modul în care căștile cu anulare a zgomotului atenuează undele sonore. Răspunsul rămas a furnizat perioada, care putea fi apoi folosită pentru a calcula numerele prime.

Odată ce lucrarea lui Shor a fost distribuită pe scară largă, secretul a fost descoperit și a Adidași scenariul se profila, cu excepția unei mici probleme. Nici IBM, nici Apple și nici nimeni altcineva nu au vândut computere cuantice.

„În prezent, nimeni nu știe cum să construiască un computer cuantic”, a scris Shor în lucrarea sa din 1994. „Se speră că această lucrare va stimula cercetarea asupra faptului că este fezabil să construim unul.”

A făcut, desigur. În ultimele două decenii, calculul cuantic a devenit unul dintre cele mai fierbinți subiecte atât în ​​fizica cuantică, cât și în informatică. Au fost construite calculatoare cuantice rudimentare și au luat în considerare cu succes numere precum 15 și 21. (Pretențiile de succes cu numere mai mari au fost contestate.) Aceasta este destul de departe de Adidași scenariu, dar în viața reală progresul este de obicei mai lent decât în ​​filme.

Dar algoritmul lui Shor nu a inspirat doar un nou tip de tehnologie. A generat un impuls intelectual pentru un nou domeniu de studiu științific numit teoria informației cuantice. La câteva săptămâni după revelația lui Shor, liderii domeniului informatic cuantic în curs de dezvoltare s-au întâlnit la Santa Fe pentru a reflecta la ideea că realitatea cuantică a fost construită pe o fundație informațională. Am fost acolo. Așa că nu rata partea 2.

Urmărește-mă pe Twitter: @tom_siegfried