MIP ^* =RE non è un errore di battitura. È una scoperta rivoluzionaria e il titolo accattivante di un recente articolo nel campo della teoria della complessità quantistica. La teoria della complessità è uno zoo di "classi di complessità" - raccolte di problemi computazionali - di cui MIP ^* e RE non sono che due.

Il documento di 165 pagine mostra che queste due classi sono le stesse. Può sembrare un dettaglio insignificante in una teoria astratta senza alcuna applicazione nel mondo reale. Ma fisici e matematici si stanno accalcando per visitare lo zoo, anche se probabilmente non capiscono tutto. Perché si scopre che la scoperta ha conseguenze sorprendenti per le loro stesse discipline.

Nel 1936, Alan Turing ha mostrato che il problema dell'arresto, ovvero decidere algoritmicamente se un programma per computer si interrompe o si interrompe per sempre, non può essere risolto. Nasce l'informatica moderna. Il suo successo diede l'impressione che presto tutti i problemi pratici avrebbero ceduto all'enorme potenza del computer.

Ma presto divenne evidente che, mentre alcuni problemi possono essere risolti algoritmicamente, il calcolo effettivo durerà molto tempo dopo che il nostro Sole avrà inghiottito il computer che esegue il calcolo. Capire come risolvere un problema algoritmicamente non era abbastanza. Era fondamentale classificare le soluzioni in base all'efficienza. La teoria della complessità classifica i problemi in base a quanto sia difficile risolverli. La durezza di un problema si misura in termini di durata del calcolo.

RE sta per problemi che possono essere risolti da un computer. È lo zoo. Diamo un'occhiata ad alcune sottoclassi.

La classe P è costituita da problemi che un algoritmo noto può risolvere rapidamente (tecnicamente, in tempo polinomiale). Ad esempio, la moltiplicazione di due numeri appartiene a P poiché la moltiplicazione lunga è un algoritmo efficiente per risolvere il problema. Il problema di trovare i fattori primi di un numero non è noto per essere in P; il problema può certamente essere risolto da un computer ma nessun algoritmo conosciuto può farlo in modo efficiente. Un problema correlato, decidere se un dato numero è primo, era in un limbo simile fino al 2004, quando un algoritmo efficiente ha mostrato che questo problema è in P.

Un'altra classe di complessità è NP. Immagina un labirinto. "C'è una via d'uscita da questo labirinto?" è una domanda si/no. Se la risposta è sì, allora c'è un modo semplice per convincerci:semplicemente darci le indicazioni, li seguiremo, e troveremo l'uscita. Se la risposta è no, però, dovremmo attraversare l'intero labirinto senza mai trovare una via d'uscita per convincerci.

Tali problemi si/no per i quali, se la risposta è sì, possiamo dimostrare efficacemente che, appartengono a NP. Qualsiasi soluzione a un problema serve a convincerci della risposta, e quindi P è contenuto in NP. Sorprendentemente, una domanda da un milione di dollari è se P=NP. Nessuno sa.

Fidati delle macchine

Le classi fin qui descritte rappresentano problemi affrontati da un normale computer. Ma i computer stanno cambiando radicalmente:si stanno sviluppando computer quantistici. Ma se arriva un nuovo tipo di computer e pretende di risolvere uno dei nostri problemi, come possiamo fidarci che sia corretto?

Immagina un'interazione tra due entità, un interrogatore e un prover. In un interrogatorio di polizia, il prover potrebbe essere un sospetto che cerca di dimostrare la propria innocenza. L'interrogante deve decidere se il prover è sufficientemente convincente. C'è uno squilibrio; dal punto di vista della conoscenza l'interrogatore è in una posizione inferiore.

Nella teoria della complessità, l'interrogatore è la persona, con potenza di calcolo limitata, cercando di risolvere il problema. Il prover è il nuovo computer, che si presume abbia un immenso potere di calcolo. Un sistema di prova interattivo è un protocollo che l'interrogante può utilizzare per determinare, almeno con alta probabilità, se si deve credere al prover. Per analogia, questi sono crimini che la polizia potrebbe non essere in grado di risolvere, ma almeno gli innocenti possono convincere la polizia della loro innocenza. Questa è la classe IP.

Se è possibile interrogare più prover, e i prover non sono autorizzati a coordinare le loro risposte (come di solito accade quando la polizia interroga più sospetti), poi arriviamo alla classe MIP. Tali interrogatori, attraverso l'esame incrociato delle risposte dei prover, fornire all'interrogatore un potere maggiore, quindi MIP contiene IP.

La comunicazione quantistica è una nuova forma di comunicazione effettuata con i qubit. Entanglement:una caratteristica quantistica in cui i qubit sono aggrovigliati in modo spettrale, anche se separati, rende la comunicazione quantistica fondamentalmente diversa dalla comunicazione ordinaria. Consentire ai prover di MIP di condividere un qubit entangled porta alla classe MIP ^*.

Sembra ovvio che la comunicazione tra i prover possono solo servire ad aiutare i prover a coordinare le bugie piuttosto che aiutare l'interrogatore a scoprire la verità. Per tale motivo, nessuno si aspettava che consentire una maggiore comunicazione avrebbe reso i problemi computazionali più affidabili e risolvibili. Sorprendentemente, ora sappiamo che MIP ^* =RE. Ciò significa che la comunicazione quantistica si comporta in modo molto diverso dalla comunicazione normale.

Implicazioni di vasta portata

Negli anni '70, Alain Connes formulò quello che divenne noto come il problema dell'incorporamento di Connes. Grossolanamente semplificato, questo chiedeva se matrici infinite possono essere approssimate da matrici finite. Questo nuovo articolo ha ora dimostrato che ciò non è possibile, una scoperta importante per i matematici puri.

Nel 1993, nel frattempo, Boris Tsirelson ha individuato un problema in fisica ora noto come problema di Tsirelson. Si trattava di due diversi formalismi matematici di una singola situazione nella meccanica quantistica:fino ad oggi una teoria di incredibile successo che spiega il mondo subatomico. Essendo due descrizioni diverse dello stesso fenomeno c'era da aspettarsi che i due formalismi fossero matematicamente equivalenti.

Ma il nuovo documento ora mostra che non lo sono. Non è noto come esattamente possano entrambi produrre gli stessi risultati ed entrambi descrivere la stessa realtà fisica, ma è per questo che anche i fisici si stanno improvvisamente interessando.

Il tempo dirà quali altre domande scientifiche senza risposta porteranno allo studio della complessità. indubbiamente, MIP ^* =RE è un grande balzo in avanti.

Questo articolo è stato ripubblicato da The Conversation con una licenza Creative Commons. Leggi l'articolo originale.