Computere cuantice

imaginea utilizatorului Serafim

Faptul că o problemă de factorizare a cărei complexitate în momentul de față crește exponențial se transformă într-o problemă de complexitate polinomială folosind algoritmul lui Shor și computere cuantice ar putea fi o mare problemă pentru criptografia clasică folosită la ora actuală.

Primul calculator cuantic disponibil comercial a fost D-Wave One și este produs de compania canadiană D-Wave. Este o "cutie" ecranată care ocupă 10 metri pătrați și conține un procesor cu 128 de qubiți răciți criogenic. Conform cotației firmei producătoare, instalarea durează cam 4 săptămâni, calibrarea cam 6, instruirea personalului fiind aparent partea cea mai simplă pentru că durează doar 2-3 zile. Sistemul vine cu Python, C++, SQL, Mathlab și Java și prin urmare ar trebui să fie simplu de programat cam pentru orice fel de aplicație. Prețul este pe măsură și se ridică la 10 milioane de dolari.

Acest computer, primul computer cuantic comercial, a fost scos pe piață acum mai mult de un an de zile, în mai 2011. Dacă ar fi să considerăm că legea lui Moore se va aplica și pentru tehnologia IT cuantică, am putea spune că cel mai târziu prin 2030, noile calculatoare vor ajunge să coste cam 500-1000 de dolari, adică prețul aproximativ al unui PC de uz casnic în ziua de azi și se vor apropia sau vor depăși capacități de 1Mqubit.

Acuma, ca să lămurim un lucru pentru cei care ar vedea 128 qubit și ar spune "cam puțin". Un qubit poate stoca pe lângă "0" sau "1", orice superpoziție între cele două stări. Altfel spus, cantitatea de informație care poate fi stocată într-un qubit este teoretic nelimitată sau mai exact, încă nu cunoaștem limitele la care putem ajunge deși cel mai probabil vor avea de a face cu constanta lui Planck și constanta lui Boltzmann.

Să presupunem că ar fi doar 128 de bit. În acest caz am putea număra pâna la 2^128-1 sau aproximativ 3.4*10^38. În cazul în care stocăm pe lângă “1” și “0” încă 6 superpoziții, având 8 stări posibile, pe 128 de qubit putem număra până la 8^128-1 sau cam 3.9*10^115. Totuși puterea mare de calcul nu vine de la modul de stocare al informației ci de la noile moduri de lucru care pot fi abordate. Entanglementul cuantic (care a fost tradus în limba română în mai multe feluri) este fenomenul prin care două sau mai multe molecule pot să aibă stările cuplate între ele în așa fel încât ceea ce se întâmplă uneia se întâmplă și celorlalte.

Toate acestea, așa cum spuneam și la începutul articolului, înseamnă moartea criptografiei în forma actuală. Paradigmele care erau considerate imbatabile până acum, devin joacă de copii. Deja se vorbește despre criptografia post-cuantică, despre criptografie bazată pe latici, criptografie multivariată și alte variante rezistente la criptanaliză cuantică.

La ritmul în care se schimbă și se dezvoltă tehnologiile în sfera computerelor, nu va trece multă vreme până când veți citi la știrile de dimineață despre o tehnologie care va fi deja depășită până la lăsarea serii. Sau ar mai spune unii, dacă ai clipit, ai ratat o generație. Sau poate nu.

Share this

Comentarii

Cateva idei insailate pe marginea abordarii coantice

Buna ziua,

