Better bounds on finite-order Grothendieck constants

Resumo Técnico: Melhores limites para constantes de Grothendieck de ordem finita

Enunciado do Problema
O artigo aborda o cálculo das constantes de Grothendieck de ordem finita, denotadas por $KG(d)$. Estas constantes quantificam a vantagem de estratégias de $d$ dimensões sobre estratégias de 1 dimensão em uma tarefa de otimização específica envolvendo normas tensoriais. Enquanto a constante de ordem infinita $KG$ e o caso $d=2$ são bem estudados, os valores para $d \geq 3$ permanecem amplamente desconhecidos. O desafio principal reside em encontrar matrizes $M$ que maximizem a razão entre o valor de programação semidefinida (SDP) de $d$ dimensões, $SDP_d(M)$, e o valor de 1 dimensão, $SDP_1(M)$ (que é equivalente ao problema MaxCut, que é NP-difícil). Os limites existentes para $d \in \{3, \dots, 9\}$ são frouxos, e a busca por ansätze de alta dimensão adequados é dificultada pela maldição da dimensionalidade.

Metodologia
Os autores combinam uma técnica de projeção recente baseada em algoritmos de Frank-Wolfe (FW) com solvers poderosos para otimização quadrática binária. A metodologia é dividida em duas abordagens principais:

1. Instâncias Simétricas (Heurística e Analítica):

   • Os autores utilizam empacotamentos de linhas altamente simétricos (por exemplo, sistemas de raízes como $E_7, E_8$ e politopos como o 600-cell e o 120-cell) para construir matrizes de Gram $P$.
   • Eles empregam um algoritmo de Gradiente Condicional de Par Par Blended (BPCG) para projetar $P$ no politopo de correlação simetrizado $SDP_1$. Este processo busca separar $P$ de $SDP_1$ via um hiperplano (um fato $A$).
   • Para estruturas simétricas, a dimensão do espaço ambiente é reduzida, permitindo a derivação de fatos "putativos". No entanto, computar o $SDP_1(A)$ exato para estas instâncias simétricas grandes é frequentemente intratável para solvers exatos. Consequentemente, os autores utilizam métodos heurísticos (minimização alternada/otimização seesaw) para estimar o $SDP_1(A)$, gerando limites inferiores que não são rigorosamente certificados, mas que são altamente sugestivos.

2. Instâncias Assimétricas (Certificação Exata):

   • Para obter limites rigorosamente certificados, os autores constroem matrizes retangulares $M$ onde o número de linhas ($m_1$) é pequeno e o de colunas ($m_2$) é grande. Isso reduz a complexidade do cálculo de $SDP_1(M)$ (que é exponencial em $m_1$, mas linear em $m_2$).
   • Eles utilizam o algoritmo Frank-Wolfe para encontrar um hiperplano separador $M$ e então resolvem o problema de otimização quadrática binária (MaxCut) resultante de forma exata usando o solver de branch-and-bound de [13] e o solver QuBowl de [39].
   • Para $d=3$, eles refinam estratégias quânticas existentes utilizando o primeiro nível da hierarquia de Lasserre para melhorar ligeiramente o limite inferior.

Principais Contribuições e Resultados

• Limites Inferiores Certificados para $d \in \{3, 4, 5\}$:
  O artigo fornece limites inferiores rigorosamente certificados que melhoram o estado da arte (SoA) para $d=3, 4, 5$. Pela monotonicidade de $KG(d)$, estas melhorias estendem-se a todos os $d \leq 9$.

  • $KG(3) \geq 1.43670$ (melhorando o anterior $1.43665$).
  • $KG(4) \geq 1.48579$ (melhorando o anterior $1.48217$).
  • $KG(5) \geq 1.49339$ (melhorando o anterior $1.48217$).
  • Estes resultados superam os melhores limites conhecidos para $KG(d)$ até $d=9$.

• Limites Heurísticos para Dimensões Superiores:
  Utilizando estruturas altamente simétricas (especificamente o sistema de raízes $E_7$ e o 120-cell), os autores derivam limites inferiores heurísticos que são significativamente superiores aos valores do SoA atual.

  • Para $KG(7)$, o sistema de raízes $E_7$ produz um limite heurístico de $\approx 1.4997$, que é superior ao limite certificado para $KG(5)$.
  • Para $KG(8)$, o 120-cell produz um limite heurístico de $\approx 1.5138$.
  • Os autores observam que, embora estes limites sejam atualmente heurísticos devido à incapacidade de resolver as instâncias correspondentes de $SDP_1$ de forma exata, as instâncias simétricas subjacentes são fornecidas para trabalhos futuros para potencialmente certificá-las.

• Constantes Generalizadas $KG(d \to \mathbb{C})$:
  Os autores estendem sua análise para as constantes de Grothendieck generalizadas $KG(d \to 2)$, que se relacionam com a vantagem da mecânica quântica complexa de $d$ dimensões sobre a mecânica quântica real de qubits.

  • Limites Inferiores: Eles fornecem limites inferiores numéricos para $KG(d \to 2)$ utilizando a hierarquia de Lasserre (nível 2) para limitar superiormente o $SDP_2(M)$. Estes limites melhoram o estado da arte para diversas dimensões (ex: $d=3, 4, 5$).
  • Limite Superior: Eles derivam um limite superior analítico rigoroso para $KG(3 \to 2) \leq 1.1233\dots$ usando um método de decomposição adaptado de [14]. Este é o primeiro limite superior não trivial para esta constante específica.

Significância e Alegações
O artigo alega que, ao combinar técnicas de projeção Frank-Wolfe com solvers de otimização binária avançados, conseguiu estreitar os limites inferiores conhecidos para as constantes de Grothendieck de ordem finita no intervalo $3 \leq d \leq 9$. O trabalho destaca que, embora a certificação exata para instâncias altamente simétricas de alta dimensão permaneça computacionalmente difícil, os resultados heurísticos sugerem que os valores reais destas constantes podem ser significativamente maiores do que anteriormente pensado.

Os autores enfatizam a conexão com a não-localidade quântica, interpretando $KG(d \to 2)$ como a vantagem quantitativa da mecânica quântica complexa sobre a mecânica quântica real. O seu limite superior rigoroso sobre $KG(3 \to 2)$ fornece um limite concreto para esta vantagem. O artigo conclui que as instâncias e métodos fornecidos oferecem um caminho para pesquisas futuras explorarem a simetria para resolver os problemas de otimização quadrática restantes, potencialmente levando a limites que poderiam competir com o melhor limite inferior conhecido para a constante de Grothendieck de ordem infinita ($\approx 1.6769$).