Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes

I computer quantistici promettono di risolvere problemi che le macchine odierne impiegherebbero millenni a decifrare, ma sono incredibilmente fragili. La minima perturbazione dall'ambiente può sconvolgere le delicate informazioni che contengono. Per costruire una macchina che funzioni, gli scienziati devono avvolgere questi dati fragili in uno strato protettivo chiamato correzione degli errori quantistici. Questo sistema controlla costantemente gli errori, in modo simile a un correttore ortografico per un documento, ma invece di correggere i refusi, identifica e inverte gli errori fisici nei bit quantistici, o qubit. I design più promettenti per queste macchine utilizzano un tipo specifico di protezione noto come codici topologici. In questi sistemi, l'informazione non è memorizzata in una singola particella, ma è distribuita su una vasta griglia bidimensionale di qubit, rendendola robusta contro il rumore locale.

Affinché questa protezione funzioni nel mondo reale, il computer deve essere in grado di leggere i risultati dei suoi controlli e capire esattamente cosa sia andato storto, un processo chiamato decodifica. L'obiettivo è trovare la spiegazione più semplice e probabile per gli errori osservati. Se il computer non riesce a decodificare questi errori in modo rapido e accurato, la protezione fallisce e il calcolo crolla. Per molto tempo, i ricercatori hanno sperato che trovare la spiegazione più semplice per i tipi di errori più comuni fosse un compito che un computer potesse gestire efficientemente. Tuttavia, un nuovo studio di Louay Bazzi e Georges Khater suggerisce che questa speranza potrebbe essere infondata per gli schemi di correzione degli errori più potenti. Essi hanno dimostrato che, per certi codici quantistici avanzati, trovare la soluzione perfetta è così computazionalmente difficile che anche i migliori possibili scorciatoie finiranno per fallire nel mantenere l'errore abbastanza piccolo man mano che il sistema cresce di dimensioni.

I ricercatori si sono concentrati su due famiglie principali di codici quantistici: i codici di superficie e i codici di colore. I codici di superficie sono i preferiti attuali per la costruzione di computer quantistici perché sono compatibili con i design dell'hardware esistente, mentre i codici di colore offrono vantaggi unici per l'esecuzione di calcoli. In entrambi i sistemi, il computer misura un insieme di segnali chiamati sindromi, che agiscono come una mappa di dove si sono verificati gli errori. Il compito della decodifica è disegnare un percorso attraverso la griglia che connetta questi punti di errore in un modo che richieda il minor "sforzo", o peso, possibile. Negli scenari più semplici, questo è come connettere dei punti su un foglio di carta con lo spago più corto. Per alcuni codici più vecchi e semplici, questo è un problema matematico diretto che può essere risolto rapidamente.

Bazzi e Khater hanno investigato cosa accade quando gli errori sono più complessi, specificamente quando diversi tipi di errori possono accadere contemporaneamente e influenzarsi a vicenda, una situazione nota come canale depolarizzante. Si sono chiesti: esiste un algoritmo veloce ed efficiente che possa sempre trovare una soluzione molto vicina a quella assolutamente migliore? Per rispondere, non hanno eseguito simulazioni su un computer; al contrario, hanno costruito una rigorosa prova matematica. Hanno dimosttato che, per i codici di superficie e i codici di colore, il problema di trovare la correzione ottimale non è solo difficile, ma fondamentalmente intrattabile in un modo specifico. Hanno provato che, indipendentemente da quanto sia intelligente un programma per computer, man mano che il computer quantistico cresce di dimensioni, l'errore assoluto nella sua migliore ipotesi aumenterà, il che significa che il divario tra la soluzione dell'algoritmo e la risposta perfetta si allarga in un modo che non può essere ignorato.

