Automated search for highly contextual Kochen-Specker proofs

Resumo Técnico: Busca Automatizada por Provas de Kochen-Specker Altamente Contextuais

Definição do Problema
Provas de Kochen-Specker (KS) baseadas em observáveis utilizam configurações de observáveis de Pauli multi-qubit agrupados em "contextos" (conjuntos de observáveis mutuamente comutativos) cujo produto é $\pm I^{\otimes n}$. Essas provas demonstram contextualidade independente de estado. A robustez de tal prova contra ruído experimental é quantificada pela tolerância de erro por contexto, denotada por $\varepsilon = 2d/|H|$, onde $d$ é o grau de contextualidade (o número mínimo de sinais de contexto que não podem ser reproduzidos por qualquer atribuição clássica) e $|H|$ é o número total de contextos.

Buscas anteriores por provas de alto $\varepsilon$ foram amplamente restritas a "conjuntos mágicos" (magic sets), onde os observáveis residem em um número par de contextos e os contextos negativos são ímpares em número. Embora isso garanta a contextualidade, confina a busca a uma região estreita do espaço de configuração, com o quadrado de Peres-Mermin ($\varepsilon \approx 0,33$) e o pentagrama de Mermin ($\varepsilon = 0,40$) servindo como pequenos exemplos. O objetivo deste trabalho é buscar sistematicamente por configurações com valores de $\varepsilon$ mais altos, indo além das restrições dos conjuntos mágicos.

Metodologia
Os autores utilizam o conceito de hipergrama, uma estrutura abstrata definida como uma terna $(V, H, G)$ consistindo em um hipergrafo de contexto $(V, H)$ e um grafo de anticomutação $(V, G)$. Um insight teórico fundamental de trabalhos anteriores [MG25a] é que o grau de contextualidade é um invariante do hipergrama isoladamente, independente do número específico de qubits ou da rotulagem de Pauli.

Para otimizar a busca, os autores propõem um pipeline que inverte a ordem de enumeração tradicional:

1. Enumeração Baseada em Grafos: Em vez de enumerar hipergrafos e depois verificar a compatibilidade com grafos de anticomutação, os autores enumeram grafos de anticomutação simples e reduzidos $G$.
2. Suporte do Hipergrafo ($HS(G)$): Para cada grafo $G$, eles constroem o suporte do hipergrafo, $HS(G)$, que contém todos os possíveis contextos (conjuntos independentes de $G$ que satisfazem a condição de paridade necessária para a atribuibilidade).
3. Seleção de Candidato Canônico: Em vez de testar todos os subconjuntos de $HS(G)$, o pipeline examina o único hipergrama $(V, HS(G), G)$ para cada grafo. Esta configuração "maximal" é hipotetizada para gerar o maior $\varepsilon$.
4. Espaço de Busca: O pipeline foi aplicado a duas fontes distintas em passagens separadas:
   • O banco de dados House of Graphs: 13.864 grafos conectados e reduzidos com $\le 30$ vértices.
   • Censos de grafos transitivos de vértices: Todos os tais grafos com $\le 24$ vértices (18.948 grafos), cobrindo um espectro mais amplo do que o subconjunto da House of Graphs.
5. Verificação: A atribuibilidade é verificada via uma condição de matriz ($H \cdot G = 0$ sobre $\mathbb{F}_2$). Os graus de contextualidade são computados usando solvers SAT (exatos) ou solvers heurísticos (para instâncias maiores).

Principais Contribuições

1. Pipeline de Busca Sistemática: O artigo estabelece um pipeline completo e automatizado para a descoberta de provas de KS ao operar no nível de hipergramas abstratos derivados de grafos de anticomutação, eliminando a necessidade de rotulagem explícita de qubits durante a fase de busca.
2. Descoberta de Configurações de Alto $\varepsilon$: A busca identificou configurações que excedem significativamente o recorde anterior de $\varepsilon = 0,424$ (de [TLC22a], que era restrito a conjuntos mágicos).
3. Insights Estruturais:
   • Grafos de Linha: Os autores provam (Teorema 4) que toda correspondência perfeita de um grafo base $H$ forma um contexto em seu grafo de linha $L(H)$. Isso explica por que grafos de linha frequentemente geram configurações de alto $\varepsilon$ e identifica o quadrado de Peres-Mermin e o doily como os primeiros membros de famílias infinitas de tais configurações.
   • Uniões Disjuntas: O estudo revela que uniões disjuntas de grafos produzem resultados superiores. Como o número de contextos em uma união disjunta é multiplicativo enquanto o número de observáveis é aditivo, o empilhamento de cópias de pequenos grafos de alto desempenho (como o grafo de Petersen ou $L(K_{3,3})$) aumenta drasticamente o $\varepsilon$.
4. Interpretação Geométrica: O artigo fornece descrições geométricas finitas das principais configurações dentro de espaços polares simpléticos ($W_n$), ligando-as a estruturas específicas como ovoides, quadricas hiperbólicas e planos de Fano.

Resultos
O pipeline recuperou com sucesso configurações conhecidas (quadrado de Peres-Mermin, pentagrama de Mermin, doily) e descobriu novas configurações altamente contextuais:

• Recorde de $\varepsilon$: A melhor configuração encontrada é o grafo 3-Petersen (três cópias disjuntas do grafo de Petersen), que produz $\varepsilon = 0,707$. Isso supera o recorde anterior de 0,424 e o recorde não publicado de 0,5.
• Outras Configurações Notáveis:
  • $3L(K_{3,3})$ (três cópias disjuntas do grafo de linha de $K_{3,3}$): $\varepsilon = 0,637$.
  • $2L(K_6)$: $\varepsilon = 0,612$.
  • $L(K_{5,5})$ (grafo de Rook): $\varepsilon = 0,600$.
  • $L(C(10, \{1, 3\}))$: $\varepsilon = 0,500$ (identificado como a configuração encontrada anteriormente em [Mul25]).
• Estatísticas do Banco de Dados: A busca cobriu 13.864 grafos da base de dados House of Graphs e 18.948 grafos transitivos de vértices. Apenas uma pequena fração gerou hipergramas contextuais válidos. Os resultados confirmam que alta simetria (transitividade de vértices) e propriedades estruturais específicas (serem grafos de linha ou uniões disjuntas) correlacionam-se com um alto $\varepsilon$.

Significância e Alegações
O artigo afirma que, ao deslocar o foco da busca de configurações quânticas específicas para os hipergramas abstratos subjacentes, é possível descobrir provas de KS com muito maior robustez ao ruído. Os autores enfatizam que a união disjunta de grafos é a característica estrutural mais eficaz para maximizar o $\varepsilon$, pois aproveita a natureza multiplicativa da geração de contextos.

O trabalho identifica o quadrado de Peres-Mermin e o doily não como anomalias isoladas, mas como os membros iniciais de famílias infinitas geradas por grafos de linha. Além disso, os autores observam que, embora sua busca atual seja limitada por restrições computacionais (solvers SAT têm dificuldade além de ~1.000 contextos), a abordagem heurística sugere que configurações ainda maiores (por exemplo, $K_6 \square K_6$) podem produzir valores de $\varepsilon$ ainda mais altos, potencialmente aproximando-se de 1. O artigo conclui sugerindo que trabalhos futuros poderiam envolver loops automatizados usando IA para propor famílias de grafos e conjecturas, embora os resultados atuais sejam baseados na exploração guiada por humanos de bases de dados existentes.