Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy

Problema

As Redes Neurais de Grafos (GNNs) tornaram-se centrais para o aprendizado de dados relacionais em química, biologia e otimização, impulsionadas pelo primitivo de "passagem de mensagem" (message passing). No entanto, as contrapartes quânticas existentes enfrentam limitações significativas:

1. Falta de Passagem de Mensagem Real: A maioria dos modelos de grafos quânticos propostos não realiza a passagem de mensagem dentro do circuito quântico. Em vez disso, eles mapeiam as arestas do grafo para portas de circuito, mas dependem de pós-processamento clássico para agregar informações de vizinhança, perdendo as vantagens coerentes das operações quânticas.
2. Teto de Expressividade: As GNNs de passagem de mensagem padrão são limitadas pelo teste 1-Weisfeiler–Leman (1-WL), o que significa que não conseguem distinguir certos grafos estruturalmente distintos (ex: moléculas não isomórficas específicas ou subestruturas).
3. Treinabilidade e Escalabilidade: Os Circuitos Quânticos Variacionais (VQCs) frequentemente sofrem com o problema dos "platôs estéreis" (barren plateaus), onde os gradientes desaparecem exponencialmente à medida que o tamanho do circuito cresce, tornando o treinamento impossível para grafos grandes. Além disso, poucos modelos quânticos oferecem garantias de equivariância de permutação ou escalabilidade para grandes instâncias de grafos.

Metodologia

Os autores introduzem um framework de Rede Neural de Grafo Quântica (QGNN) construído sobre circuitos de preservação de subespaço que opera inteiramente no regime quântico. A arquitetura consiste em quatro componentes principais:

1. Carregador de Dados Hierárquico ($V$): O sistema utiliza dois registradores:

   • Um Registrador de Nós ($N$ qubits) codificando nós do grafo em um peso de Hamming específico $j$. Os estados da base representam $j$-subconjuntos de nós (ex: nós únicos em $j=1$, arestas em $j=2$, triângulos em $j=3$).
   • Um Registrador de Embedding ($D$ qubits) codificando características em um peso de Hamming $k$.
   • Um codificador de partícula de Givens controlado carrega as características dos nós no subespaço conjunto $H^j_N \otimes H^k_D$.

2. Camada de Adjacência Equivariante ($A(G)$): Esta camada codifica a conectividade do grafo aplicando rotações de Givens entre pares de qubits de nós correspondentes a arestas. Os ângulos de rotação são derivados de pesos de arestas em uma ordenação canônica, garantindo que a operação respeite a estrutura do grafo sem depender de rótulos de nós.

3. Evolução Treinável ($W(\theta)$): Atuando exclusivamente no registrador de embedding, esta camada atualiza as características dos nós. Ela utiliza portas de preservação de subespaço (especificamente uma parametrização de Cayley de $SO(D)$ elevada para a representação composta) para garantir que a dinâmica permaneça dentro de um subespaço estruturado, evitando o platô estéril.

4. Mistura de Registradores Conjuntos ($M(\theta_M)$): Uma camada final acopla os registradores de nós e de embedding via rotações de Givens, permitindo que a informação flua entre os subespaços estruturais e de características.

Mecanismos Chave:

• Passagem de Mensagem: O circuito realiza a passagem de mensagem de forma coerente. A camada de adjacência roteia amplitudes ao longo das arestas, e a evolução treinável atualiza as características. O re-upload do carregador em cada camada introduz não-linearidade.
• Equivariância de Permutação: A arquitetura é exatamente equivariante à permutação por construção. Como a evolução treinável atua apenas no registrador de embedding compartilhado e as camadas de adjacência/mistura seguem uma ordenação canônica baseada em pesos de arestas (não em rótulos de nós), o renomear dos nós simplesmente renomeia a saída sem alterar a função.
• Leitura (Readout): As características são lidas via matriz de densidade de partícula única (1-RDM) do registrador de embedding ($\gamma_{pq} = \langle \psi | a^\dagger_p a_q | \psi \rangle$). Isso pode ser estimado com custo polinomial ($O(D^3/\epsilon^2)$) usando sombras de matchgate ou leituras determinísticas de Hartree–Fock, independente do número total de nós $N$.

