USA teadlased on välja mõelnud, kuidas testida probleeme, mis pole inimestele veel kättesaadavad. Teadlased kasutavad nende probleemide lahendamisel arvutitega dialoogis sama meetodit nagu politseiuurijad. Nad "ajavad segamini" ülekuulatud, küsitlevad kahte autot eraldi jne. Kasutatakse isegi kvantmehaanikat.
Kujutage ette: mees tuleb teie juurde ja ütleb, et tal on lõõtspill ja et see näpits võib paljastada universumi arusaamatud saladused. Oled küll huvitatud, kuid vaevalt sa teda usud. Kindlasti soovite veenduda, et diviner räägib tõtt, ja selleks vajate mõnda viisi või meetodit.
See on infotehnoloogia ühe peamise probleemi olemus. Mõnda ülesannet on mõistliku aja jooksul liiga keeruline täita. Kuid nende lahendust on lihtne kontrollida. Sel põhjusel tahavad arvutiteadlased teada: kui keeruline võib olla probleem, millel on kontrollitav lahendus?
Selgub, et vastus on: see võib olla uskumatult keeruline.
Aprillis avaldasid kaks arvutiteadlast uurimistöö, mis korrutas keeruliste probleemide arvu, mida on keeruline lahendada, kuid mida on lihtne kontrollida. Nad kirjeldasid meetodit peaaegu uskumatult keerukate probleemide lahenduste testimiseks. "See kõlab nagu hullumeelne," ütles California tehnikainstituudi arvutiteadlane Thomas Vidick, kes polnud selle uue tööga seotud.
Uurimistöös käsitletakse kvantarvuteid, mis teostavad arvutusi kvantmehaanika vastuoluliste reeglite kohaselt. Kvantarvutid alles hakkavad ilmuma, kuid tulevikus võivad need arvutamisel ja arvutamisel pöörde muuta.
Tegelikult annab uus tehtud teaduslik uurimistöö meile võimaluse mõjutada artikli alguses kirjeldatud divinerit. Isegi kui ta lubab meile anda vastused nendele probleemidele, mida me ise ei suuda lahendada, on meil isegi selles näiliselt lootuseta olukorras siiski võimalus proovile panna nutiotsija ja veenduda, et ta räägib tõtt (või petab).
Reklaamvideo:
ÜLIKOOLI SURMAKS
Kui probleemi on keeruline lahendada, kuid seda on lihtne kontrollida, võtab lahenduse leidmine palju aega, kuid antud lahenduse õigsuse kontrollimine mitte.
Siin on näide. Kujutage ette, et teile antakse joonis. See on punktide (tippude) kogum, mida ühendavad jooned (servad). Teilt küsitakse, kas on võimalik neid kuju punkte värvida vaid kolme värviga, nii et joontega ühendatud punktid oleksid eri värvi.
Seda kolmevärvilist probleemi on raske lahendada. Üldiselt kasvab kolmevärvilise kujundi koostamiseks (või tuvastamiseks, et seda ei saa eksisteerida) kuluv aeg eksponentsiaalselt, kui kujund suureneb. Näiteks kui joonisel on 20 joonte ühenduspunkti, siis võtab probleemi lahendamine nanosekundite kahekümnenda võimsuseni, see tähendab mitu sekundit ajaühikutes, millega oleme harjunud. Kui aga arv on 60 punkti, võtab lahenduse otsimine 100 korda kauem aega kui meie hinnanguline universumi vanus.
Kuid kujutlegem: keegi väidab, et on teinud sellise kolmevärvilise figuuri. Tema avalduse õigsuse kontrollimiseks kulub natuke aega. Alustame lihtsalt liinide ühenduspunktide kontrollimist ükshaaval. Arvu kasvades pikeneb aeglaselt ka kontrolliaeg. See on nn polünoomi aeg. Selle tulemusel selgub, et arvutil ei kuluta 60 tipuga kolmevärvilise kujundi kontrollimiseks palju rohkem aega kui 20 ühenduspunktiga kujundi kontrollimiseks.
"Selle vooluringi toimimise testimine on üsna lihtne, kui see on tõeline kolmevärviline kuju," ütleb MIT-i füüsik John Wright, kes kirjutab Caltechi Anand Natarajaniga uut paberit. …
Programmeerijad tegid 1970ndatel kindlaks probleemide klassi, mida on lihtne katsetada, kuigi mõnikord on seda keeruline lahendada. Nad andsid sellele klassile nime NPT - mittedeterministlik polünoomi aeg. Sellest ajast alates on paljud arvutiteadlased neid probleeme väga intensiivselt uurinud. Eriti tahavad teadlased teada saada, kuidas see probleemiklass muutub, kui inspektoril on uusi võimalusi lahenduse õigsuse kontrollimiseks.
ÕIGED KÜSIMUSED
Enne Natarajani ja Wrighti tööd tehti lahenduse õigsuse kontrollimisel kaks olulist avastust. Need on märkimisväärselt suurendanud meie võimalust testida ülikõrgeid probleeme.
Esimese läbimurde avastuse olemuse mõistmiseks kujutlege, et olete värvipime. Teie ees asetatakse kaks kuupi lauale ja teilt küsitakse, kas need on sama värvi või erinevad. See ülesanne on teie jaoks võimatu. Pealegi ei saa te teise inimese otsust testida.
Kuid teil on lubatud küsitleda seda inimest, keda me kutsume vanasõnaks. Ütleme, et vanasõna ütleb teile, et paar kuubikut on erinevat värvi. Esimese kuubi tähistame tähega "A" ja teise tähega "B". Võtate kuubikud, peidate need oma selja taha ja kandke neid mitu korda käest kätte. Siis näitad kuubikuid ja palud proveril näidata A-kuubikut.
Kui kuubikud on erinevat värvi, on kõik äärmiselt lihtne. Vanasõna teab, et kuup A on, näiteks, punane, ja ta osutab sellele iga kord õigesti.
Kuid kui kuubikud on sama värvi, see tähendab, et vanasõna valetas, öeldes, et nende värv on erinev, saab ta ainult arvata, kus see kuubik asub. Seetõttu näitab ta õigesti ainult 50 protsenti ajast. See tähendab, et küsides vanalt korduvalt lahenduse kohta, saate kontrollida selle õigsust.
"Eksamineerija võib vanasõbrale küsimusi esitada," sõnas Wright. "Ja võib-olla vestluse lõpus tõuseb kontrollija usaldus."
1985. aastal tõestas kolm programmeerijat, et selliseid interaktiivseid tõestusi saab kasutada NIP-klassist keerukamate probleemide lahenduste testimiseks. Nende töö tulemusel ilmus uus probleemiklass IPT - interaktiivne polünoomi aeg. Kahe kuubi värvi testimiseks kasutatavat meetodit saab kasutada keerukamate probleemide ja küsimuste lahenduste testimiseks.
Teine suurem samm tehti samal kümnendil. Kõik siin järgib politseiuurimise loogikat. Kui teil on kaht kahtlustatavat, kes arvate, et nad on kuriteo toime pannud, ei küsitle te neid koos. Küsite neid erinevates ruumides ja võrrelge nende antud vastuseid. Neid inimesi eraldi küsitledes saate teada rohkem tõde kui siis, kui teil on ainult üks kahtlusalune.
"Kaks kahtlusalust ei suuda välja pakkuda mingit usutavat ja järjepidevat versiooni, kuna nad lihtsalt ei tea üksteise vastuseid," sõnas Wright.
1988. aastal tõestas neljast arvutiteadlasest koosnev rühm, et kui kahel arvutil palutakse sama probleem eraldi lahendada ja seejärel eraldi vastuseid küsida, siis saab testida veelgi laiemat probleemide klassi kui IPV. Seda klassi kutsutakse IDMD-ks - paljude proversidega interaktiivne tõend.
Seda lähenemisviisi kasutades saab näiteks testida "kolmevärvilisi" probleeme kujundite jada suhtes, mis kasvab suurusjärgus palju kiiremini kui kujundid mittedeterministliku polünoomi ajal. Mittedeterministliku polünoomi ajal suureneb kujude suurus lineaarselt - sirgete ühenduspunktide arv võib suureneda 1-st 2-ni, siis 3-ni, siis 4-ni jne. Seega ei ole kujundi suuruses kunagi tohutut erinevust, kui palju aega kulub selle trikoloori katsetamiseks. Kuid kui me räägime interaktiivsest tõestusest, millel on palju proverde, siis siin suureneb joonisel toodud punktide arv plahvatuslikult.
Selle tulemusel muutuvad need arvud liiga suureks ega mahu kontrollimisarvuti mällu, mistõttu ei saa ta ühenduspunktide loendi kaudu nende trikoloori kontrollida. Kuid trikoloori on siiski võimalik kontrollida, esitades kahele proversile eraldi, kuid omavahel seotud küsimused.
IDMD probleemiklassis on eksamineerijal programmi käivitamiseks piisavalt mälu, et teha kindlaks, kas kuju kaks punkti on ühendatud joonega. Kuulutaja võib seejärel paluda igal vanasõnal nimetada üks kahest joonega ühendatud punktist, mille järel saab ta hõlpsalt võrrelda proversori vastuseid, et veenduda kolmevärvilise kuju õigsuses.
Klassikaliste arvutite abil on võimalik tõsta raskesti lahendatavate, kuid hõlpsasti kontrollitavate ülesannete taset NPV-st IPV-ni ja seejärel IDMD-ni. Kvantarvutid töötavad erinevalt. Aastakümneid polnud selge, kuidas nad pilti muudavad, st kas nende abiga on keerulisem või lihtsam lahendust kontrollida.
Natarajani ja Wrighti uus töö pakub sellele küsimusele vastuse.
KVANTUMI OTSUS
Kvantarvutid viivad arvutamise läbi kvantbittide (kbittide) manipuleerimisega. Neil on kummaline omadus, mille põhiolemus on see, et nad võivad üksteisega segi minna. Kui kaks vutti või isegi suured vutisüsteemid üksteisega sassi lähevad, tähendab see, et nende füüsikalised omadused mängivad neid teatud viisil välja.
Natarajan ja Wright käsitlevad oma uues töös stsenaariumi, kus kaks eraldi kvantarvutit jagavad ühiseid takerdunud vutte.
Näib, et selline skeem töötab valideerimise vastu. Interaktiivse tõendusmaterjali veenvus paljude proveritega on seletatav just asjaoluga, et saate kahte proversti eraldi üle kuulata ja seejärel nende vastuseid võrrelda. Kui need vastused vastavad, siis on need tõenäoliselt õiged. Kuid kui kaks prouvert on segaduses, siis on neil rohkem võimalusi järjekindlalt ja järjekindlalt valesid vastuseid anda.
Tõepoolest, kui 2003. aastal pakuti välja kahe takerdunud kvantarvuti stsenaarium, pakkusid teadlased välja, et takerdumine nõrgendab kontrollimisvõimalusi. "Kõigil, sealhulgas ka minul, oli väga ilmne reaktsioon: nüüd on proverstidel rohkem jõudu ja veenvust," ütles Vidik. "Nad saavad vastuste kooskõlastamiseks kasutada takerdumist."
Vaatamata sellele esialgsele pessimismile veetis Vidic mitu aastat, et tõestada teisiti. 2012. aastal tõestas ta koos Tsuyoshi Itoga, et IDMD-klassis on endiselt võimalik kõiki probleeme testida takerdunud kvantarvutite abil.
Nüüd on Natarajan ja Wright tõestanud, et olukord on veelgi parem. Langumisega saab katsetada laiemat probleemide klassi kui ilma selleta. Seoseid takerdunud kvantarvutite vahel saab eksamineerija kasuks pöörata.
Kuidas seda mõista, tuletagem meelde kolmevärviliste figuuride katsetamise protseduuri, mille suurus suureneb plahvatuslikult, kui kasutatakse interaktiivset tõendit paljude proveritega. Kontrollijal pole kogu kujundi talletamiseks piisavalt mälu, kuid piisavalt, et tuvastada kaks omavahel seotud punkti ja küsida proverstidelt, mis värvi need on.
Kui me räägime probleemidest, mida Natarajan ja Wright arvestavad - ja nad kuuluvad klassi, mida nimetatakse mittedeterministlikuks topelteksponentsiajaks (NDEW) -, siis suureneb neis oleva kujundi suurus isegi kiiremini kui IDMD-klassi probleemiga. NDEV-arv kasvab "kahekordse eksponentsiaalsusega". See tähendab, et see on kahekordne geomeetriline progressioon. Joonis ei suurene mitte 21., 22., 23. kraadi kiirusega, vaid "kraadides". Seetõttu kasvavad kujud nii kiiresti, et eksamineerija ei leia ühte ühendatud punktide paari.
"Punkti märkimiseks kulub 2n bitti, mis on eksponentsiaalselt suurem kui kontrollija töömälu," räägib Natarajan.
Natarajan ja Wright väidavad aga, et kahekordse eksponentsiaalsusega figuuri kolmevärvilist värvust on võimalik testida, ilma et oleks võimalik kindlaks teha, milliseid punkte proverstidelt küsida. Asi on selles, et proverid esitavad ise küsimusi.
Teadlaste sõnul on mõte paluda arvutitel küsitluste teel enda otsuseid kontrollida. Sama mõistlik kui idee paluda kuriteos kahtlustatavatel end ülekuulata. See tähendab, et see on täielik jama. Tõsi, Natarajan ja Wright väidavad, et see pole nii. Põhjus on segadus.
"Seotud riik on jagatud ressurss," ütleb Wright. "Kogu meie protokolli eesmärk on mõista, kuidas seda ühist ressurssi kasutada seotud küsimuste ettevalmistamiseks."
Kui kvantarvutid on segamini, siis on nende valitud punktid omavahel ühendatud ja nad annavad trikoloori testimiseks õige komplekti küsimusi.
Samal ajal ei vaja eksamineerija kahte kvantarvutit liiga tihedalt ühendatud, kuna nende vastused neile küsimustele on järjepidevad (see võrdub tõsiasjaga, et kaks kahtlusalust lepivad kokku vale alibiga). Teine kummaline kvantomadus parandab selle probleemi. Kvantmehaanikas takistab mõõtemääramatuse põhimõte meid üheaegselt osakese asukoha ja selle jõu impulsi tundmist. Kui mõõdate ühte, siis hävitage teave teise kohta. Määramatuse põhimõte piirab tõsiselt teadmisi kvantisüsteemi kahe "täiendava" omaduse kohta.
Natarajan ja Wright kasutasid seda oma töös ära. Tipppunkti värvi arvutamiseks kasutavad nad kahte kvantarvutit, mis täiendavad üksteise mõõtmeid. Iga arvuti arvutab oma punktide värvi ja seda tehes hävitab kogu teabe teise arvuti punktide kohta. Teisisõnu, takerdumine võimaldab arvutitel sõnastada omavahel seotud küsimusi, kuid määramatuse printsiip takistab neid vastates vandenõu.
"Peame panema vanasõbra unustama [sündmuste võltsversiooni] ja see on peamine asi, mida nad [Natarajan ja Wright] oma töös tegid," sõnas Vidik. "Nad sunnivad vanasõitu mõõtmise ajal teabe eemaldama."
Nende tööl on tohutud ja väga olulised tagajärjed. Enne selle töö ilmumist oli teadmiste hulga piir, mida meil täieliku enesekindlusega võiks olla, oluliselt madalam. Kui meile antaks vastus IDMD probleemile, peaksime sellega leppima usus, kuna meil pole muud valikut. Kuid Natarajan ja Wright kõrvaldasid selle piirangu ja võimaldasid kinnitada vastuseid paljudele muudele arvutusprobleemidele.
Kuid nüüd, kui nad on selle teinud, pole selge, kus on valideerimise piir.
"See võib minna palju kaugemale," ütles Georgia tehnoloogiainstituudi arvutiteaduste uurija Lance Fortnow. "Nad jätavad ruumi veel ühe sammu jaoks."
Kevin Hartnett
