Sintesi Tecnica: Gerarchia NPA per l'Indistinguibilità di Isomorfismo e Omoformismo Quantistico

1. Enunciato del Problema e Motivazione

Il saggio affronta la caratterizzazione computazionale e strutturale dell'isomorfismo quantistico tra grafi. Due grafi $G$ e $H$ sono quantisticamente isomorfi ($G \cong_q H$) se esiste una strategia quantistica perfetta per il gioco dell'isomorfismo dei grafi, che coinvolge entanglement condiviso e misurazioni locali.

Mentre l'isomorfismo dei grafi classico è decidibile (risolvibile in tempo quasi-polinomiale), Mančinska e Roberson [FOCS'20] hanno dimostrato che decidere l'isomorfismo quantistico è indecidibile in generale. Ciò motiva lo studio dei rilassamenti dell'isomorfismo quantistico, specificamente la gerarchia NPA (nominata da Navascués, Pironio e Acín), che fornisce una sequenza di rilassamenti di programmazione semidefinita (SDP) per approssimare le correlazioni quantistiche.

Una questione centrale nella teoria emergente dell'indistinguibilità di omoformismo è se la fattibilità di ogni livello di questi rilassamenti SDP possa essere caratterizzata combinatoriamente. Nello specifico, gli autori si chiedono: La fattibilità del $k$-esimo livello della gerarchia NPA per il gioco di $(G, H)$-isomorfismo è equivalente al fatto che $G$ e $H$ siano indistinguibili per omoformismo su una specifica classe di grafi?

2. Metodologia e Tecniche di Dimostrazione

Il saggio impiega una sintesi di combinatoria algebrica, teoria degli operatori e teoria dei grafi. La metodologia principale si basa sulla corrispondenza tra grafi bi-etichettati e tensori di omoformismo.

Strumenti Chiave

• Grafi Bi-etichettati e Tensori di Omoformismo: Un grafo $(k, l)$-bi-etichettato $F = (F, u, v)$ è associato a un tensore $F^G \in \mathbb{C}^{V(G)^k \times V(G)^l}$, dove le voci contano gli omoformismi che mappano le etichette di input $u$ in $x$ e le etichette di output $v$ in $y$. Le operazioni combinatorie sui grafi bi-etichettati (composizione in serie, composizione in parallelo, permutazione ciclica delle etichette) corrispondono ad operazioni algebriche su questi tensori (moltiplicazione di matrici, prodotto di Schur, permutazione).
• Riformulazione della Gerarchia NPA: Gli autori riformulano l'esistenza di un certificato per il $k$-esimo livello della gerarchia NPA come l'esistenza di una mappa di isomorfismo quantistico di livello-$k$. Si tratta di una mappa completamente positiva tra algebre di matrici che preserva specifiche proprietà strutturali relative ai tensori di omoformismo.
• $k$-Equivalenza Algebrica: Introducono il concetto di $k$-equivalenza algebrica, definita come un isomorfismo di algebre tra sottoalgebre generate da tensori di omoformismo di specifici grafi atomici, soddisfacendo condizioni di preservazione della traccia e unitalità.

Struttura della Dimostrazione

La dimostrazione del teorema principale procede attraverso una catena di equivalenze:

1. Fattibilità NPA $\iff$ Mappa di Isomorfismo Quantistico: Una sottomatrice principale di un certificato NPA viene interpretata come la matrice di Choi di una mappa completamente positiva. I vincoli della gerarchia NPA sono mostrati essere equivalenti agli assiomi di una mappa di isomorfismo quantistico di livello-$k$ (Teorema 3.6).
2. Mappa di Isomorfismo Quantistico $\iff$ $k$-Equivalenza Algebrica: La mappa di isomorfismo quantistico è mostrata essere restrittiva a un isomorfismo tra le algebre generate dai tensori di omoformismo di un insieme specifico di grafi atomici, $Q_k$ (Teorema 3.9).
3. $k$-Equivalenza Algebrica $\iff$ Indistinguibilità di Omoformismo: Utilizzando la corrispondenza tra operazioni sui grafi e algebra tensoriale, l'esistenza di tale isomorfismo di algebre è mostrata essere equivalente al fatto che $G$ e $H$ abbiano uguali conteggi di omoformismo da una classe costruita di grafi, $P_k$ (Teorema 4.4).

3. Contributi Principali e Risultati

Teorema Principale (Teorema 1.1)

Per grafi $G$ e $H$ e un intero $k \ge 1$, i seguenti sono equivalenti:

