Metoda de cautare cuantica echivalenta ca eficienta cu algoritmul Google !

Motorul de cautare Google se bazeaza pe un algoritm cunoscut sub numele de „PageRank”. Principiul de functionare este destul de usor de înteles, dar implementarea acestuia este dificila. Parcurgerea si verificarea tuturor paginilor aflate pe internet este o problema complexa. Evaluarea site-urilor web in scopul maparii inseamna evaluarea acestora din perspectiva structurilor de date tip graph, unde entitati precum paginile web sunt reprezentate prin noduri, iar legaturile dintre acestea sunt reprezentate prin linii conectoare.

Unii algoritmi de explorare graph de calitate joasa se pot compara cu nivelul NP-hard, o clasă de complexitate computatională care cuprinde probleme probabil imposibil de rezolvat chiar si de cele mai puternice computere existente in prezent (complexitatea respectivelor probleme este atat de mare incat se considera ca indiferent de puterea de calcul rezolvarea lor este relativ imposibila). Luand in considerare un graph neexplorat, este foarte dificil sa prezinti modul cel mai eficient de a vizita toate nodurile si legaturile, prin urmare solutia posibila ar fi sa exploram graph-ul in mod aleatoriu, folosind metoda numita „random walk”.

„Random walk” permite algoritmului de cautare sa controleze caracteristicile geometrice neobisnuite ale graph-ului, ceea ce ar putea impiedica o cautare directionata. O noua metoda, care exploatează fizica cuantică pentru a imbunatati strategia de parcurgere a algoritmului „random walk” a fost implementata cu succes conform unei lucrari recent publicata in revista Physical Review A. Considerand particulele subatomice „cercetatori/cautatori”, s-a obtinut posibilitatea explorarii graph-ului intrun mod aleatoriu, exploatand in acelasi timp efectele de interferenta intre particule. Simplu spus, exploratorii graph-ului sunt deopotriva aleatorii precum si constienti de amplitudinea graph-ului.

Exploatarea efectelor cuantice in scopul obtinerii randomizarii este evidenta, fizica cuantica implicand o doza mare de incertitudine si de informatii incomplete. Exista totusi o problema in utilizarea efectelor cuantice pentru explorarea graph-urilor, unitaritatea, un principiu care stabileste faptul ca sistemele cuantice pot evolua in timp doar simetric.
Practic pot fi parcurse doar graph-uri numite nedirectionate, in care legaturile dintre noduri sunt bidirecționale (simetrice).

Totusi, fizicieni implementatori ai noii metode au reusit sa gaseasca o metoda ocolitoare a acestei restrictii prin exploatarea unui alt tip de simetrie avand legatura cu modul în care paritatea unui sistem cuantic evolueaza in timp. In unele dintre experimente, metoda cuantica s-a dovedit a fi mai eficienta decat „PageRank”, de exemplu in identificarea unor seturi echivalente de noduri dintrun graph. Bineinteles, desi rezultatele sunt uimitoare lumea cuantica ramane un domeniu in mare parte neinteles si dificil de cercetat.

Lasă un comentariu