Principais Contribuições

1. Garantias Teóricas: O artigo prova que a QGNN realiza verdadeira passagem de mensagem, é exatamente equivariante à permutação e alcança expressividade $j$-WL. Ao definir o número de partículas do registrador de nós como $j \ge 3$, o modelo pode distinguir pares de grafos que o teste 1-WL padrão (e, portanto, todas as GNNs de passagem de mensagem padrão) não consegue distinguir.
2. Escalabilidade via Preservação de Subespaço: Ao confinar a dinâmica a um subespaço de tamanho fixo (determinado por $D$ e $k$, não por $N$), o modelo evita o desaparecimento exponencial de gradiente associado a VQCs genéricos.
3. Estratégia de Pré-treinamento: O framework adota uma abordagem "treine-pequeno, implemente-grande". Como os parâmetros treináveis atuam apenas no registador de embedding (que é independente do tamanho do grafo), um modelo treinado em grafos pequenos pode ser transferido para instâncias maiores inicializando o modelo maior com os parâmetros do modelo menor.

Resultados

O framework foi validado através de simulações clássicas de larga escala (até 56 qubits) em três conjuntos de dados:

1. Grafos Cai–Fürer–Immerman (CFI):

   • Objetivo: Distinguir pares de grafos não isomórficos que o 1-WL não consegue separar.
   • Resultado: A QGNN alcançou 100% de precisão de teste exatamente nos números de partículas previstos ($j=3$ para CFI(K3) e $j=4$ para CFI(K4)), enquanto as bases 1-WL permaneceram no nível do acaso. Isso confirma a capacidade do modelo de exceder o teto do 1-WL.

2. Predição de Propriedades Moleculares QM9:

   • Objetivo: Predizer o gap HOMO–LUMO para 130.831 moléculas.
   • Resultado: Aumentar o número de partículas $j$ de 1 para 3 reduziu o Erro Médio Absoluto (MAE) de 0.398 eV para 0.235 eV, apesar de manter a contagem de parâmetros quase constante. Isso demonstra que a resolução estrutural de ordem superior melhora o desempenho em tarefas químicas reais.

3. Problema do Caixeiro Viajante Euclidiano (TSP):

   • Objetivo: Encontrar rotas próximas das ótimas para $N$ cidades ($N$ até 50).
   • Resultado: O modelo produziu rotas com um ratio de 1.201 para $N=50$ (onde 1.0 é o ótimo). Crucialmente, o modelo permaneceu treinável nessas escalas.
   • Treinabilidade: A variância do gradiente permaneceu polinomial (não exponencial) conforme o número de qubits aumentou até 56. O aprendizado por transferência (inicializando modelos maiores a partir de menores treinados) manteve os sinais de gradiente de 1 a 2 ordens de magnitude acima da inicialização aleatória.
   • Leitura (Readout): Leituras baseadas em matchgate superaram significativamente as leituras de base computacional, recuperando informações fora da diagonal essenciais para o desempenho da tarefa.

Significância e Alegações

O artigo afirma abrir um caminho para algoritmos quânticos de curto prazo que possuem tanto garantias teóricas quanto escalabilidade prática.

• Unindo Teoria e Prática: Ele traz os princípios do aprendizado em grafos (passagem de mensagem, equivariância, hierarquia WL) diretamente para o design de circuitos quânticos, indo além de modelos quânticos heurísticos.
• Resolvendo a Treinabilidade: Ao utilizar a dinâmica de preservação de subespaço e pré-treinamento, o trabalho aborda o gargalo do platô estéril, demonstrando que modelos de grafos quânticos podem ser treinados em instâncias de grande escala.
• Expressividade: Fornece o primeiro modelo de grafo quântico comprovado que pode superar o limite de expressividade 1-WL, oferecendo uma base teórica para distinguir estruturas de grafos complexas que as redes de passagem de mensagem clássicas perdem.

Os autores enfatizam que, embora a validação atual seja via simulação clássica, a arquitetura foi projetada para ser compatível com hardware quântico de curto prazo (exigindo ~56 qubits para $N=50$), com custos de leitura que escalam polinomialmente com a dimensão das características, em vez do tamanho do grafo.