Stiu ca nu ne cunoastem decat foarte tangential. Sambata care a trecut am avut ocazia sa va vad pentru prima data dar din pacate toate lucrurile s-au petrecut atat de rapid incat am ratat foarte multe, printre care si o discutie cu dumneavoastra. Asa ca o sa imi permit sa vorbesc ca intre oameni onesti cu aceleasi preocupari, pornind de la premisa ca aceste preocupari comune sunt de ajuns pentru a indrazni.
Ieri ati intrebat unul din vorbitori ce parere are despre impactul calculatoarelor cuantice. Raspunsul nu m-a multumit pe mine cel putin (mai ales pentru ca stiu cine a raspuns si stiu ca putea sa raspunda mult mult mai bine, dar emotiile .. ). Am sa incerc eu un raspuns la intrebarea dumneavoastra, asadar.
Pe foarte scurt eu cred ca nu va schimba mai nimic. In orice caz nu ceva substantial. Raspunsul mai detailat urmeaza.
Am sa trec peste dificultatile de a face un asemenea calculator cat de cat stabil si cat de cat utilizabil asa incat sa il putem incadra, destul de generos zic eu, in categoria comodity, pentru ca el sa se poata ulitiza pe scara larga. Pentru asta probabil va trebui sa mai asteptam vre-o 10-30 de ani. Am sa trec si peste dificultatile de a reaseza algoritmii pe o alta baza, dificultati care vor face viata mai interesanta inginerilor de atunci, asa sper cel putin. Am sa ma rezum numai la aspectul computational.
Astfel. Clasa problemelor pe care astfel de calculatoare le pot rezolva se stie ca acopera P, se stie ca acopera in consecinta si, o parte cel putin din NP. Dar aceasta nu ajuta la nimic. Pentru ca tot din NP fac parte si problemele NP-complete, care de fapt sunt cele mai multe si cele mai interesante. Nu se stie precis, dar in lumea stintifica se crede ca nu exista nici o sansa ca acestea sa poata fi acoperite cu aceasta abordare si toate rezutatele care aduc un progres musca din sansele ca sa intample asa ceva. Si nici nu mai aduc in discutie problemele NP-hard care nu sunt NP-complete. Acolo e foarte dureros, pentru ca nu stim mai nimic.
In ceea ce priveste factorizarea intregilor, se stie ca este problema NP. Adevarat. Dar a fi problema NP nu inseamna decat ca o solutie a problemei poate fi verificata in timp polinomial. Nu indica nimic din dificultatea problemei, aceasta putand varia intre toate limitele posibile. Nu se cunoaste decat ca cel mai probabil factorizarea este o problema in P, iar atata vreme cat P!=NP, nu inseamna decat ca are o forma mai dificil de exprimat si atat.
In concluzie eu cred ca singurul efect vizibil ar fi acela ca algoritmii bazati pe factorizare vor fi pusi la sertar si se vor folosi alte familii de algoritmi bazati pe alte idei (de altfel e o intreaga literatura despre asa ceva).
Nu sunt un expert in criptografie/securitate/etc, deci parerile mele sunt doar cele ale unui inginer oarecum pasionat de computer science in formele sale de baza, ca sa spun asa.
In alta ordine de idei sunt foarte curios despre opiniile dumneavoastra despre TechO(n). Stiu eu unul ca se putea mai mult, si mai stiu ca daca as putea sa fac totul de la capat (in ceea ce ma priveste), as fi facut destul de multe lucruri altfel. Dar nu imi dau seama deloc de cum s-a vazut din afara si ar si foarte interesat sa aud.
Cu stima,
Aurelian Tutuianu

imaginea utilizatorului Serafim

Da, este la început

Vă mulțumesc că ați îndrăznit :)

Da, toată chestia cu computerele cuantice este într-un stadiu destul de infantil deocamdată. Probabil vor mai trece ceva ani până când să vedem măcar câte unul în fiecare centru mare universitar. Eu însă sunt ceva mai optimist în ce privește timpul de desfășurare al evenimentelor și nu cred că va dura 30 de ani pentru dezvoltarea unor algoritmi destul de serioși ca să fie folosiți de marile situri în mod curent. Am auzit ceva discuții despre Google și "image recognition" dus undeva la următorul nivel cu ceva algoritmi cuantici dar încă este în stadiu incipient, de cercetare, de încercări, ca mai tot acest câmp de lucru. Cam asta a fost ideea de la care am pornit când am pus întrebarea aceea la TechO(n)

Da, știu că problemele de complexitate sunt uneori mai greu de definit și/sau de rezolvat. Cursul de algoritmi al domnului Dorel Lucanu a fost dintre preferatele mele la facultate. Fain și jocul de semne cu O(n) la TechO(n), cel puțin mie mi-a sugerat complexitate liniară, nu sunt sigur că asta a fost intenția.

Poate ne vom vedea față către față să apucăm să stăm mai pe îndelete de vorbă despre mai multe lucruri în care găsim interese comune. Nu mă dau în lături de la a învăța lucruri noi, de la a cimenta cunoștințe mai vechi sau chiar de la a face schimb de idei noi.

General despre TechO(n), pe scurt, am scris la http://tech.serafimpantea.ro/2012/10/20/si-fost-amazon-techon-prima-editie

Feedback-ul referitor la fiecare talk în parte prefer să-l dau personal, nu în public :)