Resumo Técnico: Amostragem de Surrogato Informada por Quantum (QISS) para Otimização Combinatória

1. Definição do Problema

Problemas de otimização combinatória, como o Corte Máximo (MaxCut) e o Conjunto Independente Máximo (MIS), são computacionalmente desafiadores em escala. Embora o Algoritmo de Otimização Aproximada Quântica (QAOA) ofereça uma abordagem híbrida quântico-clássica promissora, seu desempenho em hardware de curto prazo é limitado pelo ruído e pelas limitações de coerência. Essas restrições tipicamente limitam as implementações de QAOA a circuitos rasos (profundidade baixa $p$).

Uma limitação fundamental do QAOA raso é a localidade: para grafos esparsos, o "cone de luz" do circuito é limitado pela profundidade $p$, não pelo tamanho do problema $N$. Consequentemente, o QAOA de $p$ fixo frequentemente falha em explorar estruturas globais do problema e herda limitações semelhantes às de algoritmos clássicos locais. Além disso, a distribuição completa de saída de um estado quântico é geralmente intratável para amostragem clássica, e o próprio dispositivo quântico não consegue produzir diretamente soluções de alta qualidade quando restrito a profundidades rasas.

O artigo aborda a necessidade de um método que aproveite os pontos fortes específicos dos dispositivos quânticos de curto prazo — estimar eficientemente estatísticas locais de baixa ordem — enquanto delega a geração de soluções candidatas para o pós-processamento clássico escalável.

2. Metodologia: Amostragem de Surrogato Informada por Quantum (QISS)

Os autores propõem a Amostragem de Surrogato Informada por Quantum (QISS), um framework de pós-processamento que gera soluções candidatas a partir de correlações quânticas de baixo peso sem exigir dependência explícita da estrutura do problema combinatório durante a fase de amostragem.

Fluxo de Trabalho Principal

1. Estimativa Quântica: Um circuito QAOA raso (profundidade $p$) é executado em um dispositivo quântico (ou simulado) para estimar um conjunto selecionado de valores de expectativa de baixo peso (correladores) $\mu_{S_\alpha}$:
   $$\mu_{S_\alpha} = \langle \psi_p(\gamma, \beta) | \prod_{i \in S_\alpha} Z_i | \psi_p(\gamma, \beta) \rangle$$
   O artigo foca em pesos $|S_\alpha| \in \{1, 2\}$. Esses valores são acessíveis via medições repetidas e são passíveis de mitigação de erro.

2. Construção da Distribuição Surrogata: Uma distribuição de fatores clássica $P(z)$ é construída sobre o espaço de soluções $\{-1, +1\}^N$ usando esses correladores medidos como parâmetros:
   $$P(z) \propto \prod_{S_\alpha \in \mathcal{S}} \left( 1 + \mu_{S_\alpha} \chi_{S_\alpha}(z) \right)$$
   onde $\chi_{S_\alpha}(z) = \prod_{i \in S_\alpha} z_i$ é a função de paridade. Esta distribuição é equivalente a uma distribuição de Gibbs de um Hamiltoniano de Ising efetivo $H'$ com acoplamentos $J_{S_\alpha} = -\text{arctanh}(\mu_{S_\alpha})$.

3. Amostragem Clássica: Soluções candidatas são extraídas de $P(z)$ usando Monte Carlo via Cadeia de Markov (MCMC). A amostragem utiliza atualizações condicionais de sítio único, que são eficientes porque a probabilidade condicional para uma inversão de spin depende apenas dos fatores locais envolvendo esse spin. A constante de normalização (função de partição) nunca é necessária.

4. Seleção de Correladores: O artigo distingue entre dois conjuntos de correladores:

   • Conjunto de Arestas ($\mathcal{S} = E \cup V$): Apenas as arestas diretas do grafo do problema. Em grafos localmente semelhantes a árvores, isso reproduz os momentos do QAOA sem melhorias.
   • Conjunto Aumentado ($\mathcal{S}' = E' \cup V$): Inclui todos os pares $(i, j)$ dentro da distância do cone de luz $d_G(i, j) \le 2p$. Isso cria um grafo de fatores denso e não semelhante a árvore, permitindo que o surrogato capture correlações de ordem superior implicitamente e gere soluções superiores à saída bruta do QAOA.

Características Principais

• Livre de Treinamento: O método utiliza ângulos de QAOA otimizados para árvores (da Ref. [61]), não exigindo otimização variacional do surrogato.
• Modularidade: A etapa de amostragem é agnóstica à função de custo; ela requer apenas os correladores.
• Resiliência ao Ruído: O mapeamento de correladores para acoplamentos ($\text{arctanh}$) é suave, tornando o surrogato robusto ao ruído nas estatísticas medidas.

