O strategie cuantică ar putea verifica soluțiile la probleme de nerezolvat – în teorie

Visele informaticienilor au dezvăluit puterea mecanicii cuantice.

Imaginați-vă că întâlniți ființe omnisciente care pretind că au soluția unei probleme complexe pe care niciun computer nu ar putea să o rezolve vreodată. Probabil că ai fi pierdut să verifici răspunsul. Dar acum, oamenii de știință informatic raportează că mecanica cuantică oferă o modalitate de a verifica rapid soluțiile la o clasă incredibil de largă de probleme, inclusiv unele care sunt imposibil de rezolvat în primul rând.

Deși rezultatul nu are aplicații practice evidente, ramificațiile sale teoretice au avut un efect de undă, răspunzând la întrebări nerezolvate din fizică și matematică, raportează oamenii de știință într-o lucrare publicată pe 13 ianuarie pe arXiv.org. „Are atât de multe implicații pentru toate aceste domenii. Este o afacere uriașă, indiferent de modul în care te uiți la asta”, spune informaticianul teoretic Scott Aaronson de la Universitatea Texas din Austin, care nu a fost implicat în noul studiu.

În informatică, unele probleme sunt greu de rezolvat, dar au soluții ușor de verificat. Deci, cercetătorii clasifică întrebările în funcție de cât de greu este pentru computere să verifice răspunsurile pretinse.

Pe cont propriu, un computer poate merge doar atât de departe în verificarea soluțiilor. Dar oamenii de știință au câteva trucuri în mânecă. Ei inventează scenarii în care un „demonstrator” – un computer sau o persoană care pretinde că are o soluție la o problemă – este presărat cu întrebări de către persoana care încearcă să verifice soluția, „verificatorul”.

Imaginați-vă, de exemplu, că aveți un prieten care pretinde că a dedus cum să faceți diferența dintre Pepsi și Coca-Cola, deși nu puteți distinge între cele două. Pentru a confirma această afirmație, tu – verificatorul – ai putea să pregătești o ceașcă de Pepsi sau Coca-Cola și să-l întrebi pe prietenul tău – dovatorul – despre care este. Dacă prietenul tău oferă în mod constant răspunsul corect la astfel de întrebări, ai fi convins că dilema de identificare a cola a fost rezolvată.

Cunoscută ca o dovadă interactivă, această strategie poate dezvălui informații suplimentare care le-ar permite oamenilor de știință să verifice soluții la probleme de care un computer este prea dificil pentru a convinge oamenii de știință în mod independent. Dovezi interactive și mai puternice implică mai mulți doveditori. Acest scenariu seamănă un pic cu un interogatoriu al poliției a doi suspecți, izolați în camere separate, care nu își pot coordona răspunsurile pentru a păcăli un anchetator.

Clasa de probleme care pot fi verificate în acest fel este „mare, dar nu ridicol de mare”, spune coautorul studiului Thomas Vidick, un informatician teoretic la Caltech. Pentru a verifica soluțiile la o varietate și mai mare de probleme, oamenii de știință își pot imagina că adaugă o altă întorsătură: cei care dovedesc au în comun o conexiune cuantică numită întanglement, care face ca două obiecte aparent independente să se comporte în moduri corelate (SN: 4/25/18).

Până acum, nu se știa câte probleme erau verificabile cu întanglementarea cuantică. Noul rezultat dezvăluie că este „un număr incredibil de mare de probleme”, spune Aaronson.

Acest grup uriaș se numește probleme recursive enumerabile sau RE. „Conține toate problemele care pot fi rezolvate de computere și apoi unele”, spune coautorul Henry Yuen, un informatician la Universitatea din Toronto. „Este o chestie nebună.” Este „și apoi unii” care este cu adevărat uluitor. Niciun computer nu ar fi capabil să rezolve aceste probleme definitiv, dar dacă două ființe omnisciente încurcate ar avea o soluție, te-ar putea convinge că este corect. Desigur, implementarea tehnicii de verificare în lumea reală este făcută neplauzibilă din cauza lipsei de ființe omnisciente care să ofere răspunsurile.

Rezultatul este rezumat în egalitatea succintă, MIP* = RE, unde MIP* înseamnă Multi-prover Interactive Proof cu entanglement cuantic. Fiecare problemă din RE este și în MIP* și invers.

Deși nu a fost încă revizuit de colegi, studiul este luat foarte în serios, spune informaticianul Lance Fortnow de la Institutul de Tehnologie Illinois din Chicago. „Aș paria că probabil că este corect… Nu există niciun motiv să credem că este greșit.”

Iar rezultatul este o triplă amenințare: a rezolvat trei probleme deodată. Pe lângă faptul că a dezvăluit că MIP* este egal cu RE, a răspuns simultan la alte două întrebări deschise, una la fizică și una la matematică. Primul este un puzzle de fizică cuantică numită problema lui Tsirelson, care întreabă dacă tipurile de corelații cuantice care ar putea fi produse folosind o cantitate infinită de întanglement ar putea fi aproximate cu o cantitate foarte mare, dar finită de întanglement. Răspunsul, dezvăluie studiul, este nu: uneori nici măcar nu poți să te apropii de a reproduce încâlcirea infinită cu încâlcirea finită.

În matematică, studiul stabilește conjectura de încorporare a lui Connes, o idee de lungă durată care este echivalentă din punct de vedere matematic cu problema lui Tsirelson. De asemenea, se ocupă de întrebarea dacă o aproximare finită poate replica în mod necesar ceva cu adevărat infinit. Din nou, răspunsul este nu.

„Este o realizare incredibilă; este cu adevărat interesant”, spune matematicianul William Slofstra de la Universitatea din Waterloo din Canada. „Este o împlinire a ceva ce ne-am dorit de mult timp.”