Nel mondo dell'informazione, proteggere i dati dalla corruzione è una questione di sopravvivenza. Che si tratti di inviare un messaggio attraverso un canale radio rumoroso o di memorizzare un file su un disco rigido, gli ingegneri utilizzano codici di correzione degli errori. Si tratta di strutture matematiche che aggiungono ridondanza ai dati, permettendo a un ricevitore di rilevare e correggere gli errori senza chiedere una ritrasmissione. Per decenni, gli scienziati hanno saputo che trovare la versione più robusta di questi codici è un enigma incredibilmente difficile. Nel mondo classico, dove i dati sono fatti di semplici bit che sono o zero o uno, è stato dimostrato che calcolare l'esatta forza di un codice è un compito così complesso che nessun algoritmo di computer efficiente può risolverlo per ogni caso.

Il regno quantistico, tuttavia, opera secondo regole diverse. Invece dei bit, i computer quantistici utilizzano i qubit, che possono esistere in delicate sovrapposizioni di stati. Per proteggere questa fragile informazione, i fisici utilizzano codici di correzione degli errori quantistici, che sono molto più intricati dei loro cugini classici. Una misura chiave della forza di un codice quantistico è la sua "distanza", un numero che ci dice quanti errori il codice può sopportare prima che l'informazione vada perduta. Se la distanza è piccola, il codice è fragile; se è grande, il codice è robusto. Per molto tempo, i ricercatori hanno creduto che, sebbene trovare questa distanza fosse difficile, forse non lo fosse quanto la versione classica. Alcuni studi recenti suggerivano che la difficoltà potesse stabilizzarsi a un certo punto, creando una barriera in cui il problema diventava più facile da approssimare rispetto a quanto precedentemente pensato. Questa idea lasciava intendere che i codici quantistici potessero possedere una semplicità nascosta che i codici classici non hanno.

Un nuovo studio di Upendra Kapshikar presso l'Università di Ottawa sfida direttamente questa nozione. Il ricercatore ha dimostrato che la difficoltà di approssimare la distanza di un codice quantistico è altrettanto severa della versione classica, arrivando fino ai limiti estremi di ciò che i computer possono fare, a condizione che certe ipotesi fondamentali di complessità siano vere. Costruendo un ponte specifico tra problemi classici e quantistici, Kapshikar dimostra che non esiste una scorciatoia per trovare la forza di questi codici quantistici. Il lavoro dimostra che cercare di indovinare la distanza entro un margine di errore ragionevole è un compito che rimane computazionalmente impossibile per qualsiasi algoritmo efficiente, a meno che le ampiamente accettate ipotesi sulla natura del calcolo non crollino. Ciò chiude efficacementmente la porta all'idea che i codici quantistici possiedano una proprietà speciale e più facile da risolvere.

Per comprendere la portata di questo risultato, bisogna innanzitutto afferrare la natura del problema. In un computer quantistico, gli errori possono infiltrarsi dall'ambiente, invertendo lo stato di un qubit o spostandone la fase. Un codice quantistico è progettato per intercettare questi errori. La "distanza" del codice è il numero minimo di qubit che devono essere influenzati da un errore prima che il codice non sia più in grado di rilevarlo. Se un codice ha una distanza di dieci, può rilevare qualsiasi errore che influenzi nove o meno qubit. La sfida per gli informatici è che, data la descrizione di un codice, calcolare questo numero esatto è un incubo. Nel mondo classico, è stato dimostrato anni fa che non è nemmeno possibile avvicinarsi rapidamente alla risposta corretta; il problema è "NP-hard", il che significa che man mano che il codice diventa più grande, il tempo richiesto per risolverlo cresce in modo esplosivo.

Per i codici quantistici, la situazione sembrava più torbida. Ricerche precedenti avevano dimostrato che il problema era difficile, ma solo fino a un certo punto. Quelle prove precedenti potevano mostrare che trovare la distanza era difficile se si voleva una risposta entro un divario che cresceva con la radice quadrata della dimensione del codice. Tuttavia, non potevano provare che fosse difficile trovare una risposta entro un divario che crescesse linearmente con la dimensione. Immaginate un codice con mille qubit. Un divario di radice quadrata potrebbe permettere una risposta errata di trenta, mentre un divario lineare permetterebbe una risposta errata di cento. I risultati precedenti lasciavano aperta la possibilità che i codici quantistici potessero essere facili da approssimare se si fosse disposti ad accettare un margine di errore maggiore. Il lavoro di Kapshikar rimuove questa incertezza.

Il ricercatore ha ottenuto questo costruendo un nuovo tipo di codice quantistico chiamato codice "codeword-stabilized". Questa costruzione funge da traduttore, prendendo un problema classico difficile e trasformandolo in uno quantistico. Il processo coinvolge due ingredienti principali: un codice classico e un grafo, che è una rete di punti connessi da linee. Il grafo determina come i qubit interagiscono, mentre il codice classico fornisce la struttura sottostante. L'innovazione chiave risiede nel modo in cui il grafo è stato scelto. I metodi precedenti si affidavano a grafi con connessioni molto specifiche e sparse, il che limitava la forza della prova. Kapshikar si è reso conto che utilizzando un grafo casuale — una rete in cui le connessioni sono scelte per caso — si poteva ottenere un risultato molto più forte.

