Coherent swap regret i kanali koji uče

Zamisli da igraš poker protiv protivnika koji u svakom trenutku može zamijeniti svoje karte tvojima, a da ti toga nisi ni svjestan. I sad ti netko kaže da je fer igra ako se obvežeš da ćeš uvijek držati iste karte — pa makar i bile lošije. To je, otprilike, razina na kojoj smo dosad mjerili koliko su kvantni algoritmi "stabilni" u igrama. Koji kurac.

Četrdeset godina teorije igara i netko se konačno sjetio da bi protivnik mogao napraviti nešto pametnije od pukog ponavljanja iste strategije — mogao bi primijeniti lokalnu kvantnu operaciju na stanje koje si mu upravo poslao. Ne mora mijenjati cijelu strategiju, samo malo zavrnuti tvoje vlastito stanje. Kao da ti u šahu protivnik ne bi pomaknuo skakača, nego bi ti malo okrenuo ploču za pet stupnjeva i tvrdio da je to i dalje tvoj potez.

Ovo što su izvukli iz laboratorija zove se "coherent swap regret" i zvuči kao nešto što bi izmislio čovjek koji se probudio usred noći s idejom da je cijela dosadašnja matematika krivo postavila pitanje. Jer, eto, ispada da je standardni "external regret" — mjera koja ti garantira da ne možeš biti eksploatiran ako se držiš jedne fiksne strategije — potpuno beskoristan kad protivnik ima pristup kvantnim operacijama. A tko nema, ?

Algoritam koji su razvili postiže O(sqrt(dT log d)) coherent swap regret, što je tehnički lijepo, ali je filozofski jezivo. Jer implikacija je da u kvantnim igrama — a sve više stvarnih ekonomskih i sigurnosnih sustava postaju kvantne igre — tvoja "optimalna" strategija ne vrijedi ništa ako protivnik može primijeniti CPTP mapu na tvoje vlastito stanje. To je kao da otkriješ da banka u kojoj držiš novac može, bez tvoje dozvole, pretvoriti tvoje eure u dolarima u švicarske franke s kamatom od minus dva posto. I to je legalno, jer je "lokalna operacija".

Ljudi koji su ovo napisali očito su proveli previše vremena gledajući kako kvantne dekoherencije razaraju njihove eksperimente pa su odlučili: ako već ne možemo spriječiti protivnika da petlja po našem stanju, idemo napisati algoritam koji to uračunava. Pragmatično, jebeno pametno, ali i malo depresivno. Kao kad shvatiš da brava na vratima ne štiti od provalnika koji ima tvoj ključ — pa umjesto da promijeniš bravu, napišeš ugovor u kojem se obvezuješ da nećeš provaliti sam sebi u stan.

Tehnički, ključni uvid je da CPTP mape — one lokalne operacije koje protivnik može primijeniti — nisu samo "varanje" u klasičnom smislu. One su fundamentalno drugačija klasa odstupanja od tvoje strategije. Klasični regret pretpostavlja da protivnik bira između fiksnih alternativa. Kvantni regret priznaje da protivnik može miksati tvoje poteze s vlastitima na način koji nema klasičnog ekvivalenta. Kao da si u šahu odjednom shvatio da protivnik može igrati i tvojim i svojim figurama istovremeno, ali samo na pola ploče.

Primjene? Pa, osim očitih u kvantnim kriptografskim protokolima i kvantnom strojnom učenju, ovo ima jednu zgodnu osobinu: algoritam koji su razvili je "channel-proof", što znači da radi čak i kad su komunikacijski kanali šumoviti. A šumoviti su uvijek. Pogotovo kad netko aktivno pokušava da budu. To je kao da si napravio auto koji vozi i kad ti netko probuši gume — sporije, ali vozi.

Naravno, cijela ova priča ima i jednu mračniju stranu koju nitko ne spominje. Ako možeš garantirati stabilnost protiv lokalnih CPTP devijacija, možeš i konstruirati napade koji ih koriste. Svaki alat za obranu je ujedno i priručnik za napad. To je zakon termodinamike informacije: što bolje znaš kako netko može varati, to bolje znaš kako varati sam. I sad zamisli da ovaj algoritam implementiraš u kvantnom komunikacijskom protokolu između dvije banke. I jedan od protokola je kompromitiran. I sad netko može primijeniti lokalnu CPTP mapu na tvoje stanje i ti misliš da si siguran jer tvoj algoritam garantira O(sqrt(dT log d)) regret. A garantira. Samo što je netko već iskoristio tu garanciju da izgradi napad koji je brži od tvoje obrane. Ironija, pas mater.

Ali najbolji dio: cijela ova teorija počiva na pretpostavci da su igrači "racionalni" u kvantnom smislu. A što je kvantna racionalnost? To je kad tvoje odluke ne moraju biti konzistentne u klasičnom smislu — možeš biti u superpoziciji između "želim profit" i "želim uništiti protivnika", a algoritam će i dalje garantirati stabilnost. To je kao da kažeš: "Ne brini što si u životu napravio sto kontradiktornih stvari, tvoj portfolio je i dalje optimalan." I u tome je, naravno, istina. Jer kvantni svijet ne poznaje kontradikcije. Samo vjerojatnosti.

I tako smo došli do točke u kojoj matematičari dokazuju da je najbolji način da se zaštitiš od varanja u kvantnoj igri — priznati da ćeš biti varan i uračunati to u svoju strategiju. Pragmatizam na steroidima. Ako moraš objasniti zašto tvoj protokol nije ranjiv na napade, vjerojatno jest.

Izvor: arxiv.org