Forskere i USA har funnet ut hvordan de skal teste problemer som ennå ikke er tilgjengelige for mennesker. Forskere bruker samme metode som politietterforskere i sin dialog med datamaskiner som løser disse problemene. De "forvirrer" de avhørte, avhører to biler hver for seg, etc. Til og med kvantemekanikk brukes.
Se for deg: en mann kommer til deg og sier at han har en ledsager, og at denne ledsageren kan avsløre universets uforståelige hemmeligheter. Du er fascinert, men du tror nesten ikke ham. Du vil definitivt ønske deg at divinen forteller sannheten, og for dette trenger du noen måte eller metode.
Dette er essensen av et av hovedvitenskapene i informatikk. Noen oppgaver er for vanskelige å utføre innenfor en rimelig tidsramme. Men løsningen deres er enkel å verifisere. Av denne grunn vil dataforskere vite: Hvor komplekst kan et problem være som har en etterprøvbar løsning?
Det viser seg at svaret er: det kan være utrolig sammensatt.
I april publiserte to datavitere en forskningsartikkel som multipliserte antall problemer som er vanskelige å løse, men som er enkle å verifisere. De beskrev en metode for å teste løsninger på problemer med nesten utrolig kompleksitet. "Det høres ut som sprøtt," sa Thomas Vidick, dataforsker ved California Institute of Technology, som ikke var involvert i dette nye arbeidet.
Forskningen gjelder kvantemaskiner som utfører beregninger i henhold til de motstridende reglene for kvantemekanikk. Kvantedatamaskiner begynner akkurat å dukke opp, men i fremtiden kan de revolusjonere beregning og beregning.
Faktisk gir den nye vitenskapelige undersøkelsen oss muligheten til å påvirke spådommen som ble beskrevet i begynnelsen av artikkelen. Selv om han lover å gi oss svar på de problemene som vi selv ikke er i stand til å løse, så selv i denne tilsynelatende håpløse situasjonen, vil vi fortsatt ha en måte å teste den ledsageren på og sørge for at han forteller sannheten (eller lurer).
Salgsfremmende video:
TIL DIVET TIL UNIVERSET
Når et problem er vanskelig å løse, men enkelt å verifisere, tar det å finne en løsning mye tid, men det er ikke å sjekke riktigheten av den gitte løsningen.
Her er et eksempel. Se for deg å bli gitt en tegning. Det er en samling punkter (toppunkt) som er forbundet med linjer (kanter). Du blir spurt om det er mulig å male disse punktene av en form med bare tre farger, slik at punktene som er forbundet med linjer har forskjellige farger.
Dette “trefargede” problemet er vanskelig å løse. Generelt vokser mengden tid det tar å komponere en trefarget figur (eller for å bestemme at den ikke kan eksistere) eksponentielt etter hvert som tallet øker i størrelse. For eksempel, hvis et tall har 20 poeng for tilkobling av linjer, tar løsningen av problemet 3 til den tjuende kraften til nanosekunder, det vil si flere sekunder i forhold til tidsenhetene vi er vant til. Men hvis tallet er på 60 poeng, vil søket etter en løsning ta 100 ganger lenger tid enn vår estimerte alder på universet.
Men la oss tenke oss: noen hevder å ha laget en så trefarget figur. Det vil ta oss litt tid å sjekke sannheten i uttalelsen hans. Vi begynner bare å sjekke tilkoblingspunktene for linjene én etter én. Når tallet vokser vil sjekketiden sakte øke. Dette er den såkalte polynomietiden. Som et resultat viser det seg at datamaskinen ikke tar mye mer tid å sjekke en trefarget figur med 60 hjørner enn den gjør for å sjekke et tall med 20 tilkoblingspunkter.
"Det er ganske enkelt å teste at denne kretsen fungerer, så lenge den er en skikkelig trefarget skikkelse," sier MIT-fysikeren John Wright, som skrev en ny artikkel med Caltechs Anand Natarajan. …
På 1970-tallet identifiserte programmerere en klasse problemer som er enkle å teste, selv om det noen ganger er vanskelige å løse. De ga denne klassen navnet NPT - ikke-deterministisk polynomisk tid. Siden den gang har mange informatikere studert disse problemene veldig intenst. Spesielt ønsker forskere å vite hvordan denne klassen av problemer endres når inspektøren har nye måter å kontrollere at løsningen er korrekt.
KORREKTE SPØRSMÅL
Før Natarajan og Wright arbeidet ble det gjort to viktige funn for å verifisere løsningen. De har økt vår evne til å teste superharde problemer.
For å forstå essensen av det første breakoutfunnet, kan du forestille deg at du er fargeblind. To terninger er plassert på bordet foran deg, og du blir spurt om de er i samme farge eller forskjellige. Denne oppgaven er umulig for deg. Dessuten er du ikke i stand til å teste en annens beslutning.
Men du har lov til å avhøre denne personen, som vi vil kalle prover. La oss si at prover forteller deg at et par terninger er i forskjellige farger. Vi vil utpeke den første kuben med bokstaven "A", og den andre med bokstaven "B". Du tar kubene, gjemmer dem bak ryggen og overfører dem fra hånd til hånd flere ganger. Så viser du terningene og ber prover vise kub A.
Hvis terningene er i forskjellige farger, er alt ekstremt enkelt. Den prover vet at kuben A er, for eksempel, rød, og han vil peke den riktig hver gang.
Men hvis kubene har samme farge, det vil si at proveren fortalte en løgn og sa at fargen deres er annerledes, kan han bare gjette hvor kuben er. På grunn av dette vil han bare indikere dø A 50 prosent av tiden. Dette betyr at ved å gjentatte ganger spørre prover om løsningen, kan du bekrefte riktigheten.
"Sensoren kan stille spørsmålene til den ordentlige," sa Wright. "Og kanskje på slutten av samtalen vil verifiserens tillit øke."
I 1985 beviste en trio av programmerere at slike interaktive bevis kan brukes til å teste løsninger på problemer som er mer kompliserte enn NIP-klassen. Som et resultat av arbeidet deres dukket det opp en ny klasse problemer kalt IPT - interaktiv polynomisk tid. Metoden som brukes for å teste fargen på to terninger, kan brukes til å teste løsninger på mer komplekse problemer og spørsmål.
Det andre store skrittet ble tatt i samme tiår. Alt her følger logikken i en politietterforskning. Hvis du har to mistenkte som du mener har begått en forbrytelse, vil du ikke avhøre dem sammen. Du vil avhøre dem i forskjellige rom, og deretter sammenligne svarene de har gitt. Ved å avhøre disse menneskene hver for seg, kan du lære mer sannhet enn hvis du bare har en mistenkt.
"De to mistenkte vil ikke kunne komme med en plausibel og konsistent versjon fordi de rett og slett ikke kjenner hverandres svar," sa Wright.
I 1988 beviste en gruppe av fire informatikere at hvis to datamaskiner ble bedt om å løse det samme problemet hver for seg, og deretter spørres separat om svarene, så kunne en enda større klasse problemer testes enn IPV. Denne klassen kalles IDMD - interaktivt bevis med mange bevisere.
Ved å bruke denne tilnærmingen kan man for eksempel teste "tricolor" -problemer mot en sekvens av former som vokser i størrelse mye raskere enn former i nondeterministisk polynomisk tid. I ikke-deterministisk polynomisk tid øker størrelsen på formene lineært - antall tilkoblingspunkter på linjer kan øke fra 1 til 2, deretter til 3, deretter til 4, og så videre. Dermed vil det aldri være et stort misforhold i størrelsen på en figur med hvor lang tid det tar å teste tricolor. Men hvis vi snakker om et interaktivt bevis med mange bevisere, så øker antall poeng i figuren eksponentielt.
Som et resultat blir disse figurene for store og passer ikke inn i minnet til kontrolldatamaskinen, og det er grunnen til at den ikke kan sjekke trikoloren deres ved å gå gjennom listen over tilkoblingspunkter. Men det er fremdeles mulig å sjekke trikoloren ved å stille de to provisterne separate, men relaterte spørsmål.
I IDMD-problemklassen har sensoren nok minne til å kjøre et program for å avgjøre om to punkter i en form er forbundet med en linje. Den prover kan deretter be hver prover om å navngi en av de to prikkene som er forbundet med en linje, hvoretter han enkelt kan sammenligne provers 'svar for å sikre at den trefargede figuren er riktig.
Å øke nivået på oppgaver som er vanskelige å løse, men enkle å verifisere, fra NPV til IPV, og deretter til IDMD, kan oppnås gjennom klassiske datamaskiner. Kvantedatamaskiner fungerer annerledes. I flere tiår var det ikke klart hvordan de endrer bildet, det vil si om det er vanskeligere eller lettere å sjekke løsningen med deres hjelp.
Nytt arbeid av Natarajan og Wright gir et svar på dette spørsmålet.
KVANTUMMEDTAK
Kvantemaskiner utfører beregning ved å manipulere kvantebits (qubits). De har en merkelig egenskap, der essensen er at de kan forveksles med hverandre. Når to qubits, eller til og med store systemer med qubits, blir viklet inn i hverandre, betyr det at deres fysiske egenskaper spiller dem ut på en viss måte.
I sitt nye arbeid vurderer Natarajan og Wright et scenario med to separate kvantecomputere som deler vanlige sammenfiltrede qubits.
Det ser ut til at denne typen ordninger virker mot validering. Overtalelsesevnen for interaktivt bevis med mange bevisere forklares nettopp ved at du kan avhøre to provister hver for seg, og deretter sammenligne svarene deres. Hvis disse svarene stemmer, er de mest sannsynlig riktige. Men hvis to bevisstmenn er i en forvirret tilstand, så har de flere muligheter til konsekvent og konsekvent å gi gale svar.
Når et scenario med to sammenfiltrede kvantecomputere ble foreslått for første gang i 2003, antydet forskere at sammenfiltring ville svekke verifiseringsevnen. "Alle, inkludert meg, hadde en veldig åpenbar reaksjon: Nå skal beviserne ha mer styrke og overbevissthet," sa Vidik. "De kan bruke sammenfiltring for å koordinere svarene sine."
Til tross for denne innledende pessimismen, brukte Vidic flere år på å prøve å bevise noe annet. I 2012 beviste han, sammen med Tsuyoshi Ito, at det fortsatt er mulig å teste alle problemer i IDMD-klassen ved hjelp av sammenfiltrede kvantecomputere.
Nå har Natarajan og Wright bevist at situasjonen er enda bedre. En større klasse problemer kan testes med sammenfiltring enn uten det. Forbindelsene mellom sammenfiltrede kvantecomputere kan gjøres til glede for sensor.
For å forstå hvordan, la oss huske prosedyren for testing av trefargede figurer, hvis størrelse øker eksponentielt hvis et interaktivt bevis med mange provers brukes. Verifisereren har ikke nok minne til å lagre hele figuren, men nok til å identifisere to beslektede punkter og spør provene hvilken farge de er.
Hvis vi snakker om problemene som Natarajan og Wright vurderer - og de tilhører klassen kalt nondeterministic double exponential time (NDEW) - øker størrelsen på figuren i dem enda raskere enn i problemet med IDMD-klassen. Tallet i NDEV vokser med en "dobbel eksponentiell" hastighet. Det vil si at det er en dobbel geometrisk progresjon. Tallet øker ikke med hastigheten på 21., 22., 23. grad, men "i graden." På grunn av dette vokser formene så raskt at sensor ikke kan finne et eneste par sammenkoblede punkter.
"Det tar 2n biter for å markere et poeng, som er eksponentielt større enn verifiserens arbeidsminne," sier Natarajan.
Men Natarajan og Wright hevder at det er mulig å teste trefarges fargelegging av en dobbelt eksponentiell figur uten å være i stand til å bestemme hvilke punkter de skal spørre utøverne om. Poenget er at provene selv stiller spørsmål.
I følge forskere er ideen om å be datamaskiner om å sjekke sine egne beslutninger etter metoden for avstemning like rimelig som ideen om å be mistenkte om en forbrytelse å avhøre seg selv. Det vil si at dette er fullstendig tull. Riktig nok hevder Natarajan og Wright at dette ikke er tilfelle. Årsaken er forvirring.
"Innviklet tilstand er en delt ressurs," sier Wright. "Hele protokollen vår har som mål å forstå hvordan du bruker denne delte ressursen til å forberede relaterte spørsmål."
Hvis kvantecomputere er forvirrede, vil valg av punkter bli koblet sammen, og de vil gi riktig sett med spørsmål for å teste tricolor.
Samtidig trenger ikke sensoren at de to kvantemaskinene skal være for tett sammenkoblet, siden svarene deres på disse spørsmålene vil være konsistente (dette tilsvarer det faktum at to mistenkte er enige om hverandre om et falskt alibi). En annen merkelig kvantefunksjon løser dette problemet. I kvantemekanikk hindrer usikkerhetsprinsippet oss i å samtidig vite posisjonen til en partikkel og momentumet for dens styrke. Hvis du måler den ene, så ødelegg informasjonen om den andre. Usikkerhetsprinsippet begrenser din kunnskap om to "komplementære" egenskaper til et kvantesystem sterkt.
Natarajan og Wright utnyttet dette i arbeidet. For å beregne fargen på et toppunkt bruker de to kvantecomputere som utfyller hverandre med målinger. Hver datamaskin beregner fargen på poengene sine, og ødelegger den all informasjon om poengene til den andre datamaskinen. Med andre ord lar forviklinger datamaskiner formulere sammenhengende spørsmål, men usikkerhetsprinsippet hindrer dem i å konspirere for å svare på dem.
"Vi må få den prover til å glemme [fra den falske versjonen av hendelser], og dette er det viktigste de [Natarajan og Wright] gjorde i arbeidet sitt," sa Vidik. "De tvinger prover til å fjerne informasjonen når han tar målinger."
Deres arbeid har enorme og veldig viktige konsekvenser. Før dette arbeidet dukket opp, var grensen for mengden kunnskap vi kunne ha med full tillit betydelig lavere. Hvis vi fikk svar på IDMD-problemet, ville vi måtte akseptere det på tro, siden vi ikke har noe annet valg. Men Natarajan og Wright fjernet denne begrensningen og gjorde det mulig å validere svar på mange flere beregningsproblemer.
Men nå som de har gjort det, er det ikke klart hvor valideringsgrensen er.
"Dette kan gå mye lenger," sa Lance Fortnow, en datavitenskapelig forsker ved Georgia Institute of Technology. "De gir plass til enda et skritt."
Kevin Hartnett
