În ce cazuri specifice computerele cuantice depășesc omologii lor clasici? Este o întrebare greu de răspuns, în parte pentru că computerele cuantice de astăzi sunt lucruri capricioase, pline de erori care le pot îngrămădi și le strica calculele.
Într-o măsură, desigur, au făcut-o deja. În 2019, fizicienii de la Google a anunțat că au folosit o mașină de 53 de qubiți pentru a realiza supremația cuantică, o piatră de hotar simbolică care marchează punctul în care un computer cuantic face ceva dincolo de atingerea oricărui algoritm practic clasic. asemănător demonstrații de către fizicienii de la Universitatea de Știință și Tehnologie din China a urmat curând.
Dar, în loc să se concentreze pe un rezultat experimental pentru o anumită mașină, informaticienii vor să știe dacă algoritmii clasici vor fi capabili să țină pasul pe măsură ce computerele cuantice devin din ce în ce mai mari. „Speranța este ca în cele din urmă partea cuantică să se retragă complet până când nu mai există concurență”, a spus Scott Aaronson, un informatician la Universitatea din Texas, Austin.
La această întrebare generală este încă greu de răspuns, din nou, în parte din cauza acelor erori plictisitoare. (Viitoarele mașini cuantice își vor compensa imperfecțiunile folosind o tehnică numită corectarea cuantică a erorilor, dar acea capacitate este încă departe.) Este posibil să obțineți avantajul cuantic scontat chiar și cu erori necorectate?
Majoritatea cercetătorilor au bănuit că răspunsul a fost nu, dar nu l-au putut dovedi pentru toate cazurile. Acum, într-o hârtie postat pe serverul de preprint arxiv.org, o echipă de informaticieni a făcut un pas major către o dovadă cuprinzătoare că corectarea erorilor este necesară pentru un avantaj cuantic de durată în eșantionarea aleatorie a circuitelor - problema personalizată pe care Google a folosit-o pentru a arăta supremația cuantică. Au făcut acest lucru prin dezvoltarea unui algoritm clasic care poate simula experimente aleatorii de eșantionare a circuitelor atunci când sunt prezente erori.
„Este un rezultat teoretic frumos”, a spus Aaronson, subliniind că noul algoritm nu este practic util pentru simularea unor experimente reale precum cel de la Google.
În experimentele de eșantionare aleatoare a circuitelor, cercetătorii încep cu o serie de qubiți sau biți cuantici. Apoi, aceștia manipulează aleatoriu acești qubiți cu operațiuni numite porți cuantice. Unele porți fac ca perechile de qubiți să se încurce, ceea ce înseamnă că au o stare cuantică și nu pot fi descrise separat. Straturile repetate de porți aduc qubiții într-o stare de încurcătură mai complicată.
Pentru a afla despre acea stare cuantică, cercetătorii măsoară apoi toți qubiții din matrice. Acest lucru face ca starea lor cuantică colectivă să se prăbușească într-un șir aleatoriu de biți obișnuiți - 0 și 1. Numărul de rezultate posibile crește rapid odată cu numărul de qubiți din matrice: cu 53 de qubiți, ca în experimentul Google, este de aproape 10 cvadrilioane. Și nu toate șirurile sunt la fel de probabile. Eșantionarea dintr-un circuit aleatoriu înseamnă repetarea acestor măsurători de mai multe ori pentru a construi o imagine a distribuției probabilității care stă la baza rezultatelor.
Întrebarea avantajului cuantic este pur și simplu aceasta: este greu să imitem acea distribuție a probabilității? cu un algoritm clasic care nu folosește nicio încurcătură?
În 2019, cercetători s-au dovedit că răspunsul este da pentru circuitele cuantice fără erori: este într-adevăr greu de simulat în mod clasic un experiment de eșantionare aleatoare a circuitelor atunci când nu există erori. Cercetătorii au lucrat în cadrul teoriei complexității computaționale, care clasifică dificultatea relativă a diferitelor probleme. În acest domeniu, cercetătorii nu tratează numărul de qubiți ca pe un număr fix, cum ar fi 53. „Gândește-te la asta ca n, care este un număr care va crește”, a spus Aram Harrow, fizician la Institutul de Tehnologie din Massachusetts. „Atunci vrei să întrebi: facem lucruri în care efortul este exponențial n sau polinom în n?” Aceasta este modalitatea preferată de a clasifica timpul de rulare al unui algoritm - când n crește suficient de mare, un algoritm care este exponențial în n rămâne cu mult în urma oricărui algoritm care este polinom n. Când teoreticienii vorbesc despre o problemă dificilă pentru calculatoarele clasice, dar ușoară pentru computerele cuantice, ei se referă la această distincție: cel mai bun algoritm clasic ia timp exponențial, în timp ce un computer cuantic poate rezolva problema în timp polinomial.
Cu toate acestea, lucrarea din 2019 a ignorat efectele erorilor cauzate de porțile imperfecte. Acest lucru a lăsat deschis cazul unui avantaj cuantic pentru eșantionarea aleatorie a circuitelor fără corectarea erorilor.
Dacă vă imaginați creșterea continuă a numărului de qubiți așa cum fac teoreticienii complexității și, de asemenea, doriți să luați în considerare erorile, trebuie să decideți dacă veți continua să adăugați mai multe straturi de porți - crescând adâncimea circuitului, așa cum spun cercetătorii. Să presupunem că păstrați adâncimea circuitului constantă la, de exemplu, trei straturi relativ puțin adânci, pe măsură ce creșteți numărul de qubiți. Nu veți obține prea multă încurcătură, iar rezultatul va fi în continuare supus simulării clasice. Pe de altă parte, dacă creșteți adâncimea circuitului pentru a ține pasul cu numărul tot mai mare de qubiți, efectele cumulate ale erorilor de poartă vor spăla încurcarea, iar ieșirea va deveni din nou ușor de simulat în mod clasic.
Dar între ele se află o zonă Goldilocks. Înainte de noua lucrare, era încă o posibilitate ca avantajul cuantic să supraviețuiască aici, chiar dacă numărul de qubiți creștea. În acest caz cu adâncime intermediară, creșteți adâncimea circuitului extrem de lent pe măsură ce numărul de qubiți crește: chiar dacă ieșirea va fi degradată în mod constant de erori, ar putea fi totuși greu de simulat clasic la fiecare pas.
Noua lucrare închide această lacună. Autorii au derivat un algoritm clasic pentru simularea eșantionării aleatoare a circuitelor și au demonstrat că timpul său de rulare este o funcție polinomială a timpului necesar pentru a rula experimentul cuantic corespunzător. Rezultatul creează o legătură teoretică strânsă între viteza abordărilor clasice și cuantice ale eșantionării aleatoare a circuitelor.
Noul algoritm funcționează pentru o clasă majoră de circuite cu adâncime intermediară, dar ipotezele sale subiacente se defectează pentru unele mai puțin adânci, lăsând un mic decalaj în care metodele clasice de simulare eficiente sunt necunoscute. Dar puțini cercetători își păstrează speranța că eșantionarea aleatorie a circuitelor se va dovedi greu de simulat în mod clasic în această fereastră subțire rămasă. „Îi dau cote destul de mici”, a spus Bill Fefferman, un informatician la Universitatea din Chicago și unul dintre autorii lucrării de teorie din 2019.
Rezultatul sugerează că eșantionarea aleatorie a circuitelor nu va aduce un avantaj cuantic prin standardele riguroase ale teoriei complexității computaționale. În același timp, ilustrează faptul că algoritmii polinomiali, pe care teoreticienii complexității îi numesc fără discriminare eficienți, nu sunt neapărat rapizi în practică. Noul algoritm clasic devine progresiv mai lent pe măsură ce rata de eroare scade, iar la ratele scăzute de eroare obținute în experimentele de supremație cuantică, este mult prea lent pentru a fi practic. Fără erori, se defectează cu totul, astfel încât acest rezultat nu contrazice nimic pe care cercetătorii știau despre cât de greu este să simuleze în mod clasic eșantionarea aleatorie a circuitelor în cazul ideal, fără erori. Sergio Boixo, fizicianul care conduce cercetarea Google privind supremația cuantică, spune că consideră lucrarea „mai mult ca o confirmare plăcută a eșantionării aleatoare a circuitelor decât orice altceva”.
Într-un anumit punct, toți cercetătorii sunt de acord: noul algoritm subliniază cât de crucială va fi corectarea erorilor cuantice pentru succesul pe termen lung al calculului cuantic. „Aceasta este soluția, la sfârșitul zilei”, a spus Fefferman.
