Projected Variational Quantum Extragradient for Zero-Sum Games

Título: Projeção Variacional Quântica Extragradient para Jogos de Soma Zero

1. Problema e Motivação

O artigo aborda o problema de calcular Equilíbrios de Nash (EN) aproximados em jogos matriciais de soma zero com dois jogadores.

• Contexto: Jogos de soma zero são fundamentais em cibersegurança, aprendizado de máquina adversarial e controle robusto. O equilíbrio de Nash corresponde a um ponto de sela na otimização bilinear clássica.
• Desafio: Métodos clássicos de programação linear tornam-se impraticáveis para jogos de grande escala ou baseados em oráculos. Além disso, métodos de primeira ordem clássicos operam diretamente no espaço de estratégias, que pode ser de alta dimensão.
• Oportunidade Quântica: O uso de Circuitos Quânticos Parametrizados (PQCs) para representar distribuições de probabilidade (estratégias mistas) oferece uma nova abordagem. No entanto, transformar o problema bilinear clássico em um espaço de parâmetros quânticos introduz não-linearidades, resultando em um problema de otimização min-max não convexo-não côncavo, o que torna a convergência para o equilíbrio desafiadora.

2. Metodologia Proposta: VQEG

Os autores propõem um framework chamado Projected Variational Quantum Extragradient (VQEG). A metodologia é dividida em três componentes principais:

A. Embedding Dominado (Dominant Embedding)
Para lidar com tamanhos de jogo arbitrários $(m, n)$ que não são potências de dois (necessários para qubits), os autores introduzem uma técnica de embedding:

• O jogo original é mapeado para um jogo $(M, N)$, onde $M$ e $N$ são as menores potências de dois maiores que $m$ e $n$.
• Preservação do Equilíbrio: Ao contrário do preenchimento com zeros simples (que alteraria o valor do jogo), o método adiciona "ações fictícias" (dummies) com recompensas estritamente dominadas (muito baixas para o jogador linha e muito altas para o jogador coluna).
• Resultado Teórico: Garante que, em qualquer Equilíbrio de Nash do jogo embutido, a probabilidade de escolher as ações fictícias seja zero, preservando a estrutura do equilíbrio do jogo original.

B. Parametrização Variacional e Estimativa de Gradiente

• Estratégias: As estratégias mistas dos jogadores são representadas como distribuições de Born geradas por PQCs. O jogador linha usa um circuito $U_\theta$ e o jogador coluna usa $V_\phi$.
• Função Objetivo: O payoff esperado é expresso como o valor esperado de um observável diagonal, permitindo a avaliação via medição de qubits.
• Gradiente: Utiliza a Regra de Deslocamento de Parâmetros (Parameter-Shift Rule) para calcular gradientes exatos (em valor esperado) a partir de medições de shots (amostragens). Isso torna o método compatível com hardware quântico atual (ruidoso).
• Estimadores Estocásticos: Os gradientes são estimados com um número finito de shots ($S$), introduzindo ruído estatístico com variância que escala como $O(1/S)$.

C. Algoritmo de Atualização Extragradient Projetada
Para lidar com a não convexidade e o ruído, o algoritmo utiliza um método de Extragradient com projeção:

1. Passo Preditivo: Calcula um ponto intermediário usando o gradiente estimado no ponto atual.
2. Passo Corretivo: Calcula o gradiente no ponto intermediário e atualiza a iteração final.
3. Projeção: Garante que os parâmetros permaneçam dentro de um conjunto convexo e limitado ($W$).
   Isso mitiga comportamentos oscilatórios comuns em métodos de gradiente simples para problemas de ponto de sela.

3. Contribuições Principais

1. Parametrização Quântica Variacional: Introdução de uma representação de estratégias mistas via distribuições de Born de PQCs, transformando o problema de jogo em um problema de otimização de parâmetros.
2. Embedding Dominado: Desenvolvimento de uma técnica para mapear jogos de qualquer tamanho para dimensões compatíveis com qubits sem alterar a estrutura do equilíbrio.
3. Algoritmo VQEG: Proposição de um algoritmo de extragradient projetado que utiliza estimadores de gradiente baseados em shots e a regra de deslocamento de parâmetros.
4. Análise de Convergência: Prova teórica de convergência para estacionariedade de primeira ordem aproximada no espaço de parâmetros, sob suposições de suavidade e variância limitada. A variância do estimador escala como $O(1/S)$.
5. Certificado de Equilíbrio: Reconhecimento de que a estacionariedade no espaço de parâmetros não garante otimalidade no jogo original; portanto, o desempenho é avaliado usando o Gap de Nash (Nash Gap) no espaço do jogo.

4. Resultados Numéricos

Os experimentos foram realizados em instâncias de jogos de soma zero de tamanhos variados ($2 \times 2$ até $32 \times 32$) e diferentes classes:

• Jogos com Linha Dominante: O VQEG alcançou soluções de alta precisão (Gaps de Nash próximos à precisão numérica) em todos os tamanhos testados, demonstrando convergência estável na última iteração.
• Jogos "Matching Pennies": O método manteve-se estável e preciso, com gaps muito pequenos.
• Jogos Aleatórios (Unstructured): O desempenho degradou-se com o aumento do tamanho do problema, resultando em gaps de Nash maiores. Isso destaca os desafios impostos pela limitação da expressividade do circuito e pelo ruído estocástico em configurações sem estrutura clara.
• Vazamento (Leakage): A técnica de embedding mostrou-se eficaz, com vazamento de probabilidade para as ações fictícias sendo desprezível ($\approx 10^{-16}$).

5. Significado e Conclusão

O trabalho demonstra a viabilidade de usar hardware quântico variacional para resolver problemas de teoria dos jogos complexos.

• Inovação: É uma das primeiras abordagens a integrar explicitamente a estimativa de gradiente baseada em shots e a análise de variância em um algoritmo de extragradient para jogos quânticos.
• Limitações e Futuro: Embora eficaz para jogos estruturados, o método enfrenta desafios em cenários não estruturados devido ao ruído e à expressividade limitada dos ansatzes atuais. Trabalhos futuros focarão em técnicas de redução de variância e regularização para melhorar a escalabilidade e robustez.

Em resumo, o VQEG oferece um framework promissor para a computação de equilíbrios em jogos de soma zero, unindo a teoria de otimização de pontos de sela com as capacidades emergentes da computação quântica variacional.