Unitary complexity in polynomial space

Nel mondo dell'informatica, esiste una divisione fondamentale tra ciò che una macchina può fare velocemente e ciò che può fare se dotata di una vasta quantità di memoria. Per decenni, gli scienziati dell'informatica hanno mappato questi territori, creando categorie per i problemi facili da risolvere, i problemi difficili da risolvere e i problemi che sembrano impossibili da risolvere entro un tempo ragionevole. Una domanda centrale in questo campo è se la capacità di utilizzare più memoria permetta a un computer di risolvere problemi che sono strettamente fuori portata per un computer con memoria limitata. Sebbene abbiamo forti sospetti sulle risposte, molte di queste domande rimangono non dimostrate.

Parallelamente a questo mondo classico, esiste il regno dell'informatica quantistica, dove le macchine utilizzano le strane proprietà delle particelle subatomiche per elaborare informazioni. Qui, le regole sono diverse. Un computer quantistico non si limita a invertire i bit tra acceso e spento; manipola complesse onde di probabilità. Ciò gli consente di eseguire determinati compiti che richiederebbero a un computer classico un'eternità. Tuttavia, un profondo mistero persiste: il potere dell'informatica quantistica dipende da un tipo di difficoltà completamente nuovo, o è segretamente solo una versione molto efficiente dell'informatica classica travestita? Nello specifico, i ricercatori si sono chiesti se ogni possibile operazione che un computer quantistico può eseguire possa essere scomposta in una sequenza di passaggi che un computer classico potrebbe eventualmente comprendere, con i giusti suggerimenti. Se la risposta fosse sì, allora il potere unico della crittografia quantistica potrebbe essere un'illusione. Se la risposta fosse no, allora i computer quantistici possiedono una forza fondamentale che le macchine classiche non potranno mai replicare.

Due ricercatori, William Kretschmer ed Ewin Tang, hanno recentemente compiuto un passo significativo verso la risoluzione di questa incertezza. Non hanno risolto interamente il mistero, ma hanno costruito un potente ponte logico che collega l'esistenza della crittografia quantistica sicura ad alcuni dei problemi più vecchi e ostinati dell'informatica classica. Il loro lavoro suggerisce che se la crittografia quantistica sicura esiste nel mondo reale, allora deve essere vera una di queste due cose: o esiste un limite fondamentale alla nostra capacità di tradurre le operazioni quantistiche in istruzioni classiche, oppure una specifica questione, decennale, sulla potenza dei computer classici deve avere una risposta sorprendente.

Per comprendere il loro traguardo, occorre innanzitutto afferrare la natura del compito che stanno analizzando. Immaginate un computer quantistico come un dispositivo in grado di ruotare un oggetto complesso e multidimensionale in un modo che sia perfettamente reversibile. Il "problema della sintesi unitaria" chiede se, per ogni tale rotazione, sia possibile trovare un insieme di istruzioni classiche che un computer standard potrebbe seguire per ricreare quella rotazione. Se potessimo sempre farlo, significherebbe che il mondo quantistico è, in un certo senso, solo una versione molto complicata del mondo classico. I ricercatori si sono concentrati su una classe specifica di queste rotazioni: quelle che un computer quantistico può eseguire utilizzando una quantità ragionevole di memoria. Si sono chiesti se queste rotazioni specifiche potessero essere sempre sintetizzate da un computer classico con l'aiuto di un oracolo, che è essenzialmente una scatola nera magica in grado di rispondere istantaneamente a domande specifiche.

Gli autori hanno iniziato affrontando un ostacolo pratico: come definire precisamente questi compiti quantistici. I tentativi precedenti di categorizzarli avevano portato a risultati confusionari, in parte perché permettevano di lasciare dietro di sé dei "residui" (garbage). Nell'informatica quantistica, quando una macchina esegue un calcolo, spesso lascia dietro di sé dati extra che non sono più necessari ma che non possono essere semplicemente eliminati senza disturbare il risultato. Alcune definizioni permettevano questi dati residui disordinati, mentre altre richiedevano un processo perfettamente pulito. Kretschmer e Tang hanno dimostrato che per i compiti che coinvolgono grandi quantità di memoria, questa distinzione non è importante. Hanno dimostrato che qualsiasi processo quantistico disordinato e pieno di residui può essere convertito in un processo pulito e privo di residui senza cambiare la difficoltà fondamentale del compito. Questo è stato un passo cruciale, poiché ha permesso loro di trattare queste complesse operazioni quantistiche con un livello di chiarezza matematica che era mancato finora.