Il team ha dimostrato che per un computer quantistico con un certo numero di qubit, qualsiasi algoritmo veloce produrrà inevitabilmente una soluzione che è scostata di un margine significativo rispetto alla risposta perfetta. Nello specifico, hanno scoperto che per il codice torico e il codice di colore 4.8.8, l'errore nella soluzione cresce a un ritmo correlato alla quattordicesima radice del numero totale di qubit. Per il codice di superficie planare, l'errore cresce a un ritmo correlato alla diciottesima radice del numero di qubit. Sebbene questi numeri possano sembrare piccoli, rappresentano un divario crescente che non può essere colmato semplicemente rendendo il computer più intelligente o più veloce. I ricercatori hanno stabilito che, a meno che non avvenga una grande scoperta nell'informatica — specificamente, se un problema noto per essere estremamente difficile dovesse rivelarsi facile — nessun algoritmo in tempo polinomiale può garantire una soluzione entro questo divario.

Per raggiungere questa conclusione, gli autori hanno costruito un complesso quadro logico utilizzando piccole strutture modulari che hanno chiamato gadget. Immaginateli come piccole macchine autosufficienti progettate per imporre regole specifiche, simili a come una serratura assicura che una porta si apra solo con la chiave giusta. Hanno disposto questi gadget in una griglia per imitare il comportamento di un difficile puzzle logico noto per essere difficile da risolvere. Spaziando attentamente questi gadget, hanno garantito che la soluzione del puzzle non potesse prendere scorciatoie attraverso la griglia. Hanno dimostrato che l'unico modo per risolvere il puzzle in modo efficiente sarebbe risolvere il problema logico sottostante, che sanno essere impossibile da risolvere rapidamente per input di grandi dimensioni. Questo metodo ha permesso loro di tradurre la difficoltà di un problema noto come difficile direttamente nella difficoltà di decodificare gli errori quantistici.

Lo studio ha affrontato anche un'ondata recente di ottimismo nel campo. Poco prima di questo lavoro, altri ricercatori avevano scoperto che, per questi stessi codici, è possibile avvicinarsi molto alla risposta perfetta se si è disposti ad accettare una piccola percentuale fissa di errore. Ciò aveva portato alla convinzione che la decodifica efficiente fosse a portata di mano. Il lavoro di Bazzi e Khater chiarisce i limiti di questo ottimismo. Hanno dimostrato che, sebbene sia possibile avvicinarsi alla risposta migliore, non si può arrivare arbitrariamente vicini. Esiste un muro invalicabile dove l'errore diventa troppo grande per essere ignorato man mano che il sistema scala verso l'alto. Questa distinzione è cruciale perché nel calcolo quantistico, anche un piccolo errore persistente può accumularsi e distruggere il calcolo nel tempo.

Le implicazioni di questa scoperta sono significative per il futuro dell'hardware quantistico. Suggerisce che gli ingegneri non possono fare affidamento su un singolo algoritmo universale per correggere gli errori per tutte le dimensioni dei computer quantistici. Mentre costruiscono macchine più grandi, potrebbero dover accettare che il processo di decodifica diventerà meno preciso, oppure devono trovare modi completamente nuovi per strutturare i loro codici che evitino queste specifiche trappole matematiche. I ricercatori hanno anche sviluppato un nuovo toolkit di "gadget" e un metodo per controllare come interagiscono, il che potrebbe aiutare altri scienziati a esplorare i limiti della decodifica in diversi tipi di sistemi quantistici. Il loro lavoro non dice che i computer quantistici siano impossibili, ma traccia una linea netta nel terreno riguardo a quanto efficientemente possiamo gestire i loro errori.

In definitiva, il documento fornisce un realismo sobrio ma necessario. Conferma che il percorso verso un computer quantistico tollerante ai guasti non è solo una questione di costruzione di un hardware migliore o di software più veloce. Rivela una complessità fondamentale nella matematica della correzione degli errori che richiederà nuove strategie per essere superata. I ricercatori hanno dimostrato che, per i codici più promettenti attualmente sul tavolo, il sogno di un decoder perfetto e veloce è matematicamente fuori portata. La sfida ora si sposta sul trovare modi per lavorare entro questi limiti, forse progettando codici che siano intrinsecamente più facili da decodificare o accettando che un certo livello di approssimazione sia inevitabile nella corsa a costruire un computer quantistico funzionante.