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

Resumo Técnico: Limites Afiados nos Autovalores de Grafos de Kikuchi e Aplicações ao Corte Máximo Quântico

1. Formulação do Problema

O artigo aborda as propriedades espectrais dos grafos de Kikuchi (também conhecidos como grafos de tokens), que são construídos a partir de um grafo base $G = ([n], E)$ com $m$ arestas. O grafo de Kikuchi de nível-$k$, denotado $F_k(G)$, possui um conjunto de vértices consistindo em todos os $k$-subconjuntos de $[n]$. Dois vértices $S$ e $T$ são adjacentes se sua diferença simétrica $S \oplus T$ for uma aresta em $G$.

O problema central é estabelecer limites superiores afiados para os autovalores máximos das seguintes matrizes associadas a $F_k(G)$:

1. O Laplaciano assinado $L^{(k)}_G = D^{(k)}_G - A^{(k)}_G$.
2. O Laplaciano não assinado (sem sinal) $Q^{(k)}_G = D^{(k)}_G + A^{(k)}_G$.
3. A matriz de adjacência $A^{(k)}_G$.

Anteriormente a este trabalho, o melhor limite geral conhecido para o Laplaciano não assinado era $\lambda_{\max}(L^{(k)}_G) \leq m + 4k - 2$ (Lew, 2026). Apte, Parekh e Sud (APS) conjecturaram recentemente que, para qualquer grafo $G$ e $0 \leq k \leq n$, os autovalores máximos satisfazem $\lambda_{\max}(L^{(k)}_G) \leq m + k$ e $\lambda_{\max}(Q^{(k)}_G) \leq m + k$. Essas conjecturas são críticas porque os limites espectrais dos grafos de Kikuchi se traduzem diretamente em limites superiores para as energias máximas de Hamiltonianos quânticos específicos 2-locais.

2. Metodologia

Os autores empregam uma técnica inovadora de indução por gradiente de aresta para provar os limites espectrais. A metodologia procede da seguinte forma:

• Definição Unificada de Operador: Os autores definem um operador unificado $L^{(k)}_{b,G} = D^{(k)}_G + bA^{(k)}_G$ para $b \in \{-1, 1\}$, cobrindo tanto o Laplaciano assinado ($b=-1$) quanto o Laplaciano não assinado ($b=1$).
• Estrutura Indutiva: A prova procede por indução em $k$. Para um autovetor fixo $x$ de $L^{(k)}_{b,G}$ com autovalor $\lambda$, os autores definem vetores de "gradiente de aresta" $g_e$ para cada aresta $e = (i, j)$ no grafo base $G$. Esses gradientes são construídos diferenciando o autovetor através da aresta $e$ no grafo de tokens.
  • Para $b=-1$, $g_e$ representa a diferença padrão $x_{R \cup \{i\}} - x_{R \cup \{j\}}$.
  • Para $b=1$, representa a soma $x_{R \cup \{i\}} + x_{R \cup \{j\}}$.
• Decomposição de Operadores: A ação do operador $L^{(k)}_{b,G}$ sobre os vetores de gradiente é decomposta em três componentes com base na relação entre uma aresta fixa $e$ e outras arestas $f$ em $G$:
  1. Aresta própria ($f=e$): Contribui com um fator de 2.
  2. Arestas disjuntas ($f \cap e = \emptyset$): Estas induzem um operador de $(k-1)$-tokens no grafo $G - \{i, j\}$ (o grafo base com os vértices $i$ e $j$ removidos).
  3. Arestas adjacentes ($|f \cap e| = 1$): Estas produzem termos de "torção" envolvendo permutações de coordenadas assinadas. Os autores mostram que esses termos preservam as normas euclidianas via bijeções entre espaços de configuração.
• Soma de Normas: Somando as normas quadradas dos vetores de gradiente sobre todas as arestas e aplicando a hipótese de indução ao subgrafo $G - \{i, j\}$, os autores derivam uma desigualdade relacionando $\lambda$ ao número de arestas $m$ e à contagem de tokens $k$.

