TL;DR - Kratak rezime

Rizik: Naša trenutna teorija složenosti ne može da obradi probleme koji primaju ili emituju kvantna stanja, zbog čega propuštamo značajan deo kvantno unapređenog računarstva i kriptografije.
Uticaj: Potpuno kvantni okvir složenosti mogao bi da poveže naizgled nepovezane kvantne zadatke — poput protokola obavezivanja bitom (bit-commitment), dekodiranja informacija iz crnih rupa i kvantne kompresije — pružajući kriptografima i fizičarima potpuno nove alate.
Izgledi: Rani radovi ukazuju na to da je problem "Ulmanove transformacije" centralna tačka koja povezuje mnoge kvantne izazove; dublja istraživanja mogla bi preoblikovati akademske programe i podstaći razvoj praktičnog softvera optimizovanog za kvantne sisteme.

Nova teorija složenosti za kvantno doba

Decenijama su informatičari istraživali koliko je teško transformisati jedan niz bitova u drugi. Taj pravac razmišljanja — teorija kompjuterske složenosti — čini osnovu svega, od kriptografskih šema do čuvene zagonetke "P protiv NP". Međutim, ona funkcioniše samo sa klasičnim ulazima i izlazima, odnosno običnim binarnim nizovima.

Tu na scenu stupa Henri Juen (Henry Yuen), profesor sa Univerziteta Kolumbija, koji tvrdi da ova pretpostavka gura čitavu klasu problema u senku. "Tradicionalna teorija složenosti ovo jednostavno ignoriše", objašnjava on. "Možda nam je potrebna potpuno nova teorija za ovakve vrste problema." Juen teži stvaranju celovite kvantne teorije složenosti koja bi radila sa podacima koji su sami po sebi kvantna stanja.

Zašto su kvantni ulazi važni

Uzmimo za primer kriptografski primitiv poznat kao obavezivanje bitom (bit commitment). U klasičnom smislu, poruku zaključate u zapečaćenu kovertu, držite je skrivenom i osiguravate da se kasnije ne može promeniti. Njena bezbednost počiva na teškim matematičkim problemima — zadacima koje čak ni moćan klasični računar ne može da reši.

Zamenite kovertu kvantnom i pravila igre se menjaju. Čak ni supermoćni klasični računar ne mora nužno da provali ovaj protokol, jer izazov sada podrazumeva manipulaciju kvantnim stanjima, a ne samo puko procesuiranje brojeva. Ovo pokazuje da se problemi sa kvantnim ulazom mogu ponašati fundamentalno drugačije od svojih klasičnih parnjaka.

Problem unitarne sinteze

Jedno od intrigantnih otvorenih pitanja koje Juen postavlja jeste problem unitarne sinteze. Zamislite klasično proročište (oracle) koje trenutno rešava bilo koju klasičnu zagonetku. Da li bismo mogli da iskoristimo to proročište da efikasno izvršimo bilo koju transformaciju kvantnog stanja — unitarnu operaciju — na kvantnom sistemu? Ako je odgovor negativan, to bi dokazalo da zadaci sa kvantnim ulazom i izlazom pripadaju domenu koji klasična složenost ne može da obuhvati.

Do sada je postignut tek skroman napredak, ali ovaj problem služi kao ključni test za to da li se potpuno kvantna teorija može izdvojiti kao nezavisna u odnosu na staru.

Pronalaženje zajedničkog čvorišta: Ulmanova transformacija

Juenov najnoviji rad definiše "čvorište" koje povezuje niz kvantnih zagonetki: problem Ulmanove (Uhlmann) transformacije. Ulmanova teorema nam govori koliko uspešno možemo pretvoriti jedno spregnuto (entangled) stanje u drugo manipulisanjem samo jednom česticom. Kada se ta teorema postavi kao zadatak sa kvantnim ulazom i izlazom, Juen i njegov tim su pokazali da mnogi drugi problemi dele isti nivo težine.

Ovi zadaci uključuju:

Dekodiranje Hokingovog zračenja iz crne rupe — što je suštinski razmrsivanje ogromnog roja spregnutih čestica.
Kompresiju kvantnih informacija na efikasan način.
Dizajniranje bezbednih kvantno-kriptografskih protokola za "obavezivanje bitom".

Posmatranje ovih pitanja kao različitih strana iste transformacije nagoveštava da bi jedinstvena kvantna teorija složenosti mogla da pojednostavi istraživanja u fizici, kriptografiji i teoriji informacija.

Od video-igara do kvantne teorije

Juenova priča pokazuje kako interdisciplinarna radoznalost dovodi do prodora. Rođen 1989. godine u porodici kambodžanskih izbeglica, programiranje je naučio pomažući u porodičnom restoranu. Tinejdžerska strast prema dizajnu video-igara privukla ga je informatici, a slučajan pronalazak bloga Skota Aronsona o kvantnom računarstvu usmerio ga je ka teoretskim granicama nauke.

Rani rad sa Lenom Adlemanom, pionirom DNK računarstva, naučio ga je da "ignoriše sve što su ljudi radili decenijama" i da krči nove matematičke puteve. Taj mentalni sklop sada primenjuje na samu srž kompjuterske složenosti.

Šta nas čeka dalje

Izgradnja pune kvantne teorije složenosti je još uvek u povoju. Juenov tim je skicirao nekoliko ekvivalencija, ali velika pitanja — poput definisanja čvrstih klasa složenosti sa kvantnim ulazom i dokazivanja njihove razlike u odnosu na klasične — i dalje ostaju otvorena.

Ipak, ovaj okvir već oblikuje način na koji istraživači pristupaju kvantnoj kriptografiji, problemima informacija u crnim rupama i dizajnu kvantnih kompajlera. Kako kvantni hardver bude postajao pouzdaniji, praktična korist od jedinstvene teorije mogla bi postati jasnija, pružajući nam prečice za bezbedne kvantne komunikacije i optimizaciju kola.

Predviđanja za 2031. godinu:

Novi, potpuno kvantni okvir kompleksnosti uzdrmaće kriptografske standarde, čime će mnoge post-kvantne metode postati nesigurne, što otvara put za inovativne pristupe zasnovane na kvantnom obavezivanju (quantum-based commitment).
Univerziteti i agencije za finansiranje verovatno će se fokusirati na klase problema sa kvantnim unosom, što će dovesti do stvaranja podoblasti koja spaja teoriju kvantnih informacija sa teorijom kompleksnosti, menjajući strukturu postdiplomskih programa širom sveta.
Industrija će predstaviti prve kvantno-optimizovane kompilatore, čime će se drastično skratiti vreme sinteze kola i ubrzati razvoj praktičnih kvantnih procesora za specifične zadatke, poput bezbedne razmene poruka, pa čak i dekodiranja podataka iz crnih rupa.

Teorija kvantne složenosti mogla bi da redefiniše kriptografiju i fiziku.