Scienziati negli Stati Uniti hanno scoperto come testare problemi che non sono ancora disponibili per gli esseri umani. Gli scienziati usano lo stesso metodo degli investigatori della polizia nel loro dialogo con i computer che risolvono questi problemi. "Confondono" l'interrogato, interrogano due macchine separatamente, ecc. Anche la meccanica quantistica viene utilizzata.
Immagina: un uomo viene da te e ti dice che ha un indovino e che questo indovino può rivelare i segreti incomprensibili dell'universo. Sei incuriosito, ma difficilmente gli credi. Sicuramente vorrai assicurarti che il rabdomante stia dicendo la verità, e per questo avrai bisogno di un modo o di un metodo.
Questa è l'essenza di uno dei principali problemi dell'informatica. Alcune attività sono troppo difficili da eseguire in un lasso di tempo ragionevole. Ma la loro soluzione è facile da verificare. Per questo motivo, gli informatici vogliono sapere: quanto può essere complesso un problema che ha una soluzione verificabile?
Si scopre che la risposta è: può essere incredibilmente complesso.
Ad aprile, due informatici hanno pubblicato un documento di ricerca che ha moltiplicato il numero di problemi difficili da risolvere, ma facili da verificare. Hanno descritto un metodo per testare soluzioni a problemi di complessità quasi incredibile. "Sembra una follia", ha detto Thomas Vidick, uno scienziato informatico presso il California Institute of Technology, che non è stato coinvolto in questo nuovo lavoro.
La ricerca riguarda i computer quantistici che eseguono calcoli secondo le regole contraddittorie della meccanica quantistica. I computer quantistici stanno appena iniziando a emergere, ma in futuro potrebbero rivoluzionare il calcolo e il calcolo.
Infatti, la nuova ricerca scientifica condotta ci offre l'opportunità di influenzare il rabdomante descritto all'inizio dell'articolo. Anche se promette di darci risposte a quei problemi che noi stessi non siamo in grado di risolvere, quindi anche in questa situazione apparentemente senza speranza, avremo comunque un modo per mettere alla prova l'indovino e assicurarci che stia dicendo la verità (o ingannando).
Video promozionale:
ALLA MORTE DELL'UNIVERSO
Quando un problema è difficile da risolvere, ma facile da verificare, trovare una soluzione richiede molto tempo, ma controllare la correttezza della soluzione data non lo è.
Ecco un esempio. Immagina di ricevere un disegno. È una raccolta di punti (vertici) collegati da linee (bordi). Ti viene chiesto se è possibile dipingere questi punti di una forma con solo tre colori in modo che i punti collegati da linee siano di colori diversi.
Questo problema dei "tre colori" è difficile da risolvere. In generale, il tempo necessario per comporre una figura a tre colori (o per determinare che non può esistere) cresce in modo esponenziale all'aumentare delle dimensioni della figura. Ad esempio, se una figura ha 20 punti di connessione di linee, la soluzione del problema richiede 3 alla ventesima potenza di nanosecondi, cioè diversi secondi in termini di unità di tempo a cui siamo abituati. Ma se la cifra è di 60 punti, la ricerca di una soluzione richiederà 100 volte più tempo della nostra età stimata dell'universo.
Ma immaginiamo: qualcuno afferma di aver realizzato una figura così tricolore. Ci vorrà un po 'di tempo per verificare la veridicità della sua dichiarazione. Inizieremo solo a controllare i punti di connessione delle linee uno per uno. Man mano che la cifra aumenta, anche il tempo di controllo aumenterà lentamente. Questo è il cosiddetto tempo polinomiale. Di conseguenza, si scopre che il computer non impiega molto più tempo per controllare una figura a tre colori con 60 vertici rispetto a una figura con 20 punti di connessione.
"È abbastanza facile testare che questo circuito funzioni, purché sia una figura reale a tre colori", afferma il fisico del MIT John Wright, che sta scrivendo un nuovo articolo con Anand Natarajan del Caltech. …
Negli anni '70, i programmatori hanno identificato una classe di problemi facili da testare, anche se a volte difficili da risolvere. Hanno dato a questa classe il nome NPT - tempo polinomiale non deterministico. Da allora, molti scienziati informatici hanno studiato questi problemi molto intensamente. In particolare, gli scienziati vogliono sapere come cambia questa classe di problemi quando l'ispettore ha nuovi modi per verificare la correttezza della soluzione.
DOMANDE CORRETTE
Prima del lavoro di Natarajan e Wright, sono state fatte due importanti scoperte per verificare la correttezza della soluzione. Hanno notevolmente aumentato la nostra capacità di testare problemi super difficili.
Per comprendere l'essenza della prima scoperta rivoluzionaria, immagina di essere daltonico. Due cubi vengono posti sul tavolo di fronte a te e ti viene chiesto se sono dello stesso colore o diversi. Questo compito è impossibile per te. Inoltre, non sei in grado di mettere alla prova la decisione di un'altra persona.
Ma puoi interrogare questa persona, che chiameremo il prover. Diciamo che il prover ti dice che un paio di cubi sono di colori diversi. Designeremo il primo cubo con la lettera "A" e il secondo con la lettera "B". Prendi i cubetti, nascondili dietro la schiena e trasferiscili di mano in mano più volte. Quindi mostri i cubi e chiedi al prover di mostrare il cubo A.
Se i cubi sono di colori diversi, tutto è estremamente semplice. Il prover sa che il cubo A è, diciamo, rosso e lo indicherà correttamente ogni volta.
Ma se i cubi sono dello stesso colore, cioè il prover ha detto una bugia, dicendo che il loro colore è diverso, può solo indovinare dove si trova il cubo. Per questo motivo, indicherà correttamente die A solo il 50% delle volte. Ciò significa che chiedendo ripetutamente al prover la soluzione, è possibile verificarne la correttezza.
"L'esaminatore può porre domande al prover", ha detto Wright. "E forse alla fine della conversazione, la fiducia del verificatore aumenterà".
Nel 1985, un trio di programmatori ha dimostrato che tali dimostrazioni interattive possono essere utilizzate per testare soluzioni a problemi più complessi della classe NIP. Come risultato del loro lavoro, è apparsa una nuova classe di problemi chiamata IPT: tempo polinomiale interattivo. Il metodo utilizzato per testare il colore di due cubi può essere utilizzato per testare soluzioni a problemi e domande più complessi.
Il secondo grande passo è stato compiuto nello stesso decennio. Tutto qui segue la logica di un'indagine della polizia. Se hai due sospetti che ritieni abbiano commesso un crimine, non li interrogherai insieme. Li interrogherai in stanze diverse e poi confronterai le risposte fornite da loro. Interrogando queste persone separatamente, puoi apprendere più verità che se avessi un solo sospetto.
"I due sospetti non saranno in grado di trovare una versione plausibile e coerente perché semplicemente non conosceranno le risposte l'uno dell'altro", ha detto Wright.
Nel 1988, un gruppo di quattro scienziati informatici ha dimostrato che se si chiedesse a due computer di risolvere lo stesso problema separatamente, e poi si interrogassero separatamente sulle risposte, allora si poteva testare una classe di problemi ancora più ampia dell'IPV. Questa classe si chiama IDMD - prova interattiva con molti dimostratori.
Usando questo approccio, si possono, ad esempio, testare problemi "tricolori" su una sequenza di forme che crescono di dimensioni molto più velocemente delle forme in un tempo polinomiale non deterministico. Nel tempo polinomiale non deterministico, la dimensione delle forme aumenta linearmente: il numero di punti di connessione delle linee può aumentare da 1 a 2, quindi a 3, quindi a 4 e così via. Pertanto, non ci sarà mai un'enorme disparità nelle dimensioni di una figura con la quantità di tempo necessaria per testare il suo tricolore. Ma se stiamo parlando di una dimostrazione interattiva con molti dimostratori, allora qui il numero di punti nella figura aumenta in modo esponenziale.
Di conseguenza, queste cifre diventano troppo grandi e non si adattano alla memoria del computer di controllo, motivo per cui non può controllare il loro tricolore scorrendo l'elenco dei punti di collegamento. Ma è ancora possibile controllare il tricolore ponendo ai due sperimentatori domande separate ma correlate.
Nella classe di problemi IDMD, l'esaminatore ha memoria sufficiente per eseguire un programma per determinare se due punti in una forma sono collegati da una linea. Lo sperimentatore può quindi chiedere a ogni sperimentatore di nominare uno dei due punti collegati da una linea, dopodiché può facilmente confrontare le risposte degli sperimentatori per assicurarsi che la figura a tre colori sia corretta.
L'aumento del livello delle attività difficili da risolvere, ma facili da verificare, da NPV a IPV, e quindi a IDMD, potrebbe essere ottenuto tramite computer classici. I computer quantistici funzionano in modo diverso. Per decenni non è stato chiaro come cambiassero il quadro, cioè se fosse più difficile o più facile verificare la soluzione con il loro aiuto.
Un nuovo lavoro di Natarajan e Wright fornisce una risposta a questa domanda.
INGANNO QUANTISTICO
I computer quantistici eseguono il calcolo manipolando i bit quantistici (qubit). Hanno una strana proprietà, la cui essenza è che possono confondersi l'uno con l'altro. Quando due qubit, o anche grandi sistemi di qubit, si intrecciano l'uno con l'altro, significa che le loro proprietà fisiche li riproducono in un certo modo.
Nel loro nuovo lavoro, Natarajan e Wright considerano uno scenario con due computer quantistici separati che condividono qubit entangled comuni.
Sembrerebbe che questo tipo di schema funzioni contro la convalida. La capacità di persuasione di una dimostrazione interattiva con molti dimostratori è dovuta proprio al fatto che puoi interrogare due sperimentatori separatamente e poi confrontare le loro risposte. Se queste risposte corrispondono, molto probabilmente sono corrette. Ma se due sperimentatori sono in uno stato confuso, allora hanno più opportunità di dare costantemente e costantemente risposte sbagliate.
Infatti, quando nel 2003 è stato proposto per la prima volta uno scenario con due computer quantistici collegati, gli scienziati hanno suggerito che l'entanglement indebolirebbe le capacità di verifica. "Tutti, me compreso, hanno avuto una reazione molto ovvia: ora i provers avranno più forza e persuasività", ha detto Vidik. "Possono usare l'entanglement per coordinare le loro risposte".
Nonostante questo iniziale pessimismo, Vidic ha trascorso diversi anni cercando di dimostrare il contrario. Nel 2012, lui e Tsuyoshi Ito hanno dimostrato che è ancora possibile testare tutti i problemi nella classe IDMD utilizzando computer quantistici entangled.
Ora Natarajan e Wright hanno dimostrato che la situazione è ancora migliore. Una classe più ampia di problemi può essere testata con l'entanglement che senza di essa. Le connessioni tra computer quantistici entangled possono essere trasformate a vantaggio dell'esaminatore.
Per capire come si fa, ricordiamo la procedura per il controllo delle figure tricolore, la cui dimensione aumenta in modo esponenziale se si utilizza una dimostrazione interattiva con più provers. Il verificatore non ha memoria sufficiente per memorizzare l'intera figura, ma sufficiente per identificare due punti correlati e chiedere ai prover di che colore sono.
Se parliamo dei problemi che Natarajan e Wright considerano - e appartengono alla classe chiamata tempo doppio esponenziale non deterministico (NDEW) - allora la dimensione della cifra in essi aumenta ancora più velocemente che nel problema della classe IDMD. La cifra in NDEV sta crescendo a un ritmo "doppio esponenziale". Cioè, è una doppia progressione geometrica. La cifra non aumenta con la velocità del 21 °, 22 °, 23 ° grado, ma "nel grado di gradi". Per questo motivo, le forme crescono così rapidamente che l'esaminatore non riesce a trovare una singola coppia di punti collegati.
"Sono necessari 2n bit per contrassegnare un punto, che è esponenzialmente più grande della memoria di lavoro del verificatore", afferma Natarajan.
Ma Natarajan e Wright sostengono che è possibile testare la colorazione a tre colori di una figura doppiamente esponenziale senza essere in grado di determinare su quali punti interrogarsi. Il punto è che gli stessi sperimentatori fanno domande.
Secondo gli scienziati, l'idea di chiedere ai computer di controllare le proprie decisioni con il metodo del sondaggio è ragionevole quanto l'idea di chiedere ai sospettati di un crimine di interrogarsi. Cioè, questa è una totale assurdità. È vero, Natarajan e Wright sostengono che non è così. Il motivo è la confusione.
"Lo stato di entangled è una risorsa condivisa", afferma Wright. "Il nostro intero protocollo mira a capire come utilizzare questa risorsa condivisa per preparare domande correlate".
Se i computer quantistici sono confusi, la loro scelta di punti sarà interconnessa e daranno la giusta serie di domande per testare il tricolore.
Allo stesso tempo, l'esaminatore non ha bisogno che i due computer quantistici siano troppo strettamente interconnessi, poiché le loro risposte a queste domande saranno coerenti (ciò equivale al fatto che due sospetti concordano tra loro su un falso alibi). Un'altra strana caratteristica quantistica risolve questo problema. Nella meccanica quantistica, il principio di indeterminazione ci impedisce di conoscere simultaneamente la posizione di una particella e la quantità di moto della sua forza. Se ne misuri uno, distruggi le informazioni sull'altro. Il principio di indeterminazione limita fortemente la tua conoscenza di due proprietà "complementari" di un sistema quantistico.
Natarajan e Wright ne hanno approfittato nel loro lavoro. Per calcolare il colore di un vertice, usano due computer quantistici che si completano a vicenda con misurazioni. Ogni computer calcola il colore dei suoi punti e, così facendo, distrugge tutte le informazioni sui punti dell'altro computer. In altre parole, l'entanglement consente ai computer di formulare domande correlate, ma il principio di indeterminazione impedisce loro di cospirare nel rispondere.
"Dobbiamo far dimenticare allo sperimentatore [la falsa versione degli eventi], e questa è la cosa principale che loro [Natarajan e Wright] hanno fatto nel loro lavoro", ha detto Vidik. "Costringono il prover a rimuovere le informazioni quando prende le misurazioni."
Il loro lavoro ha conseguenze enormi e molto importanti. Prima che questo lavoro apparisse, il limite alla quantità di conoscenza che potevamo avere con completa fiducia era significativamente inferiore. Se ci fosse data una risposta al problema dell'IDMD, dovremmo accettarla per fede, poiché non abbiamo altra scelta. Ma Natarajan e Wright hanno rimosso questa limitazione e hanno reso possibile convalidare le risposte a molti altri problemi di calcolo.
Ma ora che lo hanno fatto, non è chiaro dove sia il limite di convalida.
"Questo potrebbe andare molto oltre", ha detto Lance Fortnow, un ricercatore di informatica presso il Georgia Institute of Technology. "Lasciano spazio per un altro passo."
Kevin Hartnett