In un grafo casuale, le connessioni sono dense e imprevedibili. Lo studio mostra che per quasi ogni grafo casuale scelto, il codice quantistico risultante avrà una distanza strettamente legata alla distanza del codice classico originale. Se il codice classico è forte, il codice quantistico è forte. Se il codice classico è debole, il codice quantistico è debole. Questo legame è così stretto che, se si potesse approssimare facilmente la distanza del codice quantistico, si potrebbe anche approssimare facilmente la distanza del codice classico. Poiché sappiamo che il problema classico è impossibile da risolvere efficientemente, anche il problema quantistico deve esserlo, assumendo che le ipotesi standard sulla complessità, come la Ipotesi del Tempo Esponenziale (SETH) e l'Ipotesi del Gap-Esponenziale (Gap-ETH), siano valide. La prova stabilisce che nessun computer può approssimare la distanza quantistica entro un divario lineare a meno che le fondamentali assunzioni sulla natura del calcolo non crollino.

Lo studio va oltre, esaminando il problema attraverso la lente della complessità "fine-grained". Questo approccio non chiede solo se un problema sia difficile, ma esattamente quanto lo sia. Considera il tempo necessario per risolvere il problema man mano che la dimensione dell'input cresce. La ricerca mostra che anche se si permette a un algoritmo di eseguire per un tempo molto lungo — più lungo di qualsiasi tempo polinomiale ma più breve di una ricerca esponenziale completa — non riuscirà comunque a risolvere il problema, a condizione che le ipotesi SETH e Gap-ETH siano vere. Nello specifico, l'articolo dimostra che nessun algoritmo può risolvere il problema in un tempo significativamente inferiore al tempo che sarebbe necessario per controllare ogni possibile schema di errore. Ciò è vero per i potenti computer teorici, a condizione che operino entro le normali regole di logica e probabilità e che le suddette ipotesi rimangano valide.

Uno degli aspetti più sorprendenti della scoperta è la sua robustezza. Il risultato regge anche quando il codice quantistico è limitato a un tipo specifico e popolare noto come codice CSS. Questi codici sono ampiamente utilizzati nelle progettazioni pratiche di calcolo quantistico perché sono più facili da implementare. Il ricercatore ha dimostrato che la difficoltà si applica anche a essi, il che significa che la difficoltà non è un artefatto di un design di codice strano o esotico, ma è una proprietà fondamentale della correzione degli errori quantistici stessa. La prova affronta anche la questione della "degenerazione", una caratteristica unica dei codici quantistici in cui alcuni errori sono innocui perché agiscono in modo banale sull'informazione. Lo studio tiene conto di questo con cura, mostrando che anche con questa particolarità quantistica, il problema rimane intrattabile.

Le implicazioni di questo lavoro sono profonde per il futuro del calcolo quantistico. Confermano che la barriera nel progettare e analizzare i codici quantistici non è un ostacolo temporaneo che sarà superato da algoritmi migliori. Al contrario, la difficoltà è intrinseca alla matematica del problema, assumendo le congetture standard sulla complessità. Ciò significa che gli ingegneri che progettano computer quantistici non possono fare affidamento su un calcolo rapido per verificare la forza dei loro codici. Devono o accettare che trovare la distanza esatta è computazionalmente proibitivo per sistemi grandi, o fare affidamento su costruzioni specifiche in cui la distanza è nota per progettazione. Lo studio traccia efficacemente una linea nella sabbia, mostrando che la ricerca di comprendere i limiti della correzione degli errori quantistici deve procedere con la consapevolezza che la matematica sottostante è tanto ostinata quanto possibile.

L'articolo tocca anche la natura della casualità nel calcolo. La prova si basa sull'idea che una scelta casuale di un grafo sia sufficiente per creare un'istanza difficile. Sebbene la prova iniziale utilizzi un processo casuale, il ricercatore mostra anche come rimuovere questa casualità sotto un'ipotesi ampiamente accettata riguardo alla potenza dei circuiti informatici. Ciò significa che la difficoltà non è solo un colpo di fortuna statistico del caso, ma una realtà deterministica. Esistono codici quantistici specifici e fissi che sono garantiti essere difficili da analizzare, e questi codi possono essere generati da un computer senza bisogno di lanciare dadi. Questo rafforza la conclusione, spostandola da una dichiarazione probabilistica a una garanzia ferma sui limiti del calcolo.

In definitiva, questa ricerca chiude un vuoto che era rimasto aperto per un certo periodo. Prende la difficoltà nota dei codici classici ed estende completamente nel regno quantistico, rimuovendo la barriera della radice quadrata che gli studi precedenti avevano incontrato. Il risultato è un quadro chiaro del panorama computazionale: il problema di trovare la distanza di un codice quantistico è difficile quanto i problemi più difficili dell'informatica, a condizione che le ipotesi standard di complessità siano valide. Per l'osservatore curioso, questo significa che il mondo quantistico, pur essendo pieno di fenomeni strani e meravigliosi, non offre una via di fuga dai limiti fondamentali della logica. La complessità di proteggere l'informazione quantistica è reale, profonda e, per ora, inamovibile.