Znanstvenici u Sjedinjenim Državama smislili su kako testirati probleme koji ljudima još nisu dostupni. Znanstvenici koriste istu metodu kao i policijski istražitelji u dijalogu s računalima koja rješavaju ove probleme. Oni "zbunjuju" ispitivane, ispituju odvojeno dva automobila itd. Čak se koristi i kvantna mehanika.
Zamislite: čovjek dođe k vama i kaže da ima govornicu, a da taj govornik može otkriti neshvatljive tajne svemira. Zaintrigirani ste, ali teško da mu vjerujete. Sigurno ćete se htjeti pobrinuti da divist govori istinu, a za to će vam trebati neki način ili metoda.
To je suština jednog od glavnih problema informatike. Neke su zadatke preteško izvršiti u razumnom roku. Ali njihovo je rješenje lako provjeriti. Iz tog razloga, računalni znanstvenici žele znati: Koliko složen može biti problem koji ima rješenje koje se može provjeriti?
Ispada da je odgovor sljedeći: može biti nevjerojatno složen.
U travnju su dva informatičara objavila istraživački rad koji je umnožio broj problema koje je teško riješiti, ali je lako provjeriti. Opisali su metodu za testiranje rješenja gotovo nevjerojatne složenosti. "Zvuči ludo", rekao je Thomas Vidick, informatičar s Kalifornijskog tehnološkog instituta, koji nije bio uključen u ovo novo djelo.
Istraživanje se odnosi na kvantna računala koja obavljaju račune prema oprečnim pravilima kvantne mehanike. Kvantna računala tek se počinju pojavljivati, ali u budućnosti mogu revolucionirati računarstvo i računanje.
Zapravo, novo provedena znanstvena istraživanja daju nam priliku utjecati na razvratnik opisan na početku članka. Čak i ako nam obeća da će dati odgovore na one probleme koje sami nismo u stanju riješiti, pa ćemo čak i u ovoj naoko beznadnoj situaciji ipak imati načina da testiramo govornika i budemo sigurni da govori istinu (ili obmanjuje).
Promotivni video:
DO SMRTI SVEUČILIŠTA
Kada je problem teško riješiti, ali je lako provjeriti, pronalaženje rješenja oduzima puno vremena, ali provjera ispravnosti datog rješenja nije.
Evo primjera. Zamislite da vam se prikaže crtež. To je skup točaka (vrhova) koji su povezani linijama (rubovima). Od vas se traži da li je moguće obojiti ove točke oblika sa samo tri boje tako da točke povezane crtama budu različitih boja.
Taj je trobojni problem teško riješiti. Općenito, vrijeme potrebno za sastavljanje trobojne figure (ili za utvrđivanje da ne može postojati) raste eksponencijalno kako se lik povećava u veličini. Na primjer, ako brojka ima 20 točaka povezivanja linija, tada rješenje problema ima 3 do dvadesete snage nanosekundi, odnosno nekoliko sekundi u odnosu na jedinice vremena na koje smo navikli. Ali ako je brojka sa 60 točaka, tada će potraga za rješenjem trajati 100 puta duže od naše procijenjene dobi svemira.
Ali zamislimo: netko tvrdi da je napravio takvu trobojnu figuru. Trebat će nam malo vremena da provjerimo istinitost njegove izjave. Tek ćemo početi provjeravati točke povezivanja linija jedan po jedan. Kako brojka raste, vrijeme provjere također će se polako povećavati. Ovo je takozvano polinomno vrijeme. Kao rezultat, ispada da računalu ne treba puno više vremena za provjeru trobojnice s 60 vrhova nego za provjeru figure s 20 točaka spajanja.
"Prilično je lako testirati da li ovaj krug djeluje, pod uvjetom da je pravi trobojni lik", kaže fizičar MIT-a John Wright, koji je zajedno napisao novi rad s Caltechovim Anandom Natarajanom. …
1970-ih programeri su identificirali klasu problema koje je lako testirati, iako ih je ponekad teško riješiti. Oni su ovoj klasi dali ime NPT - nedeterminističko polinomno vrijeme. Od tada, mnogi računalni znanstvenici vrlo intenzivno proučavaju ove probleme. Znanstvenici posebno žele znati kako se ta klasa problema mijenja kada inspektor ima nove načine provjere ispravnosti rješenja.
PRAVILNA PITANJA
Prije rada Natarajana i Wrighta, učinjena su dva važna otkrića u provjeri ispravnosti rješenja. Uvelike su povećali našu sposobnost testiranja super teških problema.
Da biste shvatili suštinu prvog otkrića, zamislite da ste slijepi za boju. Dvije kocke postavljene su na stol ispred vas, a vi ćete biti upitani jesu li iste boje ili različiti. Ovaj zadatak vam je nemoguć. Štoviše, niste u prilici testirati odluku druge osobe.
Ali vam je dozvoljeno ispitivati ovu osobu koju ćemo nazvati dokazivanjem. Recimo da vam dokazi govore da su par kockica različite boje. Označit ćemo prvu kocku slovom „A“, a drugu slovom „B“. Uzmeš kocke, sakriješ ih iza leđa i nekoliko puta prebaciš iz ruke u ruku. Tada pokazujete kocke i tražite od dokazivanja da pokaže kocku A.
Ako su kocke različite boje, sve je krajnje jednostavno. Dogovor zna da je kocka A, recimo, crvena, i točno će je ukazati svaki put.
Ali ako su kocke iste boje, tj. Dokazivač je lagao govoreći da je njihova boja različita, on može samo nagađati gdje je kocka. Zbog toga će on samo ispravno naznačiti umrijeti A 50 posto vremena. To znači da stalnim postavljanjem dokaza za rješenje možete provjeriti njegovu ispravnost.
"Ispitivač može postavljati provjerena pitanja", rekao je Wright. "I možda će na kraju razgovora samopouzdanje verifikatora porasti."
Godine 1985. trio programera dokazao je da se takvi interaktivni dokazi mogu koristiti za testiranje rješenja složenijih problema od klase NIP. Kao rezultat njihovog rada, pojavila se nova klasa problema pod nazivom IPT - interaktivno polinomno vrijeme. Metoda koja se koristi za testiranje boje dvije kocke može se koristiti za testiranje rješenja složenijih problema i pitanja.
Drugi veliki korak učinjen je u istom desetljeću. Sve ovdje slijedi logiku policijske istrage. Ako imate dva osumnjičena za koja mislite da su počinili zločin, nećete ih zajedno ispitivati. Ispitivat ćete ih u različitim sobama, a zatim usporediti odgovore koje su vam dali. Ispitujući ove ljude odvojeno, možete naučiti više istine nego ako imate samo jednog osumnjičenog.
"Dvojica osumnjičenih neće moći smisliti neku uvjerljivu i konzistentnu verziju jer jednostavno neće znati odgovore jednih drugih", rekao je Wright.
Godine 1988. grupa od četiri računalna znanstvenika dokazala je da ako se od dva računala pita da zasebno riješe isti problem, a potom odvojeno ispituju odgovore, tada se može ispitati još šira klasa problema od IPV-a. Ova se klasa naziva IDMD - interaktivni dokaz s mnogim dokazima.
Koristeći ovaj pristup, može se, primjerice, testirati problemi s trobojnicom u odnosu na niz oblika koji rastu u veličini mnogo brže od oblika u nedetermineriranom polinomnom vremenu. U vremenu koje nije determinirano od polinoma, veličina oblika se linearno povećava - broj priključnih točaka linija može se povećati od 1 do 2, zatim na 3, zatim na 4 i tako dalje. Dakle, nikad neće doći do velike razlike u veličini figure s količinom vremena potrebnim za testiranje njegove trobojnice. Ali ako govorimo o interaktivnom dokazu s mnogim dokazima, tada se broj točaka na slici eksponencijalno povećava.
Kao rezultat, ove brojke postaju prevelike i ne uklapaju se u memoriju računala za provjeru, pa on ne može provjeriti njihovu trobojnicu tako što će proći kroz popis spojnih točaka. Ali još je uvijek moguće provjeriti trobojnicu postavljanjem dva ispitivača odvojena, ali povezana pitanja.
U programskoj klasi IDMD ispitivač ima dovoljno memorije da pokrene program da utvrdi jesu li dvije točke u nekom obliku povezane linijom. Dotada zatim može zatražiti od svakog dokazivača da nazove jednu od dviju točaka povezanih linijom, nakon čega može lako usporediti odgovore ispitanika kako bi se uvjerio da je trobojna figura ispravna.
Povećanje razine zadataka koje je teško riješiti, ali je lako provjeriti, od NPV-a do IPV-a, a potom i IDMD-a, moglo bi se postići putem klasičnih računala. Kvantna računala rade drugačije. Desetljećima nije bilo jasno kako mijenjaju sliku, odnosno je li teže ili lakše provjeriti rješenje uz njihovu pomoć.
Novi rad Natarajana i Wrighta daje odgovor na to pitanje.
KVANTNA ODLUKA
Kvantna računala izvode računanje manipuliranjem kvantnim bitovima (kbitima). Imaju čudno svojstvo, čija je suština da se mogu zbuniti jedni s drugima. Kada se dva qubita, ili čak veliki sustav qubita, zapleteju jedan s drugim, to znači da ih njihova fizička svojstva na određeni način reproduciraju.
U svom novom radu Natarajan i Wright razmatraju scenarij s dva odvojena kvantna računala koja dijele zajedničke isprepletene kvitove.
Čini se da ovakva shema djeluje protiv validacije. Uvjerljivost interaktivnog dokaza s mnogim dokazima objašnjava se upravo činjenicom da možete dva ispitivača zasebno ispitivati, a zatim usporediti njihove odgovore. Ako se ovi odgovori podudaraju, onda su najvjerojatnije tačni. Ali ako su dva dokaza u zbunjenom stanju, tada imaju više mogućnosti da dosljedno i dosljedno daju pogrešne odgovore.
Doista, kada je 2003. godine prvi put predložen scenarij s dva zapletena kvantna računala, znanstvenici su sugerirali da bi zapletenost oslabila sposobnosti provjere. "Svi, uključujući mene, imali su vrlo očitu reakciju: sada će dokazi imati više snage i uvjerljivosti", rekao je Vidik. "Oni mogu upotrijebiti zaplete radi koordiniranja svojih odgovora."
Unatoč ovom početnom pesimizmu, Vidić je proveo nekoliko godina pokušavajući dokazati drugačije. U 2012. godini, zajedno s Tsuyoshijem Ito, dokazao je da je još uvijek moguće testirati sve probleme u kategoriji IDMD uz pomoć isprepletenih kvantnih računala.
Sada su Natarajan i Wright dokazali da je situacija još bolja. Šira klasa problema može se testirati zapletom bez nje. Veza između zapletenih kvantnih računala može se pretvoriti u korist ispitivača.
Da bismo razumjeli kako, podsjetimo se postupka testiranja trobojnih figura, čija se veličina eksponencijalno povećava ako se koristi interaktivni dokaz s mnogim dokazima. Provjeravač nema dovoljno memorije za pohranjivanje cijele slike, ali dovoljno je da identificira dvije povezane točke i pita ispitivače koje su boje.
Ako govorimo o problemima koje Natarajan i Wright smatraju - a oni pripadaju klasi koja se naziva neterminerično dvostruko eksponencijalno vrijeme (NDEW) - tada se veličina figure u njima povećava čak i brže nego u problemu klase IDMD. Brojka u NDEV-u raste brzinom "dvostruke eksponencijalnosti". Odnosno, to je dvostruka geometrijska progresija. Brojka se povećava ne brzinom 21., 22., 23. stupnja, već „u stupnjevima stupnjeva“. Zbog toga oblici rastu tako brzo da ispitivač ne može pronaći niti jedan par povezanih točaka.
"Potrebno je 2n bita za označavanje točke, koja je eksponencijalno veća od radne memorije verifikatora", kaže Natarajan.
Ali Natarajan i Wright tvrde da je moguće testirati trobojnu obojenost dvostruko eksponencijalne figure, a da ne budu u stanju odrediti o kojim se točkama pitaju dokazi. Poanta je u tome da sami dokazi postavljaju pitanja.
Prema znanstvenicima, ideja traženja računala da provjere vlastite odluke metodom anketiranja jednako je razumna kao i ideja traženja osumnjičenih za zločin da ih se saslušaju. Odnosno, ovo je potpuna glupost. Istina, Natarajan i Wright tvrde da to nije slučaj. Razlog je zbrka.
"Opće stanje je zajednički resurs", kaže Wright. "Cijeli naš protokol želi razumjeti kako koristiti ovaj zajednički resurs za pripremu povezanih pitanja."
Ako su kvantna računala zbunjena, tada će njihov izbor bodova biti međusobno povezan i dat će pravi set pitanja za testiranje trobojnice.
Istodobno, ispitivaču nisu potrebna da dva kvantna računala budu previše međusobno povezana jer će njihovi odgovori na ta pitanja biti konzistentni (to je ekvivalentno činjenici da se dva osumnjičena slažu između sebe o lažnom alibiju). Još jedna čudna kvantna značajka popravlja ovaj problem. U kvantnoj mehanici princip neizvjesnosti sprječava nas da istovremeno znamo položaj čestice i moment njezine sile. Ako mjerite jedno, uništite podatke o drugom. Princip nesigurnosti ozbiljno ograničava vaše znanje o dva "komplementarna" svojstva kvantnog sustava.
Natarajan i Wright su to iskoristili u svom radu. Za izračunavanje vertikalne boje koriste dva kvantna računala koja se međusobno nadopunjuju mjerenjima. Svako računalo izračunava boju svojih točaka, a time uništava sve informacije o točkama drugog računala. Drugim riječima, zapetljavanje omogućava računalima formuliranje međusobno povezanih pitanja, ali princip neizvjesnosti sprječava ih u zavjeri u odgovaranju na njih.
"Moramo navesti istražitelja da zaboravi [na lažnu verziju događaja], a to je glavno što su [Natarajan i Wright] učinili u svom poslu", rekao je Vidik. "Prisiljavaju istražitelja da ukloni podatke kad izvrši mjerenja."
Njihov rad ima ogromne i vrlo važne posljedice. Prije nego što se ovaj rad pojavio, granica količine znanja koju bismo mogli imati s potpunim povjerenjem bila je znatno niža. Da smo dobili odgovor na IDMD problem, morali bismo ga prihvatiti na vjeru, jer drugog izbora nemamo. Ali Natarajan i Wright uklonili su ovo ograničenje i omogućili potvrdu odgovora na mnoge računske probleme.
Ali sada kada su to učinili, nije jasno gdje je granica valjanosti.
"Ovo bi moglo ići puno dalje", rekao je Lance Fortnow, istraživač informatike s Georgia Institute of Technology. "Ostavljaju prostor za još jedan korak."
Kevin Hartnett