_ Calculatoarele cuantice pot rezolva optimizarea combinatorie problemele mai ușor decât metodele convenționale, cercetările arată

Problema vânzătorului ambulant este considerată un prim exemplu de problemă de optimizare combinatorie. Acum, o echipă din Berlin condusă de fizicianul teoretician Prof. Dr. Jens Eisert de la Freie Universität Berlin și HZB a arătat că o anumită clasă de astfel de probleme poate fi de fapt rezolvată mai bine și mult mai rapid cu calculatoarele cuantice decât cu metodele convenționale.

Lucrarea echipei este publicată în revista Science Advances.

Computerele cuantice folosesc așa-numiții qubiți, care nu sunt nici zero, nici unu, ca în circuitele logice convenționale, dar pot lua orice valoare între ele. Acești qubiți sunt realizați de atomi, ioni sau circuite supraconductoare foarte răcite și este încă foarte complex din punct de vedere fizic să construiești un computer cuantic cu mulți qubiți. Cu toate acestea, metodele matematice pot fi deja folosite pentru a explora ce ar putea realiza computerele cuantice tolerante la erori în viitor.

„Există o mulțime de mituri despre asta și, uneori, o anumită cantitate de aer cald și hype. Dar am abordat problema cu rigurozitate, folosind metode matematice și am obținut rezultate solide pe acest subiect. Mai presus de toate, am clarificat în ce sens pot exista avantaje", spune prof. dr. Eisert, care conduce o cercetare comună. grup de la Freie Universität Berlin și Helmholtz-Zentrum Berlin.

Binecunoscuta problemă a vânzătorului ambulant servește ca exemplu principal: un călător trebuie să viziteze o serie de orașe și apoi să se întoarcă în orașul său natal. Care este cel mai scurt traseu? Deși această problemă este ușor de înțeles, ea devine din ce în ce mai complexă pe măsură ce numărul orașelor crește, iar timpul de calcul explodează. Problema vânzătorului ambulant reprezintă un grup de probleme de optimizare care au o importanță economică enormă, fie că implică rețele de cale ferată, logistică sau optimizarea resurselor. Pot fi găsite soluții suficient de bune folosind metode de aproximare.

Echipa condusă de Eisert și colegul său Jean-Pierre Seifert a folosit acum metode pur analitice pentru a evalua modul în care un computer cuantic cu qubiți ar putea rezolva această clasă de probleme, un experiment de gândire clasic cu pix și hârtie și multă experiență.

„Pur și simplu presupunem, indiferent de realizarea fizică, că există destui qubiți și ne uităm la posibilitățile de a efectua operațiuni de calcul cu aceștia.” explică Vincent Ulitzsch, Ph.D. student la Universitatea Tehnică din Berlin.

Procedând astfel, echipa a dezvăluit asemănări cu o problemă binecunoscută în criptografie, adică criptarea datelor.

„Ne-am dat seama că am putea folosi algoritmul Shor pentru a rezolva o subclasă a acestor probleme de optimizare”, spune Ulitzsch. Aceasta înseamnă că timpul de calcul nu mai „explodează” cu numărul de orașe (exponențial, 2N), ci crește doar polinomial, adică cu Nx, unde x este o constantă. Soluția obținută în acest fel este și calitativ mult mai bună decât soluția aproximativă folosind algoritmul convențional.

„Am arătat că pentru o clasă specifică, dar foarte importantă și relevantă practic de probleme de optimizare combinatorie, calculatoarele cuantice au un avantaj fundamental față de computerele clasice pentru anumite cazuri ale problemei”, spune Eisert.

(Fluierul)