Con queste definizioni stabilite, hanno affrontato la questione centrale. Hanno dimostrato che per qualsiasi operazione quantistica che può essere eseguita con spazio polinomiale (una quantità gestibile di memoria), esistono solo due possibilità. O l'operazione è così complessa che nessun computer classico, indipendentemente da quanto sia intelligente o da quanto aiuto riceva da un oracolo, potrà mai sintetizzarla efficientemente. Oppure, l'operazione non è affatto così difficile; può essere sintetizzata efficientemente se al computer classico è permesso porre domande su un tipo specifico di problema difficile noto come problema di ricerca NEXP. Questa seconda categoria rappresenta un traguardo molto alto nella teoria della complessità classica, rappresentando problemi che sono esponenzialmente più difficili di quelli che sappiamo risolvere attualmente.

Le implicazioni di questa scoperta sono profonde, particolarmente per il futuro della crittografia. La crittografia quantistica si basa sull'idea che certi compiti, come la creazione di uno schema di impegno sicuro (un modo per sigillare un segreto in una scatola digitale in modo che non possa essere cambiato o sbirciato), siano impossibili da violare per un avversario. Se esistono impegni quantistici sicuri, la logica dei ricercatori dicta che ci troviamo in una situazione molto specifica. O il problema della sintesi unitaria ha una risposta negativa, il che significa che esistono operazioni quantistiche che sono fondamentalmente oltre la portata della sintesi classica, oppure una grande questione della complessità classica deve essere risolta. Nello specifico, implicherebbe che una classe di problemi chiamata BPP (problemi risolvibili rapidamente con il caso) non è uguale a NEXP (problemi risolvibili con tempo esponenziale e non-determinismo). Questa è una questione che è rimasta aperta per oltre quarant'anni.

In termini più semplici, l'articolo sostiene che dimostrare l'esistenza della crittografia quantistica sicura non è solo una questione di costruzione di migliori dispositivi quantistici. È inestricabilmente legato ai limiti teorici più profondi dell'informatica classica. Se potessimo provare incondizionatamente che gli impegni quantistici sono sicuri, saremmo simultaneamente costretti a rispondere a uno dei due enormi enigmi della computer science, rimasti irrisolti da decenni. Dovremmo o accettare che le operazioni quantistiche possono essere fondamentalmente più difficili da simulare di quanto pensassimo, oppure dovremmo dimostrare che un tipo specifico e incredibilmente potente di computazione classica è strettamente più capace di una computazione randomizzata standard.

Il lavoro getta luce anche sulla relazione tra il potere quantistico e quello classico in un senso più generale. Gli autori hanno dimostrato che se assumiamo che il problema della sintesi unitaria abbia una risposta positiva (ovvero che tutto possa essere sintetizzato), allora il potere dei computer quantistici con grande memoria è strettamente vincolato dal potere dei computer classici che risolvono problemi di ricerca NEXP. Ciò suggerisce che la "magia" dell'informatica quantistica, se esiste, non è un fenomeno fluttuante, ma è profondamente radicata nella struttura della complessità classica. Se i computer quantistici possono fare qualcosa di veramente nuovo, è perché stanno accedendo a uno strato di difficoltà che i computer classici non possono raggiungere, nemmeno con i migliori possibili scorciatoie.

In definitiva, questa ricerca non ci dice se la crftografia quantistica sia sicura o se il problema della sintesi unitaria sia risolvibile. Al contrario, mappa il terreno tra queste due possibilità. Rivela che il percorso per dimostrare la sicurezza dei sistemi quantistici è bloccato dagli stessi muri che hanno impedito ai teorici della complessità classica di risolvere i loro problemi più difficili per mezzo secolo. L'articolo suggerisce che non possiamo semplicemente costruire la strada verso una prova; dobbiamo prima comprendere i limiti fondamentali del calcolo stesso. Chiarendo le definizioni e stabilendo queste rigorose connessioni, Kretschmer e Tang hanno fornito una visione più chiara del panorama, mostrando che il destino della crittografia quantistica e il destino della teoria della complessità classica sono legati insieme in un modo che non era precedentemente compreso.