Resumo Técnico: Alinhamento Emergente entre Problema e Grafo em Topologias de Entrelaçamento Descobertas por RL para QAOA

Definição do Problema

No Algoritmo de Otimização Aproximada Quântica (QAOA), a topologia de entrelaçamento — o conjunto de pares de qubits conectados por portas de dois qubits — é convencionalmente fixa para coincidir com o conjunto de arestas do grafo do problema (por exemplo, a instância de MaxCut). Embora isso garanta que cada termo no hamiltoniano de custo seja abordado, isso acopla o design do circuito ao conhecimento explícito do problema e pode não gerar o circuito mais treinável sob orçamentos de otimização limitados.

A questão central abordada é se um agente de Aprendizado por Reforço (RL) pode descobrir topologias de entrelaçamento eficazes para a otimização de MaxCut baseada em QAOA sem acesso direto à estrutura do grafo do problema. Especificamente, os autores investigam se um agente, observando apenas as arestas que ele inseriu e a razão de aproximação resultante, pode inferir a estrutura subjacente do problema e construir uma topologia que otimize o equilíbrio entre expressividade e treinabilidade do circuito.

Metodologia

Visão Geral do Framework

Os autores propõem um framework de loop aninhado:

1. Loop Externo (Agente de RL): Um agente de Otimização de Política Próxima (PPO) com Máscara constrói sequencialmente uma topologia de entrelaçamento selecionando arestas não direcionadas (portas IsingZZ) para adicionar ao circuito.
2. Loop Interno (Otimizador VQA): Um otimizador clássico (Adam) treina os parâmetros variacionais ($\gamma, \beta$) do circuito QAOA resultante para maximizar a razão de aproximação (AR) em uma instância específica de MaxCut.

Formulação do Processo de Decisão de Markov (MDP)

• Espaço de Estados ($S$): A observação do agente é um vetor de comprimento fixo contendo:
  • A sequência de arestas inseridas até o momento (índices de qubits normalizados).
  • A fração do passo atual em relação ao orçamento de arestas.
  • A razão de aproximação atual proveniente do loop de otimização interno.
  • Crucialmente, a observação não contém nenhuma informação explícita sobre as arestas do grafo do problema. O conhecimento estrutural deve ser inferido unicamente através do sinal de recompensa.
• Espaço de Ações ($A$): O agente seleciona entre todos os pares de qubits não direcionados mais uma ação STOP.
• Máscara de Ação (Action Masking): Uma máscara booleana impede a seleção de arestas que já estão na topologia, garantindo circuitos válidos.
• Recompensa ($R$): Uma recompensa terminal esparsa igual à razão de aproximação final alcançada após o loop de otimização interno (50 passos de gradiente durante o treinamento).

Ansatz QAOA

• O circuito utiliza uma camada $p=1$ para treinamento.
• Emprega uma formulação de QAOA multi-ângulo (ma-QAOA) onde cada aresta na topologia aprendida $T$ e cada qubit possui um parâmetro variacional independente. Isso proporciona um controle mais refinado do que o QAOA padrão.
• A unitária de mistura consiste em rotações $R_X$, e a unitária de custo consiste em portas IsingZZ nas arestas definidas por $T$.

Configuração Experimental

• Instâncias: Grafos aleatórios de Erdős–Rényi não ponderados $G(n, 0.5)$ com $n \in \{6, 8, 10\}$ qubits.
• Baselines: Topologia completa do grafo do problema, cadeias lineares, topologias de anel e subconjuntos aleatórios de diversas densidades.
• Métricas: Razão de Aproximação (AR), Contagem de Arestas, Razão de Sobreposição ($|T \cap E|/|T|$), Similaridade de Jaccard e medida de entrelaçamento de Meyer–Wallach.

Principais Resultados

1. Alinhamento Emergente Problema-Grafo

Apesar de não possuir conhecimento explícito do grafo do problema, o agente de RL converge consistentemente para topologias que são subconjuntos estritos das arestas do grafo do problema.

• Em instâncias de 8 e 10 qubits, a razão de sobreposição (fração de arestas selecionadas pertencentes ao grafo do problema) atinge 1.0 em todas as sementes.
• O agente aprende a selecionar apenas $\sim39\%$ das arestas do problema para instâncias de 10 qubits, mas cada aresta selecionada é relevante para o problema.
• Isso indica que o landscape de otimização variacional codifica implicitamente informações estruturais sobre o hamiltoniano de custo, as quais o agente extrai através da maximização da recompensa.

2. Troca entre Treinabilidade e Expressividade

O desempenho das topologias aprendidas é altamente dependente do orçamento de otimização:

• Baixo Orçamento (50 passos): As topologias esparsas e aprendidas superam significativamente a topologia do grafo completo do problema (AR $\approx$ 0.808 vs. 0.676). O grafo completo introduz muitos parâmetros ($\sim20$) para que o orçamento limitado converja efetivamente.
• Alto Orçamento (500 passos): A topologia do grafo completo do problema recupera e supera a topologia de RL (AR $\approx$ 0.860 vs. 0.832).
• Conclusão: No regime estudado, a topologia governa primordialmente a velocidade de convergência em vez da qualidade assintótica da solução. A topologia de RL otimiza para uma convergência rápida sob restrições de recursos.

3. Escalonamento com Profundidade de Circuito

Quando avaliado com circuitos mais profundos ($p=2, 3$) e 300 passos de otimização:

• A vantagem da topologia de RL desaparece. A topologia completa atinge AR = 1.000 em $p=2$, enquanto a topologia de RL estabiliza em torno de 0.913.
• Isso confirma que a esparsidade descoberta pelo RL é uma estratégia para o regime de baixo orçamento e baixa profundidade; com profundidade e computação suficientes, topologias mais densas são estritamente superiores.

Significância e Alegações

O artigo reivindica três contribuições primárias:

1. Descoberta de Codificação Estrutural Implícita: O trabalho demonstra que o landscape de otimização variacional para QAOA codifica inerentemente informações estruturais sobre o hamiltoniano do problema. Um agente pode inferir as arestas corretas do grafo do problema apenas maximizando a razão de aproximação, sem nunca visualizar o grafo.
2. Identificação de uma Troca Específica: O estudo revela um distinto equilíbrio entre treinabilidade e expressividade governado pela densidade da topologia. Topologias esparsas e alinhadas ao problema são ideais para restrições de curto prazo (tempos de coerência limitados e passos de otimização reduzidos) porque reduzem o espaço de parâmetros, permitindo uma convergência mais rápida.
3. Validação Metodológica: O framework valida o uso de RL para busca de arquitetura de circuitos em otimização combinatória, isolando especificamente o papel da topologia de entrelaçamento enquanto mantém os tipos de portas e templates de circuito fixos.

Os autores mantêm modéstia quanto ao escopo, observando que a "propriedade de subconjunto" foi observada em instâncias pequenas ($n \le 10$) e pode não persistir em escalas maiores onde a simulação clássica é inviável. Eles também enfatizam que o ganho de desempenho é secundário ao insight sobre a natureza do landscape de otimização; a topologia de RL não é uma solução superior universal, mas uma otimização específica para regimes de orçamento limitado.