1. Il $k$-esimo livello della gerarchia NPA per il gioco di $(G, H)$-isomorfismo è fattibile.
2. Esiste una mappa di isomorfismo quantistico di livello-$k$ da $G$ a $H$.
3. $G$ e $H$ sono algebricamente $k$-equivalenti.
4. $G$ e $H$ sono indistinguibili per omoformismo sulla classe di grafi $P_k$.

Qui, $P_k$ è una classe di grafi planari bi-etichettati costruiti induttivamente da grafi atomici $Q_k$ usando composizione in serie, composizione in parallelo con specifici grafi atomici e permutazioni cicliche delle etichette.

Proprietà della Classe di Grafi $P_k$

• Planarità: Ogni grafo in $P_k$ è planare (Lemma 셈.7).
• Treewidth Limitato: I grafi sottostanti di $P_k$ hanno treewidth al massimo $3k-1$ (Lemma 4.5).
• Chiusura rispetto ai Minori: La classe $P_k$ è chiusa rispetto alla presa di minori (Lemma 4.8).
• Unione: L'unione dei grafi non etichettati di tutte le $P_k$ (per $k \in \mathbb{N}$) è esattamente l'insieme di tutti i grafi planari (Corollario 4.12).

Risultato Algoritmico (Teorema 1.2)

Il saggio presenta un algoritmo in tempo polinomiale randomizzato per decidere l'esatta fattibilità del $k$-esimo livello della gerarchia NPA per un $k$ fissato.

• Tempo di esecuzione: $n^{O(k)} k^{O(1)}$, dove $n = \max\{|V(G)|, |V(H)|\}$.
• Metodo: Invece di risolvere l'SDP, l'algoritmo controlla l'indistinguibilità di omoformismo su $P_k$ modulo un numero primo $p$ scelto casualmente. Calcola una base per lo spazio vettoriale spaziato dai tensori di omoformismo di grafi in $P_k$ su un campo finito.
• Significato: Questo evita i problemi di approssimazione inerenti ai risolutori SDP standard (come il metodo dell'ellissoide) e fornisce una procedura decisionale esatta per livelli fissi.

Dimostrazione Alternativa di Mančinska e Roberson [FOCS'20]

Combinando il teorema principale con la convergenza della gerarchia NPA e il fatto che $\bigcup_k P_k$ è l'insieme di tutti i grafi planari, gli autori derivano una nuova dimostrazione che $G \cong_q H$ se e solo se $G$ e $H$ sono indistinguibili per omoformismo su tutti i grafi planari.

• Distinzione: A differenza della dimostrazione originale in [FOCS'20], che si basava pesantemente sulla teoria dei gruppi quantistici compatti e degli intertwiner, questa dimostrazione è puramente combinatoria e algebrica, utilizzando la gerarchia NPA e i tensori di omoformismo.

4. Significato e Rivendicazioni

Il saggio sostiene di fornire una caratterizzazione dell'indistinguibilità di omoformismo per la gerarchia NPA, collocando i rilassamenti dell'isomorfismo quantistico all'interno del più ampio quadro teorico delle relazioni di indistinguibilità di omoformismo.

• Unificazione Teorica: Colma il divario tra la gerarchia NPA non commutativa e la gerarchia di Lasserre classica (che è stata precedentemente caratterizzata da Roberson e Seppelt [ICALP'23] usando le classi di grafi $L_k$).
• Vantaggio Computazionale: Stabilisce che la fattibilità esatta per livelli fissi della gerarchia NPA è decidibile in tempo polinomiale randomizzato, un risultato che non è immediatamente ovvio dalla sola formulazione SDP.
• Semplificazione della Teoria dell'Isomorfismo Quantistico: Il saggio offre una dimostrazione della caratterizzazione fondamentale dell'isomorfismo quantistico (tramite grafi planari) che evita la "pesante strumentazione" dei gruppi quantistici, basandosi invece sulla struttura combinatoria dei vincoli NPA.

Gli autori osservano che, sebbene $P_k$ sia una sottoclasse di grafi planari con treewidth limitato, la precisa relazione strutturale tra la classe $P_k$ e le classi di grafi $L_k$ (usate per i rilassamenti dell'isomorfismo classico) rimane un problema aperto (Problema 6.1). Pongono inoltre la questione se esista una classe di grafi in cui l'isomorfismo quantistico sia determinato da un livello fisso della gerarchia NPA ma differisca dall'isomorfismo classico (Problema 6.2).