Introducere
Algoritmul lui Grover este un algoritm cuantic pentru probleme de căutare nestructurată, care oferă o îmbunătățire pătratică față de algoritmii clasici. Ceea ce înseamnă acest lucru este că algoritmul lui Grover necesită un număr de operații de ordinul rădăcinii pătrate din numărul de operații necesare pentru a rezolva căutarea nestructurată clasic — ceea ce este echivalent cu a spune că algoritmii clasici pentru căutarea nestructurată trebuie să aibă un cost cel puțin de ordinul pătratului costului algoritmului lui Grover.
Algoritmul lui Grover, împreună cu extensiile și metodologia sa de bază, se dovedește a fi aplicabil pe scară largă, conducând la un avantaj pătratic pentru multe sarcini computaționale interesante care, la prima vedere, s-ar putea să nu pară probleme de căutare nestructurată.
Deși aplicabilitatea largă a tehnicii de căutare a lui Grover este convingătoare, trebuie recunoscut încă de la începutul lecției că avantajul pătratic pe care îl oferă pare puțin probabil să ducă în curând la un avantaj practic al computației cuantice față de cea clasică. Hardware-ul de calcul clasic este mult mai avansat decât hardware-ul de calcul cuantic — iar avantajul cuantic față de cel clasic oferit de algoritmul lui Grover va fi cu siguranță anulat de vitezele de ceas uluitoare ale computerelor clasice moderne pentru orice problemă de căutare nestructurată care ar putea fi rulată în mod realist în viitorul apropiat.
Pe măsură ce tehnologia de calcul cuantic avansează, totuși, algoritmul lui Grover ar putea avea potențial. Într-adevăr, unii dintre cei mai importanți și influenți algoritmi clasici descoperit vreodată, inclusiv transformata Fourier rapidă și sortarea rapidă (de exemplu, quicksort și merge sort), oferă un avantaj ușor sub pătratic față de abordările naive ale problemelor pe care le rezolvă. Diferența cheie aici, desigur, este că o tehnologie complet nouă (adică computația cuantică) este necesară pentru a rula algoritmul lui Grover. Deși această tehnologie se află încă în stadii incipiente în comparație cu calculul clasic, nu ar trebui să subestimăm atât de repede potențialul progreselor tehnologice care ar putea permite ca un avantaj pătratic al computației cuantice față de cea clasică să ofere într-o zi beneficii practice tangibile.
Video lecție
În următorul video, John Watrous te ghidează prin conținutul acestei lecții despre algoritmul lui Grover. Alternativ, poți deschide videoclipul YouTube pentru această lecție într-o fereastră separată. Descarcă slide-urile pentru această lecție.