Introducere

Algoritmii cuantici oferă avantaje demonstrabile față de algoritmii clasici în modelul de interogare al computației. Dar ce se întâmplă cu un model de computație mai standard, în care intrările problemei sunt date explicit, nu sub forma unui oracol sau a unei cutii negre? Aceasta se dovedește a fi o întrebare mult mai dificilă, iar pentru a o aborda trebuie să stabilim mai întâi o fundație solidă pe care să ne bazăm investigația. Acesta este scopul principal al acestei lecții.

Vom începe prin a discuta costul computațional, atât pentru computațiile clasice, cât și pentru cele cuantice, și cum poate fi măsurat. Este o noțiune generală care poate fi aplicată unei game largi de probleme computaționale — dar pentru a păstra lucrurile simple, o vom examina în principal prin prisma teoriei computaționale a numerelor, care abordează sarcini computaționale ce le sunt probabil familiare majorității cititorilor, inclusiv aritmetica de bază, calculul celui mai mare divizor comun și factorizarea numerelor întregi. Deși teoria computațională a numerelor este un domeniu de aplicare restrâns, aceste probleme ilustrează bine problemele fundamentale (și se întâmplă să fie foarte relevante și pentru lecția care urmează acesteia).

Ne concentrăm pe algoritmi, nu pe hardware-ul în continuă îmbunătățire pe care aceștia rulează. În consecință, ne va interesa mai mult modul în care costul rulării unui algoritm se scalează pe măsură ce instanțele specifice ale problemei pe care le rezolvă cresc ca dimensiune, decât câte secunde, minute sau ore necesită o anumită computație. Ne concentrăm pe acest aspect al costului computațional recunoscând că algoritmii au o importanță fundamentală și vor fi implementați în mod natural pe instanțe tot mai mari ale problemelor, folosind hardware mai rapid și mai fiabil, pe măsură ce tehnologia se dezvoltă.

În final, vom aborda o sarcină de importanță critică, și anume rularea de computații clasice pe calculatoare cuantice. Motivul pentru care această sarcină este importantă nu este că sperăm să înlocuim calculatoarele clasice cu cele cuantice — ceea ce pare extrem de puțin probabil să se întâmple în curând, dacă se va întâmpla vreodată — ci pentru că deschide multe posibilități interesante pentru algoritmii cuantici. Mai concret, computațiile clasice care rulează pe calculatoare cuantice devin disponibile ca subrutine, valorificând efectiv decenii de cercetare și dezvoltare a algoritmilor clasici în urmărirea avantajelor computației cuantice.

Videoclipul lecției

În următorul videoclip, John Watrous te ghidează prin conținutul acestei lecții despre fundațiile algoritmilor cuantici. Alternativ, poți deschide videoclipul de pe YouTube pentru această lecție într-o fereastră separată. Descarcă slide-urile pentru această lecție.