Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut

Riepilogo Tecnico: Limiti Precisi sugli Autovalori dei Grafi di Kikuchi e Applicazioni al Quantum Max Cut

1. Enunciato del Problema

Il lavoro affronta le proprietà spettrali dei grafi di Kikuchi (noti anche come grafi dei token), costruiti a partire da un grafo base $G = ([n], E)$ con $m$ spigoli. Il grafo di Kikuchi di livello-$k$, indicato con $F_k(G)$, ha un insieme di vertici costituito da tutti i $k$-sottoinsiemi di $[n]$. Due vertici $S$ e $T$ sono adiacenti se la loro differenza simmetrica $S \oplus T$ è uno spigolo in $G$.

Il problema centrale consiste nell'istituire limiti superiori precisi sugli autovalori massimi delle seguenti matrici associate a $F_k(G)$:

1. Il Laplaciano con segno $L^{(k)}_G = D^{(k)}_G - A^{(k)}_G$.
2. Il Laplaciano senza segno (o privo di segno) $Q^{(k)}_G = D^{(k)}_G + A^{(k)}_G$.
3. La matrice di adiacenza $A^{(k)}_G$.

Prima di questo lavoro, il miglior limite generale noto per il Laplaciano senza segno era $\lambda_{\max}(L^{(k)}_G) \leq m + 4k - 2$ (Lew, 2026). Apte, Parekh e Sud (APS) hanno recentemente congetturato che per qualsiasi grafo $G$ e $0 \leq k \leq n$, gli autovalori massimi soddisfino $\lambda_{\max}(L^{(k)}_G) \leq m + k$ e $\lambda_{\max}(Q^{(k)}_G) \leq m + k$. Queste congetture sono critiche perché i limiti spettrali dei grafi di Kikuchi si traducono direttamente in limiti superiori sulle energie massime di specifici Hamiltoniani quantistici 2-locali.

2. Metodologia

Gli autori impiegano una nuova tecnica di induzione tramite gradiente sugli spigoli per dimostrare i limiti spettrali. La metodologia procede come segue:

• Definizione Unificata dell'Operatore: Gli autori definiscono un operatore unificato $L^{(k)}_{b,G} = D^{(k)}_G + bA^{(k)}_G$ per $b \in \{-1, 1\}$, che copre sia il Laplaciano con segno ($b=-1$) sia il Laplaciano senza segno ($b=1$).
• Struttura Induttiva: La dimostrazione procede per induzione su $k$. Per un autovettore fisso $x$ di $L^{(k)}_{b,G}$ con autovalore $\lambda$, gli autori definiscono vettori "gradiente sugli spigoli" $g_e$ per ogni spigolo $e = (i, j)$ nel grafo base $G$. Questi gradienti sono costruiti differenziando l'autovettore attraverso lo spigolo $e$ nel grafo dei token.
  • Per $b=-1$, $g_e$ rappresenta la differenza standard $x_{R \cup \{i\}} - x_{R \cup \{j\}}$.
  • Per $b=1$, rappresenta la somma $x_{R \cup \{i\}} + x_{R \cup \{j\}}$.
• Decomposizione degli Operatori: L'azione dell'operatore $L^{(k)}_{b,G}$ sui vettori gradiente è decomposta in tre componenti basate sulla relazione tra uno spigolo fisso $e$ e altri spigoli $f$ in $G$:
  1. Spigolo stesso ($f=e$): Contribuisce con un fattore di 2.
  2. Spigoli disgiunti ($f \cap e = \emptyset$): Questi inducono un operatore a $(k-1)$-token sul grafo $G - \{i, j\}$ (il grafo base con i vertici $i$ e $j$ rimossi).
  3. Spigoli adiacenti ($|f \cap e| = 1$): Questi producono termini "di torsione" che coinvolgono permutazioni di coordinate con segno. Gli autori dimostrano che questi termini preservano le norme euclidee tramite biiezioni tra spazi delle configurazioni.
• Somma delle Norme: Sommando le norme al quadrato dei vettori gradiente su tutti gli spigoli e applicando l'ipotesi induttiva al sottografo $G - \{i, j\}$, gli autori derivano una disuguaglianza che lega $\lambda$ al numero di spigoli $m$ e al numero di token $k$.

Per la Congettura di Brouwer (concernente le somme parziali degli autovalori del Laplaciano), gli autori adattano questa tecnica del gradiente sugli spigoli alla potenza esterna dello spazio vettoriale. Definendo un operatore ausiliario $B_r(G)$ relativo alla $r$-esima matrice composta additiva del Laplaciano, analizzando il "gradiente sugli spigoli" nell'algebra esterna (coinvolgendo contrazioni e proiezioni), essi limitano la forma quadratica di $B_r(G)$ e, di conseguenza, le somme parziali degli autovalori.