Para a Conjectura de Brouwer (concernente a somas parciais de autovalores do Laplaciano), os autores adaptam essa técnica de gradiente de aresta para o produto exterior do espaço vetorial. Eles definem um operador auxiliar $B_r(G)$ relacionado ao $r$-ésimo composto aditivo do Laplaciano. Ao analisar o "gradiente de aresta" na álgebra exterior (envolvendo contrações e projeções), eles limitam a forma quadrática de $B_r(G)$ e, subsequentemente, as somas parciais dos autovalores.

3. Contribuições e Resultados Chave

A. Resolução das Conjecturas de APS
O artigo prova o Teorema 1.2, confirmando as quatro conjecturas de 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)$

Os autores observam que esses limites são apertados, demonstrados por uniões disjuntas de estrelas (para Laplacianos) e uniões disjuntas de arestas (emparelhamentos perfeitos, para matrizes de adjacência).

B. Aplicações a Hamiltonianos Quânticos
Usando os limites espectrais, o artigo deriva garantias de aproximação melhoradas para a energia máxima de Hamiltonianos 2-locais. Especificamente, mostra que produtos tensoriais de estados de produto de um e dois qubits alcançam as seguintes razões estruturais:

• Corte Máximo Quântico (QMC): Razão de aproximação de $5/8 = 0,625$.
• Hamiltoniano XY: Razão de aproximação de $5/7 \approx 0,714$.
• Hamiltoniano EPR: Razão de aproximação de $(\sqrt{5} + 1)/4 \approx 0,809$.

Além disso, combinando esses limites com os algoritmos analisados por Apte, Parekh e Sud, os autores demonstram a existência de algoritmos eficientes alcançando:

• QMC: $0,614$
• XY: $0,674$
• EPR: $(\sqrt{5} + 1)/4$ (correspondendo ao limite estrutural).

Esses resultados melhoram as razões de pior caso anteriormente conhecidas para QMC (anteriormente $0,611$) e XY. Para EPR, embora a razão não supere o $0,8395$ alcançado por circuitos AGM mais complexos, o artigo fornece um certificado mais simples usando um ansatz muito menor (estados de produto em bloco) em comparação com as rotações comutativas de dois qubits usadas em trabalhos anteriores.

C. Progresso na Conjectura de Brouwer
O artigo melhora o limite sobre as somas parciais dos autovalores do Laplaciano, $\epsilon_r(G) = \sum_{i=1}^r \lambda_i(L(G)) - |E|$.

• Limite Anterior (Lew, 2026): $\epsilon_r(G) \leq \binom{r+1}{2} + 4r^{3/2} - r - 2\sqrt{r}$.
• Novo Limite (Teorema 1.4): $\epsilon_r(G) \leq \binom{r+1}{2} + \frac{4}{3}r^{3/2} - r + \sqrt{r}$.
  Isso representa uma melhoria assintótica por um fator de $1/3$ no termo de erro líder.

4. Significância

O artigo reivindica significância em três áreas primárias:

1. Teoria Espectral de Grafos: Resolve quatro conjecturas abertas sobre os autovalores extremos dos grafos de Kikuchi, fornecendo limites apertados que eram anteriormente desconhecidos.
2. Algoritmos de Aproximação Quântica: Estabelece que estados de produto simples (produtos tensoriais de estados de 1 e 2 qubits) são suficientes para alcançar razões de aproximação de $0,614$ para QMC e $0,674$ para XY, melhorando o estado da arte. Destaca que ansatzes emaranhados complexos (como circuitos AGM) podem não ser estritamente necessários para alcançar esses limites específicos, oferecendo um certificado estrutural mais simples.
3. Otimização Combinatória: Fornece as melhores estimativas conhecidas para a conjectura de Brouwer sobre a soma dos $k$-maiores autovalores do Laplaciano, refinando a compreensão da distribuição espectral dos Laplacianos de grafos.

Os autores enfatizam que seus resultados são derivados de limites espectrais afiados em grafos de Kikuchi, que servem como uma ponte entre estruturas de incidência de alta dimensão e a teoria espectral de grafos padrão, com implicações diretas para a complexidade computacional de sistemas quânticos de muitos corpos.