O strategie cuantică ar putea verifica soluțiile la problemele nerezolvabile - în teorie · BOOMBOX

O strategie cuantică ar putea verifica soluțiile la problemele nerezolvabile – în teorie

quantumcomputer

Zilele informaticienilor din calculator au relevat puterea mecanicii cuantice.

Imaginați-vă că întâlniți ființe omnisciente care pretind că au soluția unei probleme complexe pe care nici un computer nu le-ar putea rezolva vreodată. Probabil că veți pierde răspunsul. Acum, informaticienii raportează că mecanica cuantică oferă o modalitate de a verifica rapid soluțiile unei clase incredibil de largi de probleme, inclusiv unele care sunt imposibil de rezolvat în primul rând.

Deși rezultatul nu are aplicații practice evidente, ramificările sale teoretice au avut un efect de ondulare, răspunzând la întrebări nesoluționate în fizică și matematică, relatează oamenii de știință într-o lucrare publicată pe 13 ianuarie la arXiv.org. „Are atât de multe implicații pentru toate aceste domenii. Este o afacere uriașă, indiferent de modul în care o privești ”, spune informaticianul teoretician Scott Aaronson de la Universitatea din 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 calculatorul să verifice răspunsurile presupuse.

De unul singur, un computer poate merge doar atât de departe în verificarea soluțiilor. Dar oamenii de știință au câteva trucuri până la mânecă. Ele conturează scenarii în care un „prover” – un computer sau o persoană care pretinde că are o soluție la o problemă – este plin de întrebări de către persoana care încearcă să verifice soluția, „verificatorul”.

Imaginați-vă, de exemplu, că aveți un prieten care susține că a dedus cum să spună diferența dintre Pepsi și Coke, chiar dacă nu puteți face distincția între cei doi. Pentru a confirma această afirmație, dvs. – verificatorul – puteți pregăti o ceașcă de Pepsi sau Coke și să vă întrebați prietenul – proverul – pe care se află. Dacă prietenul tău oferă în mod constant răspunsul corect la astfel de întrebări, ai fi convins că problema de identificare a cola a fost rezolvată.

Cunoscută drept dovadă interactivă, această strategie poate dezvălui informații suplimentare care ar permite oamenilor de informatică să verifice soluții la probleme care sunt prea dificile pentru un computer să-i convingă pe oamenii de știință în mod independent. Dovezi interactive încă mai puternice implică mai mulți probatori. Acest scenariu seamănă 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 investigator.

Clasa problemelor care pot fi verificate în acest fel este „mare, dar nu ridicol de mare”, spune coautorul studiului Thomas Vidick, un om de informatică teoretic la Caltech. Pentru a verifica soluțiile pentru o varietate și mai mare de probleme, oamenii de știință își pot imagina adăugând o altă răsucire: Probatorii au o conexiune cuantică numită înțelegere, care determină comportarea a două obiecte aparent independente în mod corelat (SN: 4/25/18).

Până în prezent, nu se știa câte probleme erau verificabile în privința înțelegerii cuantice. Noul rezultat dezvăluie că este „un număr incredibil de mare de probleme”, spune Aaronson.

Acest grup uriaș se numește recursiv enumerabile sau probleme RE. „Conține toate problemele care pot fi rezolvate de calculatoare și apoi de unele”, spune coautorul Henry Yuen, un om de informatică de la Universitatea din Toronto. „Este o nebunie”. Este „și apoi unii” care este cu adevărat neplăcut. Niciun computer nu ar putea să rezolve aceste probleme direct, dar dacă două ființe omnisciente încurcate ar avea o soluție, te-ar putea convinge că este corect. Desigur, aplicarea tehnicii de verificare în lumea reală este făcută imposibilă de lipsa ființelor omnisciente de a oferi răspunsurile.

Rezultatul este rezumat în egalitatea succintă, MIP * = RE, în care MIP * înseamnă Proof Interactive Prover Multi cu înțelegere cuantică. Fiecare problemă din RE este, de asemenea, în MIP *, și invers.

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

Iar rezultatul este o triplă amenințare: a rezolvat trei probleme simultan. Pe lângă dezvăluirea că MIP * este egal cu RE, acesta a răspuns simultan la alte două întrebări deschise, una în fizică și una în 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 înțelegeri ar putea fi aproximate cu o cantitate foarte mare, dar finită de înțelegere. Răspunsul, dezvăluie studiul, este nu. Uneori, nu puteți chiar să vă apropiați de a reproduce o înțelegere infinită cu o înțelegere finită.

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

„Este o realizare incredibilă; este foarte interesant „, spune matematicianul William Slofstra de la Universitatea din Waterloo din Canada. „Este o realizare a ceea ce am dorit de mult timp.”