Forskare i USA har kommit fram till hur man testar problem som ännu inte är tillgängliga för människor. Forskare använder samma metod som polisutredare i sin dialog med datorer som löser dessa problem. De "förvirrar" de förhörda, förhör två bilar separat, etc. Till och med kvantmekanik används.
Föreställ dig: en man kommer till dig och säger att han har en sotare, och att denna sotare kan avslöja universumets obegripliga hemligheter. Du är fascinerad, men du tror knappast på honom. Du kommer definitivt att se till att divineraren säger sanningen, och för detta kommer du att behöva något sätt eller metod.
Detta är kärnan i ett av de viktigaste problemen i datavetenskapen. Vissa uppgifter är för svåra att utföra inom en rimlig tidsram. Men deras lösning är lätt att verifiera. Därför vill datavetare veta: Hur komplicerat kan ett problem vara som har en verifierbar lösning?
Det visar sig att svaret är: det kan vara oerhört komplicerat.
I april publicerade två datavetare ett forskningsdokument som multiplicerade antalet problem som är svåra att lösa, men som är lätta att verifiera. De beskrev en metod för att testa lösningar på problem med nästan otrolig komplexitet. "Det låter som galen", sa Thomas Vidick, en datavetare vid California Institute of Technology, som inte var inblandad i det här nya arbetet.
Forskningen avser kvantdatorer som utför beräkningar enligt kvantmekanikens motstridiga regler. Kvantdatorer börjar precis dyka upp, men i framtiden kan de revolutionera beräkning och beräkning.
I själva verket ger den nya vetenskapliga forskningen oss möjlighet att påverka den spets som beskrivs i början av artikeln. Även om han lovar att ge oss svar på de problem som vi själva inte kan lösa, - så även i denna till synes hopplösa situation, kommer vi fortfarande att ha ett sätt att testa den santare och se till att han säger sanningen (eller lurar).
Kampanjvideo:
TILL UNIVERSETS Död
När ett problem är svårt att lösa, men lätt att verifiera, kräver det att hitta en lösning mycket tid, men det är inte att kontrollera riktigheten för den givna lösningen.
Här är ett exempel. Föreställ dig att få en ritning. Det är en samling punkter (vertikaler) som är anslutna med linjer (kanter). Du blir frågad om det är möjligt att måla dessa punkter av en form med bara tre färger så att punkterna anslutna med linjer har olika färger.
Detta "tre-färg" problem är svårt att lösa. I allmänhet växer den tid det tar att komponera en trefärgsfigur (eller för att bestämma att den inte kan existera) exponentiellt när figuren ökar i storlek. Till exempel, om en siffra har 20 punkter för anslutning av linjer, tar lösningen av problemet 3 till den tjugonde kraften i nanosekunder, det vill säga flera sekunder i termer av de tidsenheter vi är vana vid. Men om siffran är med 60 poäng, kommer sökandet efter en lösning att ta 100 gånger längre tid än vår uppskattade ålder av universum.
Men låt oss föreställa oss: någon påstår sig ha gjort en sådan trefärgad figur. Det tar oss lite tid att kontrollera sanningen i hans uttalande. Vi börjar bara kontrollera anslutningspunkterna för raderna en efter en. När siffran växer kommer kontrolltiden långsamt att öka. Detta är den så kallade polynomitiden. Som ett resultat visar det sig att datorn inte tar mycket längre tid att kontrollera en trefärgad siffra med 60 vertikaler än för att kontrollera en siffra med 20 anslutningspunkter.
"Det är ganska lätt att testa att den här kretsen fungerar, så länge den är en riktig trefärgig figur," säger fysikern MIT-fysikern John Wright, som skriver ett nytt papper med Caltechs Anand Natarajan. …
Under 1970-talet identifierade programmerare en klass problem som är lätta att testa, även om de ibland är svåra att lösa. De gav denna klass namnet NPT - icke-deterministisk polynomitid. Sedan dess har många datavetare studerat dessa problem mycket intensivt. I synnerhet vill forskare veta hur denna klass av problem förändras när inspektören har nya sätt att kontrollera lösningens korrekthet.
KORREKTA FRÅGOR
Innan Natarajan och Wrights arbete gjordes två viktiga upptäckter för att verifiera lösningens korrekthet. De har ökat vår förmåga att testa superhårda problem kraftigt.
För att förstå essensen i den första breakout-upptäckten, föreställ dig att du är färgblind. Två kuber placeras på bordet framför dig och du får frågan om de har samma färg eller olika. Denna uppgift är omöjlig för dig. Dessutom är du inte i stånd att testa en annans beslut.
Men du får fråga denna person, som vi kommer att kalla prover. Låt oss säga att prover säger att ett par kuber är olika färger. Vi kommer att utse den första kuben med bokstaven "A" och den andra med bokstaven "B". Du tar kuberna, gömmer dem bakom ryggen och överför dem från hand till hand flera gånger. Sedan visar du kuberna och ber prover att visa kub A.
Om kuberna har olika färger är allt extremt enkelt. Prover vet att kuben A är, säg, röd, och han kommer att peka det korrekt varje gång.
Men om kuberna har samma färg, det vill säga proverna ljuga och säga att deras färg är annorlunda, kan han bara gissa var vilken kub är. På grund av detta kommer han bara att korrekt indikera dö A 50 procent av tiden. Detta innebär att genom att upprepade gånger fråga prover om lösningen kan du verifiera dess korrekthet.
"Undersökaren kan ställa frågorna," sa Wright. "Och kanske i slutet av konversationen kommer verifierarens förtroende att öka."
1985 bevisade en trio av programmerare att sådana interaktiva bevis kan användas för att testa lösningar på problem som är mer komplexa än NIP-klassen. Som ett resultat av deras arbete dök upp en ny klass av problem som kallas IPT - interaktiv polynomtid. Metoden som används för att testa färgen på två kuber kan användas för att testa lösningar på mer komplexa problem och frågor.
Det andra stora steget togs under samma decennium. Allt här följer logiken i en polisutredning. Om du har två misstänkta som du tror har begått ett brott kommer du inte att förhöra dem tillsammans. Du kommer att förhöra dem i olika rum och sedan jämföra de svar som de har gett. Genom att förhöra dessa människor individuellt kan du lära dig mer sanning än om du bara har en misstänkt.
"De två misstänkta kommer inte att kunna komma med någon trolig och konsekvent version eftersom de helt enkelt inte känner varandras svar," sa Wright.
År 1988 bevisade en grupp av fyra datavetare att om två datorer ombads att lösa samma problem separat och sedan ifrågasättas separat om svaren, så kunde en ännu bredare klass problem testas än IPV. Denna klass kallas IDMD - interaktivt bevis med många provare.
Genom att använda detta tillvägagångssätt kan man till exempel testa "tricolor" -problem mot en sekvens av former som växer i storlek mycket snabbare än former under nondeterministic polynomial tid. Under icke-deterministisk polynomisk tid ökar storleken på formerna linjärt - antalet anslutningspunkter för linjer kan öka från 1 till 2, sedan till 3, sedan till 4, och så vidare. Således kommer det aldrig att finnas en stor skillnad i storleken på en figur med den tid det tar att testa sin tricolor. Men om vi talar om ett interaktivt bevis med många provers, så ökar antalet poäng i figuren exponentiellt.
Som ett resultat blir dessa siffror för stora och passar inte in i minnet på kontrolldatorn, varför han inte kan kontrollera deras tricolor genom att gå igenom listan över anslutningspunkter. Men det är fortfarande möjligt att kontrollera tricolor genom att ställa de två provisterna separata, men relaterade frågor.
I IDMD-problemklassen har examinator tillräckligt med minne för att köra ett program för att avgöra om två punkter i en form är anslutna med en linje. Prover kan sedan be varje prover att namnge en av de två prickarna som är anslutna med en linje, varefter han enkelt kan jämföra provers svar för att se till att den trefärgade figuren är korrekt.
Att öka nivån på uppgifter som är svåra att lösa, men lätt att verifiera, från NPV till IPV och sedan till IDMD, kan uppnås genom klassiska datorer. Kvantdatorer fungerar annorlunda. I decennier var det inte klart hur de förändrar bilden, det vill säga om det är svårare eller lättare att kontrollera lösningen med deras hjälp.
Nytt verk av Natarajan och Wright ger svar på denna fråga.
KVANTUMMECEPTION
Kvantdatorer utför beräkning genom att manipulera kvantbitar (qubits). De har en konstig egenskap, vars kärna är att de kan bli förvirrade med varandra. När två qubits, eller till och med stora system med qubits, trasslar in i varandra, betyder det att deras fysiska egenskaper spelar dem ut på ett visst sätt.
I sitt nya arbete överväger Natarajan och Wright ett scenario med två separata kvantdatorer som delar gemensamma intrasslade qubits.
Det verkar som att denna typ av schema fungerar mot validering. Övertaligheten av interaktivt bevis med många provister förklaras exakt av det faktum att du kan förhöra två provister separat och sedan jämföra deras svar. Om dessa svar matchar, är de troligtvis korrekta. Men om två provister är i ett förvirrat tillstånd, så har de fler möjligheter att konsekvent och konsekvent ge fel svar.
När ett scenario med två intrasslade kvantdatorer först föreslogs 2003 föreslog forskare att förvirring skulle försvaga verifieringsförmågan. "Alla, inklusive mig, hade en mycket uppenbar reaktion: nu kommer provisterna att ha mer styrka och övertygande," sade Vidik. "De kan använda intrassling för att samordna sina svar."
Trots denna initiala pessimism tillbringade Vidic flera år på att försöka bevisa annat. 2012 bevisade han, tillsammans med Tsuyoshi Ito, att det fortfarande är möjligt att testa alla problem i IDMD-klassen med hjälp av intrasslade kvantdatorer.
Nu har Natarajan och Wright bevisat att situationen är ännu bättre. En större problemklass kan testas med förvirring än utan. Förbindelserna mellan intrasslade kvantdatorer kan vändas till examinatorens fördel.
För att förstå hur, låt oss komma ihåg proceduren för att testa trefärgade figurer, vars storlek ökar exponentiellt om ett interaktivt bevis med många provers används. Verifieraren har inte tillräckligt med minne för att lagra hela figuren, men tillräckligt för att identifiera två relaterade punkter och fråga provarna vilken färg de är.
Om vi pratar om de problem som Natarajan och Wright överväger - och de tillhör den klass som kallas nondeterministic double exponential time (NDEW) - ökar storleken på siffran i dem ännu snabbare än i problemet med IDMD-klassen. Siffran i NDEV växer med en "dubbel exponentiell" takt. Det vill säga, det är en dubbel geometrisk progression. Siffran ökar inte med hastigheten på den 21, 22, 23, men "i graden." På grund av detta växer formerna så snabbt att granskaren inte kan hitta ett enda par anslutna punkter.
"Det tar 2n bitar för att markera en punkt, som är exponentiellt större än verifierarens arbetsminne," säger Natarajan.
Men Natarajan och Wright hävdar att det är möjligt att testa trefärgsfärgningen av en dubbelt exponentiell figur utan att kunna bestämma vilka punkter att be provisterna om. Poängen är att bevisarna själva ställer frågor.
Enligt forskare är tanken på att be datorer att kontrollera sina egna beslut enligt metoden för valfrågor lika rimlig som idén att be misstänkta om ett brott att förhöra sig själva. Det vill säga, detta är fullständigt nonsens. Det är riktigt, Natarajan och Wright hävdar att detta inte är fallet. Anledningen är förvirring.
"Intrasslat tillstånd är en delad resurs", säger Wright. "Hela protokollet syftar till att förstå hur man använder denna delade resurs för att förbereda relaterade frågor."
Om kvantdatorer är förvirrade, kommer deras val av poäng att vara sammankopplade, och de kommer att ge rätt uppsättning frågor för att testa tricolor.
Samtidigt behöver granskaren inte att de två kvantdatorerna ska vara för nära förbundna, eftersom deras svar på dessa frågor kommer att vara konsekventa (detta motsvarar det faktum att två misstänkta är överens om ett falskt alibi). En annan konstig kvantfunktion löser problemet. I kvantmekanik förhindrar osäkerhetsprincipen oss från att samtidigt känna till en partikelns position och kraften i dess kraft. Om du mäter en, förstör information om den andra. Osäkerhetsprincipen begränsar allvarligt din kunskap om två "komplementära" egenskaper hos ett kvantsystem.
Natarajan och Wright utnyttjade detta i sitt arbete. För att beräkna färg på ett toppunkt använder de två kvantdatorer som kompletterar varandra med mätningar. Varje dator beräknar färgen på sina poäng och på så sätt förstör all information om den andra datorns poäng. Med andra ord tillåter förvirring datorer att formulera sammanhängande frågor, men osäkerhetsprincipen hindrar dem från att konspirera för att svara på dem.
"Vi måste få den prover att glömma [från den falska versionen av händelser], och det är det viktigaste som de [Natarajan och Wright] gjorde i sitt arbete," sa Vidik. "De tvingar prover att ta bort informationen när han gör mätningar."
Deras arbete har enorma och mycket viktiga konsekvenser. Innan detta arbete dök upp var gränsen för mängden kunskap som vi kunde ha med fullständigt förtroende betydligt lägre. Om vi fick ett svar på IDMD-problemet, skulle vi behöva acceptera det på tro, eftersom vi inte har något annat val. Men Natarajan och Wright tog bort denna begränsning och gjorde det möjligt att validera svar på många fler beräkningsproblem.
Men nu när de har gjort det är det inte klart var valideringsgränsen är.
"Detta kan gå mycket längre," sade Lance Fortnow, en datavetenskaplig forskare vid Georgia Institute of Technology. "De lämnar plats för ytterligare ett steg."
Kevin Hartnett