3. Contributi e Risultati Chiave

A. Risoluzione delle Congetture APS
Il lavoro dimostra il Teorema 1.2, confermando le quattro congetture di Apte, Parekh e Sud:

• $\lambda_{\max}(L^{(k)}_G) \leq m + k$
• $\lambda_{\max}(Q^{(k)}_G) \leq m + k$
• $\lambda_{\max}(A^{(k)}_G) \leq \frac{1}{2}(m + k)$
• $\lambda_{\min}(A^{(k)}_G) \geq -\frac{1}{2}(m + k)$

Gli autori notano che questi limiti sono stretti, come dimostrato da unioni disgiunte di stelle (per i Laplaciani) e unioni disgiunte di spigoli (coppiamenti perfetti, per le matrici di adiacenza).

B. Applicazioni agli Hamiltoniani Quantistici
Utilizzando i limiti spettrali, il lavoro deriva garanzie di approssimazione migliorate per l'energia massima degli Hamiltoniani 2-locali. Nello specifico, mostra che i prodotti tensoriali di stati prodotto a uno e due qubit raggiungono i seguenti rapporti strutturali:

• Quantum Max Cut (QMC): Rapporto di approssimazione di $5/8 = 0.625$.
• Hamiltoniano XY: Rapporto di approssimazione di $5/7 \approx 0.714$.
• Hamiltoniano EPR: Rapporto di approssimazione di $(\sqrt{5} + 1)/4 \approx 0.809$.

Inoltre, combinando questi limiti con gli algoritmi analizzati da Apte, Parekh e Sud, gli autori dimostrano l'esistenza di algoritmi efficienti che raggiungono:

• QMC: $0.614$
• XY: $0.674$
• EPR: $(\sqrt{5} + 1)/4$ (corrispondente al limite strutturale).

Questi risultati migliorano i precedenti rapporti peggiori noti per QMC (precedentemente $0.611$) e XY. Per l'EPR, sebbene il rapporto non superi lo $0.8395$ raggiunto da circuiti AGM più complessi, il lavoro fornisce un certificato più semplice utilizzando un ansatz molto più piccolo (stati prodotto a blocchi) rispetto alle rotazioni commutanti a due qubit utilizzate nei lavori precedenti.

C. Progressi sulla Congettura di Brouwer
Il lavoro migliora il limite sulle somme parziali degli autovalori del Laplaciano, $\epsilon_r(G) = \sum_{i=1}^r \lambda_i(L(G)) - |E|$.

• Limite Precedente (Lew, 2026): $\epsilon_r(G) \leq \binom{r+1}{2} + 4r^{3/2} - r - 2\sqrt{r}$.
• Nuovo Limite (Teorema 1.4): $\epsilon_r(G) \leq \binom{r+1}{2} + \frac{4}{3}r^{3/2} - r + \sqrt{r}$.
  Ciò rappresenta un miglioramento asintotico di un fattore $1/3$ sul termine di errore principale.

4. Significato

Il lavoro rivendica rilevanza in tre aree principali:

1. Teoria Spettrale dei Grafi: Risolve quattro congetture aperte riguardanti gli autovalori estremi dei grafi di Kikuchi, fornendo limiti stretti precedentemente sconosciuti.
2. Algoritmi di Approssimazione Quantistica: Stabilisce che semplici stati prodotto (prodotti tensoriali di stati a 1 e 2 qubit) sono sufficienti per raggiungere rapporti di approssimazione di $0.614$ per QMC e $0.674$ per XY, migliorando lo stato dell'arte. Sottolinea che ansatz entangled complessi (come i circuiti AGM) potrebbero non essere strettamente necessari per raggiungere questi specifici limiti, offrendo un certificato strutturale più semplice.
3. Ottimizzazione Combinatoria: Fornisce le migliori stime note per la congettura di Brouwer sulla somma dei primi $k$ autovalori del Laplaciano, affinando la comprensione della distribuzione spettrale dei Laplaciani dei grafi.

Gli autori sottolineano che i loro risultati derivano da limiti spettrali precisi sui grafi di Kikuchi, che fungono da ponte tra strutture di incidenza ad alta dimensionalità e la teoria spettrale standard dei grafi, con implicazioni dirette per la complessità computazionale dei sistemi quantistici a molti corpi.