Forskere i De Forenede Stater har fundet ud af, hvordan man tester problemer, der endnu ikke er tilgængelige for mennesker. Forskere bruger den samme metode som politiets efterforskere i deres dialog med computere, der løser disse problemer. De "forvirrer" de forhørte, forhører to biler hver for sig osv. Selv kvantemekanik bruges.
Forestil dig: en mand kommer til dig og siger, at han har en beroligende, og at denne beroligede kan afsløre universets uforståelige hemmeligheder. Du er fascineret, men du tror næppe ham. Du vil bestemt sørge for, at divineren fortæller sandheden, og til dette har du brug for en eller anden måde eller metode.
Dette er essensen af et af de vigtigste problemer inden for datalogi. Nogle opgaver er for vanskelige at udføre inden for en rimelig tidsramme. Men deres løsning er let at verificere. Af denne grund vil computerforskere vide: Hvor komplekst kan et problem være, der har en verificerbar løsning?
Det viser sig, at svaret er: det kan være utroligt komplekst.
I april offentliggjorde to datalogi et forskningsdokument, der multiplicerede antallet af problemer, der er vanskelige at løse, men let at verificere. De beskrev en metode til test af løsninger på problemer med næsten utrolig kompleksitet.”Det lyder som vanvittigt,” sagde Thomas Vidick, en datalogi ved California Institute of Technology, som ikke var involveret i dette nye arbejde.
Forskningen vedrører kvantecomputere, der udfører beregninger i henhold til de modstridende regler for kvantemekanikken. Kvantecomputere er lige begyndt at dukke op, men i fremtiden kan de revolutionere beregning og beregning.
Faktisk giver den nye videnskabelige undersøgelse os muligheden for at påvirke den diviner, der er beskrevet i begyndelsen af artiklen. Selv hvis han lover at give os svar på de problemer, som vi selv ikke er i stand til at løse, så selv i denne tilsyneladende håbløse situation, vil vi stadig have en måde at teste beroligeren og sørge for, at han fortæller sandheden (eller bedrag).
Salgsfremmende video:
TIL UNIVERSETS DØD
Når et problem er vanskeligt at løse, men let at verificere, tager det en masse tid at finde en løsning, men det er ikke tilfældet at kontrollere rigtigheden af den givne løsning.
Her er et eksempel. Forestil dig at få en tegning. Det er en samling af punkter (hjørner), der er forbundet med linjer (kanter). Du bliver spurgt, om det er muligt at male disse punkter af en form med kun tre farver, så punkterne, der er forbundet med linjer, er af forskellige farver.
Dette "trefarve" problem er vanskeligt at løse. Generelt vokser den tid, det tager at komponere en trefarvefigur (eller for at bestemme, at den ikke kan eksistere) eksponentielt, når tallet øges i størrelse. For eksempel, hvis et tal har 20 punkter med forbindelse af linjer, tager løsningen af problemet 3 til den tyvende magt af nanosekunder, det vil sige flere sekunder med hensyn til de tidsenheder, vi er vant til. Men hvis tallet er på 60 point, tager søgningen efter en løsning 100 gange længere tid end vores estimerede alder på universet.
Men lad os forestille os: nogen hævder at have lavet en sådan trefarvet figur. Det vil tage os lidt tid at kontrollere ægtheden af hans erklæring. Vi begynder bare at kontrollere forbindelsespunkterne på linjerne en efter en. Efterhånden som tallet vokser, øges også kontrolletiden langsomt. Dette er den såkaldte polynomietid. Som et resultat viser det sig, at computeren ikke tager meget mere tid til at kontrollere en trefarvefigur med 60 vertices end den gør for at kontrollere et tal med 20 forbindelsespunkter.
"Det er temmelig let at teste, at dette kredsløb fungerer, så længe det er en rigtig figur i tre farver," siger MIT-fysiker John Wright, som co-skrev et nyt papir sammen med Caltechs Anand Natarajan. …
I 1970'erne identificerede programmerere en klasse af problemer, der er lette at teste, selvom nogle gange er vanskelige at løse. De gav denne klasse navnet NPT - ikke-deterministisk polynomisk tid. Siden da har mange edb-forskere undersøgt disse problemer meget intenst. Især ønsker forskere at vide, hvordan denne klasse af problemer ændrer sig, når inspektøren har nye måder at kontrollere, om løsningen er korrekt.
KORREKTE SPØRGSMÅL
Før Natarajan og Wrights arbejde blev der gjort to vigtige opdagelser for at verificere rigtigheden af løsningen. De har øget vores evne til at teste superharde problemer kraftigt.
For at forstå essensen af den første breakout-opdagelse, forestil dig, at du er farveblind. To terninger er placeret på bordet foran dig, og du bliver spurgt, om de er i samme farve eller forskellige. Denne opgave er umulig for dig. Derudover er du ikke i stand til at teste en anden persons beslutning.
Men du har tilladelse til at stille spørgsmål til denne person, som vi vil kalde prover. Lad os sige, at prover fortæller dig, at et par terninger er forskellige farver. Vi udpeger den første terning med bogstavet "A" og den anden med bogstavet "B". Du tager terningerne, skjuler dem bag din ryg og overfører dem fra hånd til hånd flere gange. Så viser du terningerne og beder prover om at vise terning A.
Hvis terningerne har forskellige farver, er alt ekstremt enkelt. Den prover ved, at terningen A er, siger, rød, og han vil pege den korrekt hver gang.
Men hvis terningerne har den samme farve, det vil sige den prover, der lyder og sagde, at deres farve er anderledes, kan han kun gætte, hvor kuben er. På grund af dette angiver han kun korrekt A 50 procent af tiden. Dette betyder, at du ved at gentagne gange spørge prover om løsningen kan bekræfte dens korrekthed.
”Undersøgeren kan stille spørgsmålene,” sagde Wright. "Og måske i slutningen af samtalen vil verifikatorens tillid øges."
I 1985 beviste en trio af programmerere, at sådanne interaktive bevis kan bruges til at teste løsninger på problemer, der er mere komplekse end NIP-klassen. Som et resultat af deres arbejde dukkede en ny klasse af problemer kaldet IPT op - interaktiv polynomisk tid. Metoden, der bruges til at teste farven på to terninger, kan bruges til at teste løsninger til mere komplekse problemer og spørgsmål.
Det andet store skridt blev taget i det samme årti. Alt her følger logikken i en politiundersøgelse. Hvis du har to mistænkte, som du mener har begået en forbrydelse, vil du ikke forhøre dem sammen. Du vil forhøre dem i forskellige rum og derefter sammenligne de svar, de har givet. Ved at forhøre disse mennesker separat, kan du lære mere sandhed, end hvis du kun har en mistænkt.
”De to mistænkte vil ikke være i stand til at komme med en plausibel og konsekvent version, fordi de simpelthen ikke kender hinandens svar,” sagde Wright.
I 1988 beviste en gruppe af fire datalogikere, at hvis to computere blev bedt om at løse det samme problem hver for sig, og derefter adskilles separat om svarene, så kunne en endnu bredere klasse af problemer testes end IPV. Denne klasse kaldes IDMD - interaktivt bevis med mange provere.
Ved hjælp af denne fremgangsmåde kan man for eksempel teste "tricolor" -problemer mod en række af former, der vokser i størrelse meget hurtigere end former i ikke-deterministisk polynomisk tid. I ikke-deterministisk polynomisk tid stiger formenes størrelse lineært - antallet af forbindelsespunkter på linjer kan stige fra 1 til 2, derefter til 3, derefter til 4, og så videre. Således vil der aldrig være en stor forskel i størrelsen på en figur med den tid det tager at teste dens tricolor. Men hvis vi taler om et interaktivt bevis med mange provere, så stiger antallet af point i figuren eksponentielt.
Som et resultat bliver disse tal for store og passer ikke ind i hukommelsen på kontrolcomputeren, hvorfor han ikke kan kontrollere deres tricolor ved at køre gennem listen over forbindelsespunkter. Men det er stadig muligt at kontrollere tricolor ved at stille de to provister adskilte, men beslægtede spørgsmål.
I IDMD-problemklassen har censoren nok hukommelse til at køre et program til at bestemme, om to punkter i en form er forbundet med en linje. Den prover kan derefter bede hver prover om at navngive en af de to prikker, der er forbundet med en linje, hvorefter han let kan sammenligne provernes svar for at sikre sig, at den trefarvede figur er korrekt.
Forøgelse af niveauet for opgaver, der er vanskelige at løse, men let at verificere, fra NPV til IPV og derefter til IDMD, kunne opnås gennem klassiske computere. Kvantecomputere fungerer forskelligt. I årtier var det ikke klart, hvordan de ændrer billedet, det vil sige, om det er vanskeligere eller lettere at tjekke løsningen med deres hjælp.
Nyt arbejde af Natarajan og Wright giver et svar på dette spørgsmål.
KVANTUMMECEPTION
Kvantecomputere udfører beregning ved at manipulere kvantebits (qubits). De har en mærkelig egenskab, hvis væsentlighed er, at de kan forveksles med hinanden. Når to qubits, eller endda store systemer af qubits, bliver sammenfiltret med hinanden, betyder det, at deres fysiske egenskaber spiller dem ud på en bestemt måde.
I deres nye arbejde overvejer Natarajan og Wright et scenarie med to separate kvantecomputere, der deler fælles sammenfiltrede qubits.
Det ser ud til, at denne form for ordning fungerer imod validering. Overtalelsesevnen for interaktivt bevis med mange provister forklares netop af det faktum, at du kan forhøre to provister hver for sig og derefter sammenligne deres svar. Hvis disse svar stemmer overens, er de sandsynligvis rigtige. Men hvis to provister er i forvirret tilstand, har de flere muligheder for konsekvent og konsekvent at give forkerte svar.
Da et scenarie med to sammenfiltrede kvantecomputere først blev foreslået i 2003, foreslog forskere, at sammenfiltring ville svække verifikationskapaciteten.”Alle, inklusive mig, havde en meget indlysende reaktion: Nu vil provisterne have mere styrke og overtalelsesevne,” sagde Vidik. "De kan bruge sammenfiltring til at koordinere deres svar."
På trods af denne indledende pessimisme tilbragte Vidic flere år på at bevise andet. I 2012 beviste han sammen med Tsuyoshi Ito, at det stadig er muligt at teste alle problemer i IDMD-klassen ved hjælp af sammenfiltrede kvantecomputere.
Nu har Natarajan og Wright bevist, at situationen er endnu bedre. En bredere klasse af problemer kan testes med sammenfiltring end uden den. Forbindelserne mellem sammenfiltrede kvantecomputere kan vendes til eksaminatorens fordel.
For at forstå hvordan, lad os huske proceduren til test af trefarvede figurer, hvis størrelse øges eksponentielt, hvis der bruges et interaktivt bevis med mange provister. Verifikatoren har ikke nok hukommelse til at gemme hele figuren, men nok til at identificere to relaterede punkter og spørge provisterne, hvilken farve de er.
Hvis vi taler om de problemer, som Natarajan og Wright overvejer - og de hører til klassen kaldet nondeterministisk dobbelt eksponentiel tid (NDEW) - øges størrelsen på tallet i dem endnu hurtigere end i problemet med IDMD-klassen. Tallet i NDEV vokser med en "dobbelt eksponentiel" hastighed. Det vil sige, det er en dobbelt geometrisk progression. Tallet stiger ikke med hastigheden på den 21., 22., 23. grad, men "i graden." På grund af dette vokser figurerne så hurtigt, at eksaminatoren ikke kan finde et enkelt par forbundne punkter.
”Det tager 2n bits at markere et punkt, som er eksponentielt større end verifikatorens arbejdshukommelse,” siger Natarajan.
Men Natarajan og Wright hævder, at det er muligt at teste trefarvefarvningen af en dobbelt eksponentiel figur uden at være i stand til at bestemme, hvilke punkter man skal spørge provisterne om. Pointen er, at provisterne selv stiller spørgsmål.
I følge videnskabsmænd er ideen om at bede computere om at kontrollere deres egne beslutninger ved metoden til afstemning lige så rimelig som ideen om at bede mistænkte for en forbrydelse om at forhøre sig selv. Det vil sige, dette er komplet vrøvl. Sandt nok hævder Natarajan og Wright, at dette ikke er tilfældet. Årsagen er forvirring.
"Indviklet tilstand er en delt ressource," siger Wright. "Hele protokollen har til formål at forstå, hvordan vi bruger denne delte ressource til at forberede relaterede spørgsmål."
Hvis kvantecomputere forveksles, forbindes deres valg af punkter sammen, og de giver det rigtige sæt spørgsmål til at teste tricolor.
Samtidig behøver eksaminatoren ikke, at de to kvantecomputere skal være for tæt forbundne, da deres svar på disse spørgsmål vil være konsistente (dette svarer til det faktum, at to mistænkte er enige om hinanden om et falskt alibi). En anden underlig kvantefunktion løser dette problem. I kvantemekanik forhindrer usikkerhedsprincippet os i at kende samtidig en partikels position og momentum for dens kraft. Hvis du måler den ene, skal du ødelægge oplysninger om den anden. Usikkerhedsprincippet begrænser din viden om to "komplementære" egenskaber ved et kvantesystem kraftigt.
Natarajan og Wright udnyttede dette i deres arbejde. For at beregne farve på et toppunkt bruger de to kvantecomputere, der komplementerer hinanden med målinger. Hver computer beregner farven på sine point, og på den måde ødelægger den al information om punkterne på den anden computer. Med andre ord tillader forviklinger computere at formulere indbyrdes forbundne spørgsmål, men usikkerhedsprincippet forhindrer dem i at konspirere for at besvare dem.
”Vi er nødt til at få den oprigtige til at glemme [om den falske version af begivenheder], og dette er det vigtigste, som de [Natarajan og Wright] gjorde i deres arbejde,” sagde Vidik. "De tvinger prover til at fjerne oplysningerne, når han foretager målinger."
Deres arbejde har enorme og meget vigtige konsekvenser. Inden dette arbejde blev vist, var grænsen for mængden af viden, vi kunne have med fuld tillid, væsentligt lavere. Hvis vi fik et svar på IDMD-problemet, ville vi være nødt til at acceptere det på tro, da vi ikke har noget andet valg. Men Natarajan og Wright fjernede denne begrænsning og gjorde det muligt at validere svar på mange flere beregningsproblemer.
Men nu, når de har gjort det, er det ikke klart, hvor valideringsgrænsen er.
"Dette kunne gå meget længere," sagde Lance Fortnow, en datalogi-forsker ved Georgia Institute of Technology. "De giver plads til endnu et skridt."
Kevin Hartnett