În 1994, un matematician și-a dat seama cum să facă un computer cuantic să facă ceva ce nici un computer clasic obișnuit nu ar putea. Lucrarea a arătat că, în principiu, o mașină bazată pe regulile mecanicii cuantice ar putea împărți eficient un număr mare în factorii săi primi - o sarcină atât de dificilă pentru un computer clasic, încât formează baza pentru o mare parte a securității internetului de astăzi.
A urmat un val de optimism. Poate, s-au gândit cercetătorii, vom fi capabili să inventăm algoritmi cuantici care pot rezolva o gamă largă de probleme diferite.
Dar progresul s-a blocat. „A fost o traiectorie cam dezagreabilă”, a spus Ryan O'Donnell de la Universitatea Carnegie Mellon. „Oamenii au spus: „Este uimitor, sunt sigur că vom obține tot felul de alți algoritmi uimitoare”. Nu." Oamenii de știință au descoperit accelerații dramatice doar pentru o singură clasă restrânsă de probleme dintr-un set standard numit NP, ceea ce înseamnă că aveau soluții eficiente verificabile - cum ar fi factoring.
Așa a fost cazul timp de aproape trei decenii. Apoi, în aprilie, cercetătorii inventat un tip fundamental nou de problemă pe care un computer cuantic ar trebui să o poată rezolva exponențial mai rapid decât unul clasic. Acesta implică calcularea intrărilor unui proces matematic complicat, bazat exclusiv pe ieșirile sale amestecate. Încă nu a fost stabilit dacă problema este singură sau este prima dintr-o nouă frontieră a multor altele.
„Există un sentiment de entuziasm”, a spus Vinod Vaikuntanathan, un informatician la Institutul de Tehnologie din Massachusetts. „Mulți oameni se gândesc la ce altceva este acolo.”
Oamenii de știință în domeniul informaticii încearcă să înțeleagă ce fac mai bine calculatoarele cuantice prin studierea modelelor matematice care le reprezintă. Adesea, ei își imaginează un model de computer cuantic sau clasic asociat cu o mașină de calcul idealizată numită oracol. Oracolele sunt ca niște simple funcții matematice sau programe de calculator, care preiau o intrare și scuipă o ieșire predeterminată. Ei ar putea avea un comportament aleatoriu, emitând „da” dacă intrarea se încadrează într-un anumit interval aleator (să zicem, de la 12 la 67) și „nu” dacă nu. Sau ar putea fi periodice, astfel încât o intrare între 1 și 10 returnează „da”, 11 până la 20 produce „nu”, 21 până la 30 produce „da” din nou și așa mai departe.
Să presupunem că ai unul dintre aceste oracole periodice și nu știi perioada. Tot ce poți face este să îi alimentezi cu numere și să vezi ce iese. Cu aceste constrângeri, cât de repede ar putea un computer să găsească perioada? În 1993, Daniel Simon, pe atunci de la Universitatea din Montreal, a descoperit că un algoritm cuantic ar putea calcula răspunsul la o problemă strâns legată exponențial mai rapid decât orice algoritm clasic.
Rezultatul i-a permis lui Simon să determine unul dintre primele indicii despre unde se poate aștepta o superioritate dramatică pentru computerele cuantice. Dar când și-a prezentat lucrarea la o conferință principală, a fost respinsă. Lucrarea a interesat, totuși, un membru junior al comitetului de program al conferinței - Peter Shor, care la acea vreme se afla la Bell Laboratories din New Jersey. Shor a continuat să descopere că ar putea adapta algoritmul lui Simon pentru a calcula perioada unui oracol, dacă ar avea unul. Apoi și-a dat seama că ar putea adapta algoritmul încă o dată, pentru a rezolva o ecuație care se comportă similar unui oracol periodic: ecuația care descrie factorizarea, care este periodică.
Rezultatul lui Shor a fost istoric. Algoritmul cuantic pe care l-a descoperit ar putea reduce rapid numerele gigantice în factorii lor primi constitutivi, ceva ce nu poate face niciun algoritm clasic cunoscut. În anii care au urmat, cercetătorii au descoperit alți algoritmi cuantici eficienți. Unele dintre ele, cum ar fi algoritmul lui Shor, au oferit chiar un avantaj exponențial, dar nimeni nu a putut dovedi un avantaj cuantic dramatic pentru orice problemă NP care nu era periodică.
Această lipsă de progres i-a determinat pe doi informaticieni, Scott Aaronson de la Universitatea din Texas, Austin și Andris Ambainis al Universității din Letonia, pentru a face o observație. Dovezile avantajului cuantic păreau întotdeauna dependente de oracole care aveau un fel de structură non-aleatorie, cum ar fi periodicitatea. În 2009, ei conjecturat că nu ar putea exista accelerații dramatice ale problemelor NP care au fost aleatorii sau nestructurate. Nimeni nu a putut găsi o excepție.
Conjectura lor a pus o limită asupra puterilor computerelor cuantice. Dar a spus doar că nu au existat accelerații dramatice pentru un anumit tip de problemă NP nestructurată - cele cu răspunsuri da sau nu. Dacă o problemă a implicat găsirea unor răspunsuri mai specifice, cantitative, care este cunoscută sub numele de problemă de căutare, conjectura nu s-a aplicat.
Cu asta în minte, cercetători Takashi Yamakawa al Laboratoarelor de Informatică Socială NTT și Mark Zhandry de NTT Research și Universitatea Princeton au decis să experimenteze cu o problemă specifică de căutare, introdusă în 2005 de Oded Regev.
Imaginați-vă un set de girouete care sunt toate îndreptate în aceeași direcție. Dați fiecăreia dintre ei un împingere măsurat, apoi lăsați un vânt puternic să le influențeze direcția. Regev a vrut să determine, pe baza direcțiilor lor finale, unde au îndreptat toți inițial. Probleme ca aceasta au ajuns să fie numite „învățare cu erori”, deoarece împingerea și vântul acționează ca o sursă de eroare aleatorie pe direcția inițială. Există dovezi că este greu de rezolvat atât pentru algoritmii clasici, cât și pentru cei cuantici.
Yamakawa și Zhandry au modificat configurația. Au modificat puterea acelor împingeri de pornire, făcându-le mai previzibile. De asemenea, au făcut ca vântul să fie determinat de un oracol aleatoriu, astfel încât să fie și mai întâmplător în anumite cazuri, dar complet latent în altele.
Cu aceste modificări, cercetătorii au descoperit că un algoritm cuantic ar putea găsi în mod eficient direcția inițială. De asemenea, au demonstrat că orice algoritm clasic trebuie să fie mai lent cu un factor exponențial. Ca și Shor, apoi și-au adaptat algoritmul pentru a rezolva o versiune reală a problemei, care înlocuiește oracolul cu o ecuație matematică reală.
Informaticienii încă lucrează pentru a înțelege și a dezvolta problema. Vaikuntanathan îl compară cu unul diferit care apare atunci când faceți comprimarea datelor: atunci când informațiile sunt strânse, doi biți pot fi strânși accidental în același loc, suprascriindu-i. Problema de a prezice acele coliziuni în avans, pentru a le putea evita, are o oarecare asemănare. „Aceasta este o clasă de probleme care, practic, arată așa”, a spus el. „Poate că aceste probleme pot fi rezolvate cuantic.”
Existau speranțe că o problemă nestructurată precum cea nouă ar putea fi rezolvată chiar și pe versiunile incipiente ale calculatoarelor cuantice de astăzi, oferind astfel un mijloc de a le testa. Se credea că problemele nestructurate ar putea necesita mai puține resurse pentru a fi programate sau pot fi mai puțin sensibile la zgomot, deoarece sunt deja aleatorii. Dar până acum, noua problemă pare încă prea avansată pentru a fi rezolvată de computerele cuantice existente. „Este o problemă ciudată. Nu m-am gândit să o definesc”, a spus Aaronson. „Dar retrospectiv, are câteva caracteristici foarte frumoase.”
Rezultatul oferă primul exemplu de avantaj cuantic dramatic pe o problemă NP nestructurată. Ar putea exista multe alte probleme pe care lumea cuantică le schimbă de la practic nerezolvabile la rezolvabile? Acum există mai multe motive să cred asta.
„Ne-a răsturnat oarecum convingerile cu privire la tipurile de probleme la care computerele cuantice ar putea fi bune”, a spus O'Donnell.
