Quantum n-coloring is undecidable for every n $\ge$ 3

Negli angoli silenziosi della matematica e dell'informatica, esiste una classe di problemi che pone una domanda semplice: è possibile seguire un insieme specifico di regole senza incorrere in contraddizioni? Uno dei più famosi di questi è il problema della colorazione dei grafi. Immaginate una mappa dove ogni regione deve essere dipinta con un colore, ma due regioni che condividono un confine non possono avere la stessa tonalità. Per molto tempo, i matematici hanno saputo che per le mappe con soli due colori, la risposta poteva essere trovata rapidamente da un computer. Tuttavia, una volta che il numero di colori disponibili aumenta, il problema diventa enormemente più complesso. Nel regno della fisica quantistica, dove le particelle possono esistere in più stati contemporaneamente e condividere connessioni profonde e invisibili, questo gioco di colorazione assume una nuova forma. Qui, i "colori" non sono solo vernice, ma strumenti matematici chiamati proiezioni che descrivono lo stato di un sistema quantistico. La domanda passa dal capire se una mappa possa essere colorata con regole standard al capire se esiste una strategia perfetta per una versione quantistica del gioco. Questa distinzione è importante perché tocca i limiti stessi di ciò che può essere computato. Se un problema è indecidibile, significa che nessun computer, indipendentemente da quanto sia potente o da quanto tempo gli venga concesso, potrà mai garantire una risposta.

Per anni, i ricercatori hanno saputo che questo gioco di colorazione quantistica era impossibile da risolvere per un caso specifico che coinvolgeva tre colori. Il mistero rimaneva per qualsiasi numero di colori superiore a tre. Un team di studenti universitari della Technical University of Denmark ha ora colmato questo divario. Hanno dimostrato che il problema della colorazione quantistica è indecidibile per ogni numero di colori a partire da tre in su. Il loro lavoro non si basa su simulazioni complesse o teorie non dimostrate; è una rigorosa prova matematica che estende un'impossibilità nota a un intero nuovo intervallo di possibilità. Costruendo un ponte specifico tra il caso dei tre colori e qualsiasi numero di colori superiore, hanno dimostrato che se un computer non può risolvere la versione a tre colori, non può risolvere alcuna versione con più colori.

I ricercatori sono partiti da un grafo, che è semplicemente una collezione di punti connessi da linee, che rappresentano le regioni e i confini della mappa di colorazione. Hanno poi creato un nuovo grafo, più grande, combinando l'originale con una piccola struttura fissa e un gruppo completo di punti. Questa costruzione è una ricetta precisa che può essere seguita rapidamente da un computer. Il cuore della loro scoperta risiede nel dimostrare che la capacità di colorare questo nuovo grafo più grande con un numero specifico di colori è esattamente la stessa capacità di colorare il grafo originale con soli tre colori. Se il grafo originale può essere risolto utilizzando una strategia quantistica per tre colori, il nuovo grafo può essere risolto per il numero maggiore. Viceversa, se il nuovo grafo può essere risolto, l'originale doveva essere risolvibile per i tre colori. Ciò crea un collegamento diretto, o riduzione, il che significa che la difficoltà del problema più grande è identica alla difficoltà di quello più piccolo.

Poiché era già stato stabilito che il problema quantistico dei tre colori è indecidibile, questo legame prova che anche i problemi più grandi sono indecidibili. Gli studenti hanno dimostrato che non esiste un algoritmo in grado di esaminare un grafo e un numero di colori superiore a tre per dire definitivamente se esista una strategia quantistica perfetta. La prova funziona mostrando che qualsiasi tentativo di risolvere il problema più grande richiederebbe essenzialmente la risoluzione del impossibile problema dei tre colori in primo luogo. Questo risultato è valido sia che il sistema quantistico sia finito o infinito, coprendo tutti i modelli standard di meccanica quantistica utilizzati in questo campo. Il ritrovamento risolve una questione che era rimasta aperta per un certo tempo, confermando che la barriera al calcolo non è solo una particolarità del caso dei tre colori, ma una caratteristica fondamentale dell'intera famiglia di problemi di colorazione quantistica.

Le implicazioni di questo lavoro vanno oltre il gioco specifico della colorazione. Suggeriscono un modello più ampio nella complessità dei sistemi quantistici. Gli autori osservano che, mentre alcuni tipi specifici di problemi di colorazione quantistica sono risolvibili, il caso generale per strutture non bipartitiche sembra essere impossibile da decidere. Propongono una congettura secondo la quale, per qualsiasi struttura che non sia una semplice divisione in due parti, il problema della colorazione quantistica sarà probabilmente indecidibile. Ciò si allinea con una nota divisione nella matematica classica, dove i problemi sono o facili o difficili, ma qui il lato "difficile" è stato dimostrato essere veramente irrisolvibile. Il lavoro si pone come una chiara dimostrazione del fatto che, nel mondo quantistico, i limiti del calcolo sono più stretti di quanto precedentemente pensato, e che per una vasta gamma di scenari, la risposta alla domanda se esista una strategia perfetta è una domanda che nessuna macchina potrà mai rispondere.