Generative Quantum Search for Combinatorial Optimization: Learning Shallow Quantum Samplers for Classically Refined Solution Subspaces

Resumo Técnico: Busca Quântica Generativa para Otimização Combinatória

Enunciado do Problema
Esta pesquisa investiga se amostradores quânticos rasos podem superar amostradores clássicos em otimização combinatória ao posicionar uma maior massa de probabilidade dentro de um "bacia de recuperação clássica". O estudo adapta a arquitetura Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction (GQE+QSCI), originalmente desenvolvida para química quântica, para o domínio da otimização de grafos (especificamente o Conjunto Independente Máximo Ponderado, MWIS). A hipótese central é que um amostrador quântico poderia gerar uma distribuição de soluções candidatas que, quando refinada por um algoritmo de reparo e expansão clássico, resulte em uma taxa de sucesso superior à dos amostradores clássicos.

Metodologia
O autor propõe o framework GQO+QSS (Generative Quantum Optimization + Quantum-Selected Search), que segue um pipeline de quatro estágios:

1. Política Generativa: Um modelo de aprendizado de máquina (política condicionada ao grafo) gera programas de circuitos quânticos (ex: parâmetros de QAOA).
2. Amostragem Quântica: Os circuitos são executados em um simulador ou QPU (Piast-Q) para produzir strings de bits (soluções candidatas).
3. Recuperação Clássica: Uma função de reparo específica do problema corrige soluções infactíveis, seguida por uma expansão local (ex: vizinhança de $r$-flip) para criar um subespaço de busca restrito.
4. Solver Restrito: Um solver clássico exato encontra a solução ótima dentro deste subespaço restrito.

Formulação Teórica Fundamental
O artigo formaliza a questão do "benefício quântico" usando a massa da bacia de recuperação ($p_r$):
$$p_r(q_\theta, G) = \Pr_{x \sim q_\theta} [x \in A_r(G)]$$
onde $A_r(G)$ é o conjunto de estados que, após o reparo e a expansão de $r$-flip, contêm o ótimo global. A probabilidade de sucesso com $B$ disparos (shots) é $P_{success} = 1 - (1 - p_r)^B$. O estudo postula que a métrica crítica não é o tamanho do subespaço amostrado em relação ao espaço total ($|S_Q|/2^n$), mas sim a massa de probabilidade $p_r$ que o amostrador coloca na bacia recuperável.

Protocolo Experimental

• Datasets: 150 instâncias de MWIS com verdades fundamentais (ground truths) certificadas via CBC + verificação por força bruta.
• Baselines: Nove amostradores foram comparados, incluindo uniforme aleatório, ganancioso (greedy), simulated annealing (SA), busca tabu, busca local de início múltiplo, Metropolis, QAOA com warm-start, QAOA com oráculo (melhor de 50 configurações) e uma política clássica aprendida correspondente.
• Restrições: Um protocolo pré-registrado e congelado com um orçamento fixo de 200 disparos por amostrador.
• Hardware: Os experimentos incluíram simulações e execução no processador de íons aprisionados Piast-Q (20 qubits).

Resultados Principais

1. Dominância Clássica: A busca tabu e o Simulated Annealing (SA) superaram significativamente todos os amostradores quânticos e clássicos aprendidos em todos os tamanhos de problema testados ($n=16$ a $n=28$). A busca tabu alcançou uma massa de bacia de recuperação ($p_r$) variando de 0,822 em $n=16$ a 0,944 em $n=18$, com valores de 0,878 em $n=20$, 0,943 em $n=24$ e 0,901 em $n=28$. O SA variou de 0,088 a 0,428 nestes tamanhos.
2. Subperformance Quântica: Todos os amostradores quânticos (QAOA com warm-start, QAOA com oráculo e políticas generativas) perderam para SA e busca tabu em todos os tamanhos de problema sob o protocolo justo e pré-registrado.
3. Artefato do "Oráculo": Resultados positivos anteriores que mostravam o QAOA superando o SA foram identificados como artefatos da seleção de configuração por instância (um limite superior de "oráculo"). Quando avaliado com configurações aleatórias (um método implantável), o QAOA com oráculo alcançou $p_r = 0,014$ em $n=28$, muito abaixo do 0,088 do SA.
4. Paridade Clássica Aprendida: Uma política clássica aprendida (140K parâmetros) alcançou desempenho comparável ao QAOA com oráculo ($p_r = 0,005–0,101$ vs. $0,014–0,113$), indicando que o circuito quântico não oferece vantagem estrutural sobre um modelo clássico correspondente neste cenário.
5. Robustez do Hardware: Experimentos no Piast-Q mostraram 93,4% de consistência de recuperação entre as amostras do QPU e do simulador, confirmando a robustez do hardware, mas revelando nenhuma vantagem quântica na qualidade da otimização.
6. Transição de Recuperação: O estudo mapeou uma "transição de recuperação" onde o reparo clássico é suficiente para $n \le 16$, mas começa a falhar para $n \ge 20$ com expansão de 2-flip. No entanto, mesmo neste regime de transição, baselines clássicas fortes (SA, Tabu) mantiveram desempenho superior.

Significância e Alegações
O artigo apresenta-se como um estudo de falsificação. Sua principal alegação é que, sob avaliação rigorosa e pré-registrada com baselines aprendidos correspondentes, as distribuições de proposta derivadas de QAOA raso não superam modelos de proposta clássicos correspondentes para capturar bacias de recuperação clássica em MWIS.

• Sem Vantagem Quântica: O autor afirma explicitamente que não há vantagem quântica para a arquitetura GQO+QSS nos regimes testados.
• Refutação de Alegações Anteriores: O estudo atribui os resultados positivos anteriores ao efeito "oráculo" de selecionar a melhor configuração por instância, o que não é um método implantável.
• Correção de Métrica: O artigo argumenta que a "fração do subespaço" ($|S_Q|/2^n$) é uma métrica tautológica sob orçamentos de disparos fixos e que a massa da bacia de recuperação ($p_r$) é a quantidade cientificamente precisa para medir.
• Direção Futura: O autor sugere que, para a amostragem quântica fornecer valor, ela deve consistentemente colocar mais massa na bacia de recuperação do que baselines clássicos fortes (como SA) em regimes onde a recuperação clássica falha ($n \ge 55$), um desafio que os atuais circuitos rasos não atenderam.

O trabalho conclui que, embora a arquitetura GQO+QSS seja um framework válido para otimização híbrida, os atuais amostradores quânticos rasos não fornecem uma vantagem estrutural sobre métodos de busca estocástica clássica fortes para a tarefa específica de captura da bacia de recuperação de MWIS.