3. Contribuições Principais e Resultados

A. MaxCut em Grafos 3-Regulares

• Desempenho vs. Vanilla QAOA: Quando utilizando o conjunto de correladores aumentado (todos os pares dentro da distância $2p$), o QISS supera significativamente o vanilla QAOA. Especificamente, o QISS usando correladores de um circuito QAOA de profundidade $p=3$ ou $p=4$ alcança frações de corte médias que ultrapassam o vanilla QAOA na profundidade $p=17$ (a maior profundidade para a qual ângulos otimizados para árvores são conhecidos).
• Integração de Warm-Start: O método foi combinado com o Regularized Warm-Start QAOA (RWS-QAOA). Mesmo em profundidades rasas ($p=1, 2$), o pós-processamento QISS melhorou a qualidade da solução do RWS-QAOA, aproximando a razão de aproximação do limite ótimo.
• Validação em Hardware: Experimentos foram conduzidos no QPU IQM Emerald de 54 qubits. Os resultados demonstraram que o QISS é altamente resiliente ao ruído. As razões de aproximação obtidas a partir de correladores brutos e ruidosos do QPU foram quase indistinguíveis das obtidas em simulações sem ruído. O ruído do dispositivo foi efetivamente "lavado" pelo pós-processamento, tornando a mitigação de erro irrelevante para a qualidade da solução final neste regime.
• Escalabilidade: O método manteve o desempenho até $N=140$ (limitado pelo número de qubits disponíveis após o congelamento de variáveis), com razões de aproximação permanecendo estáveis e bem acima das garantias padrão de SDP.

B. Conjunto Independente Máximo (MIS)

• Tratamento de Restrições: Ao contrário do MaxCut, o MIS é um problema com restrições. As amostras de QISS podem conter conflitos (nós adjacentes ambos selecionados). Os autores introduziram uma rotina simples de poda de pós-processamento para resolver conflitos e adicionar nós válidos de forma gulosa.
• Desempenho: Para o MIS, usar apenas correladores de arestas resultou em um desempenho pior que o vanilla QAOA devido à falta de simetria $Z_2$ e fatores sobrepostos. No entanto, o uso do conjunto aumentado de correladores combinado com a rotina de poda permitiu que o QISS superasse o QAOA isolado e competisse com heurísticas clássicas de estado da arte (ex: busca com prioridade linear e algoritmos gulosos potencializados por quantum).

C. Comparação com Solvers Clássicos

O QISS foi testado contra Simulated Annealing (SA) e a relaxação de posto dois Burer–Monteiro (BM) do SDP de Goemans–Williamson.

• O QISS combinado com RWS-QAOA produziu resultados competitivos com o solver BM.
• Ao contrário de samplers clássicos cujo desempenho degrada conforme o tamanho do sistema aumenta sob um orçamento de tempo fixo, o QISS aproveita a localidade das correlações do QAOA, que permanecem estáveis com $N$.

4. Significância e Alegações

O artigo afirma que o QISS estabelece um novo regime para otimização de curto prazo onde circuitos quânticos rasos servem não como samplers diretos, mas como geradores de estatísticas informativas para amostragem clássica escalável.

• Divisão de Trabalho: O dispositivo quântico é utilizado por sua capacidade de estimar eficientemente observáveis locais de baixa ordem (que são robustos ao ruído e independentes do tamanho do sistema em termos de custo de amostragem), enquanto o computador clássico lida com a tarefa complexa de sintetizar essas estatísticas em soluções globais.
• Resiliência ao Ruído: Uma descoberta crítica é que a distribuição surrogata é tão robusta que pode recuperar soluções quase ótimas a partir de dados de hardware ruidosos e brutos, sem mitigação. Isso sugere que, para certas tarefas de otimização, o overhead de mitigação de erro complexa pode ser desnecessário se um nível de pós-processamento robusto como o QISS for empregado.
• Escalabilidade: A abordagem evita o escalonamento exponencial da contração clássica para circuitos profundos ao confiar em circuitos rasos e MCMC clássico, oferecendo um caminho para resolver problemas maiores do que a amostragem quântica direta permitiria no hardware atual.

Os autores concluem que, embora o QISS dependa da estrutura específica das correlações medidas, ele fornece um caminho prático, livre de treinamento e eficiente em termos de hardware para melhorar o desempenho de otimização em dispositivos quânticos de curto prazo.